An overview of the
A list of double links can be reversed in two ways.
-
By swapping the previous and next Pointers to nodes.
-
By using the stack
In this tutorial, we will cover the first approach, by swapping the previous and next Pointers.
For example, we have the following doubly linked list
When reversed, the double-linked list looks like this.
The program
In this approach, the following points need to be noted.
-
Swap the head and tail of a double-linked list
-
Swap the previous and next Pointers to all nodes
package main
import "fmt"
type node struct {
data string
prev *node
next *node
}
type doublyLinkedList struct {
len int
tail *node
head *node
}
func initDoublyList(a) *doublyLinkedList {
return &doublyLinkedList{}
}
func (d *doublyLinkedList) AddFrontNodeDLL(data string) {
newNode := &node{
data: data,
}
if d.head == nil {
d.head = newNode
d.tail = newNode
} else {
newNode.next = d.head
d.head.prev = newNode
d.head = newNode
}
d.len++
}
func (d *doublyLinkedList) AddEndNodeDLL(data string) {
newNode := &node{
data: data,
}
if d.head == nil {
d.head = newNode
d.tail = newNode
} else {
currentNode := d.head
forcurrentNode.next ! =nil {
currentNode = currentNode.next
}
newNode.prev = currentNode
currentNode.next = newNode
d.tail = newNode
}
d.len++
}
func (d *doublyLinkedList) TraverseForward(a) error {
if d.head == nil {
return fmt.Errorf("TraverseError: List is empty")
}
temp := d.head
fortemp ! =nil {
fmt.Printf("value = %v, prev = %v, next = %v\n", temp.data, temp.prev, temp.next)
temp = temp.next
}
fmt.Println()
return nil
}
func (d *doublyLinkedList) Size(a) int {
return d.len
}
func (d *doublyLinkedList) ReverseDLL(a) {
currentNode := d.head
var nextInList *node
d.head, d.tail = d.tail, d.head
forcurrentNode ! =nil {
nextInList = currentNode.next
currentNode.next, currentNode.prev = currentNode.prev, currentNode.next
currentNode = nextInList
}
}
func main(a) {
doublyList := initDoublyList()
fmt.Printf("Add Front Node: C\n")
doublyList.AddFrontNodeDLL("C")
fmt.Printf("Add Front Node: B\n")
doublyList.AddFrontNodeDLL("B")
fmt.Printf("Add Front Node: A\n")
doublyList.AddFrontNodeDLL("A")
fmt.Printf("Add End Node: D\n")
doublyList.AddEndNodeDLL("D")
fmt.Printf("Add End Node: E\n")
doublyList.AddEndNodeDLL("E")
fmt.Printf("Size of doubly linked ist: %d\n", doublyList.Size())
err := doublyList.TraverseForward()
iferr ! =nil {
fmt.Println(err.Error())
}
fmt.Println("Reversing Doubly Linked List")
doublyList.ReverseDLL()
fmt.Printf("Size of doubly linked ist: %d\n", doublyList.Size())
err = doublyList.TraverseForward()
iferr ! =nil {
fmt.Println(err.Error())
}
}
Copy the code
The output
Add Front Node: C
Add Front Node: B
Add Front Node: A
Add End Node: D
Add End Node: E
Size of doubly linked ist: 5
value = A, prev = , next = &{B 0xc000070060 0xc000070020}
value = B, prev = &{A 0xc000070040}, next = &{C 0xc000070040 0xc000070080}
value = C, prev = &{B 0xc000070060 0xc000070020}, next = &{D 0xc000070020 0xc0000700a0}
value = D, prev = &{C 0xc000070040 0xc000070080}, next = &{E 0xc000070080 }
value = E, prev = &{D 0xc000070020 0xc0000700a0}, next =
Reversing Doubly Linked List
Size of doubly linked ist: 5
value = E, prev = , next = &{D 0xc0000700a0 0xc000070020}
value = D, prev = &{E 0xc000070080}, next = &{C 0xc000070080 0xc000070040}
value = C, prev = &{D 0xc0000700a0 0xc000070020}, next = &{B 0xc000070020 0xc000070060}
value = B, prev = &{C 0xc000070080 0xc000070040}, next = &{A 0xc000070040 }
value = A, prev = &{B 0xc000070020 0xc000070060}, next =
Copy the code
Also, check out our Golang advanced Tutorial series at ——. Golang Advanced tutorial
The postReverse Doubly Linked List in Go (Golang)appeared first onWelcome To Golang By Example.