As we start coding and slowly learning about Data Structures(DS), we come across a very famous linear data structure which is known as a linked list. Linked lists and their related questions are quite popular in interviewers who love problem-solving.
What is a Linked List?
A linked list is a common linear data structure. its elements are also known as **Node** are not stored at a contiguous location. The nodes are linked using pointers. Linked lists are popular as their size is not fixed like an array. Linked list’s each node contains a value and a pointer to the next node. The head pointer points to the first node, and the last node of the list points to null. When the linked list is empty, the head pointer points to null.
Types of Linked Lists:
1. Singly Linked List (Uni-directional)
2. Doubly Linked List (Bi-directional)
3. Circular Linked List
I’ll write about linked list types in a different post as this post about reversing a linked list.
Pros:
- Dynamically increase in size
- Easy to insertion/deletion
Cons:
- Accessing a random node is not allowed.
- Additional memory space needs for each node in a linked list.
- Not cache friendly.
Linked List
Node for a linked list
type Node struct {
prev *Node
next *Node
key interface{}
}
type LinkedList struct {
head *Node
tail *Node
}
Push method for a Linked List
func (ll *LinkedList) Push(key interface{}) {
list := &Node{
next: ll.head,
key: key,
}
if ll.head != nil {
ll.head.prev = list
}
ll.head = list
l := ll.head
for ll.next != nil {
l = l.next
}
ll.tail = l
}
Display a Linked list
func (ll *LinkedList) Display() {
list := ll.head
for list != nil {
fmt.Printf("%+v ->", list.key)
list = list.next
}
fmt.Println()
}
// normal display function
func Display(list *Node) {
for list != nil {
fmt.Printf("%v ->", list.key)
list = list.next
}
fmt.Println()
}
Reverse a Linked list
func (ll *LinkedList) Reverse() {
currentNode := ll.head
var next *Node
var previousNode *Node
ll.tail = ll.head
for currentNode != nil {
next, currentNode.next = currentNode.next, previousNode
previousNode, currentNode = currentNode, next
}
ll.head = previousNode
Display(ll.head)
}
Main function
func main() {
link := LinkedList{}
link.Push(9)
link.Push(12)
link.Push(15)
link.Push(8)
link.Push(1)
link.Push(3)
fmt.Println("==============================")
fmt.Printf("Head: %v\n", link.head.key)
fmt.Printf("Tail: %v\n", link.tail.key)
link.Display()
fmt.Println("==============================")
link.Reverse()
fmt.Printf("head: %v\n", link.head.key)
fmt.Printf("tail: %v\n", link.tail.key)
fmt.Println("==============================")
}
// output
==============================
Head: 3
Tail: 9
3 -> 1 -> 8 -> 15 -> 12 -> 9 ->
==============================
9 -> 12 -> 15 -> 8 -> 1 -> 3 ->
head: 9
tail: 3
==============================
