Overview
A Doubly Linked List can be reversed by below two methods:
- By swapping previous and next pointers of nodes.
- By using stack
In this tutorial, we will cover the first method i.e by swapping previous and next pointers.
Let’s say we have below doubly linked list
After reversing, a doubly-linked list will be like below:
Program
In this approach we need to take care of the below points:
- Swap head and tail of the doubly linked list
- Swap previous and next pointers of 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() *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
for currentNode.next != nil {
currentNode = currentNode.next
}
newNode.prev = currentNode
currentNode.next = newNode
d.tail = newNode
}
d.len++
}
func (d *doublyLinkedList) TraverseForward() error {
if d.head == nil {
return fmt.Errorf("TraverseError: List is empty")
}
temp := d.head
for temp != 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() int {
return d.len
}
func (d *doublyLinkedList) ReverseDLL() {
currentNode := d.head
var nextInList *node
d.head, d.tail = d.tail, d.head
for currentNode != nil {
nextInList = currentNode.next
currentNode.next, currentNode.prev = currentNode.prev, currentNode.next
currentNode = nextInList
}
}
func main() {
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()
if err != 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()
if err != nil {
fmt.Println(err.Error())
}
}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 = Also, check out our Golang advance tutorial Series – Golang Advance Tutorial