Understanding Linked Lists in Go: A Comprehensive Guide for All Skill Levels
A linked list is a linear data structure where each element, known as a node, contains a data value and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, which allows for dynamic memory management. Linked lists come in various forms, such as singly linked lists, doubly linked lists, and circular linked lists.
1. Construction of Singly Linked List
To construct a singly linked list, you’ll need to initialize the head pointer and add nodes one by one. Each node in the list contains data and a reference to the next node. Here’s an example code snippet in Go
package main
import "fmt"
type Node struct {
data int
next *Node
}
type LinkedList struct {
head *Node
}
func (list *LinkedList) Insert(data int) {
newNode := &Node{data: data}
if list.head == nil {
list.head = newNode
} else {
current := list.head
for current.next != nil {
current = current.next
}
current.next = newNode
}
}
func (list *LinkedList) Display() {
current := list.head
if current == nil {
fmt.Println("Linked list is empty")
return
}
fmt.Print("Linked list: ")
for current != nil {
fmt.Printf("%d ", current.data)
current = current.next
}
fmt.Println()
}
func main() {
list := LinkedList{}
list.Insert(10)
list.Insert(20)
list.Insert(30)
list.Insert(40)
list.Display()
}In this example, we define two structs: Node and LinkedList. Node represents a node in the linked list, containing data and a next pointer. LinkedList has a head pointer that points to the first node in the list.
The Insert method is used to add nodes to the linked list. It traverses the list until it reaches the last node and appends the new node at the end.
The Display method is used to print the elements of the linked list. It traverses the list from the head to the last node and displays each node's data.
In the main function, we create a LinkedList object, insert some elements (10, 20, 30, 40), and then display the contents of the linked list.
When you run this code, it will output:
Linked list: 10 20 30 402. Construction of Doubly Linked List
A doubly linked list is a type of linked list where each node contains references to both the previous and next nodes in the list. This bidirectional linkage allows for efficient traversal in both directions.
To construct a doubly linked list, we start by defining a Node structure that includes data and two pointers, prev and next, pointing to the previous and next nodes respectively. We also need to keep track of the head and tail of the list.
Here’s an example code snippet in Go that demonstrates the construction and manipulation of a doubly linked list:
package main
import "fmt"
type Node struct {
data int
prev *Node
next *Node
}
type DoublyLinkedList struct {
head *Node
tail *Node
}
func (dll *DoublyLinkedList) AddNode(data int) {
newNode := &Node{
data: data,
prev: nil,
next: nil,
}
if dll.head == nil {
dll.head = newNode
dll.tail = newNode
} else {
newNode.prev = dll.tail
dll.tail.next = newNode
dll.tail = newNode
}
}
func (dll *DoublyLinkedList) PrintForward() {
currentNode := dll.head
for currentNode != nil {
fmt.Printf("%d ", currentNode.data)
currentNode = currentNode.next
}
fmt.Println()
}
func (dll *DoublyLinkedList) PrintReverse() {
currentNode := dll.tail
for currentNode != nil {
fmt.Printf("%d ", currentNode.data)
currentNode = currentNode.prev
}
fmt.Println()
}
func main() {
dll := DoublyLinkedList{}
dll.AddNode(10)
dll.AddNode(20)
dll.AddNode(30)
dll.AddNode(40)
fmt.Println("Doubly Linked List (forward):")
dll.PrintForward()
fmt.Println("Doubly Linked List (reverse):")
dll.PrintReverse()
}In the above code, we define a Node struct with data, prev, and next fields. The DoublyLinkedList struct contains head and tail pointers, initially set to nil. The AddNode method appends a new node to the end of the list by adjusting the previous and next pointers accordingly.
The PrintForward method traverses the list from the head to the tail, printing the data of each node. Conversely, the PrintReverse method traverses the list from the tail to the head, printing the data in reverse order.
When running the code, the output will be:
Doubly Linked List (forward):
10 20 30 40
Doubly Linked List (reverse):
40 30 20 10This demonstrates the construction and traversal of a doubly linked list in Go. Doubly linked lists are useful when bidirectional traversal is required, such as in implementing data structures like doubly-ended queues or when efficient removal of nodes is needed.
3. Convert the Array to a Linked List
Converting an array into a linked list involves creating nodes for each element of the array and linking them together to form the list. This process requires iterating over the array and creating a new node for each element, while appropriately updating the next pointers to maintain the linkage.
Here’s an example code snippet in Go that demonstrates the conversion of an array into a singly linked list:
package main
import "fmt"
type Node struct {
data int
next *Node
}
func ArrayToLinkedList(arr []int) *Node {
var head, tail *Node
for _, val := range arr {
newNode := &Node{
data: val,
next: nil,
}
if head == nil {
head = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
}
return head
}
func PrintLinkedList(head *Node) {
currentNode := head
for currentNode != nil {
fmt.Printf("%d ", currentNode.data)
currentNode = currentNode.next
}
fmt.Println()
}
func main() {
arr := []int{10, 20, 30, 40, 50}
linkedList := ArrayToLinkedList(arr)
fmt.Println("Linked List:")
PrintLinkedList(linkedList)
}In the above code, we define a Node struct with data and next fields. The ArrayToLinkedList the function takes an array as input and converts it into a linked list. It iterates over each element of the array, creates a new node for the element, and adjusts the next pointers to link the nodes together.
The PrintLinkedList function traverses the linked list and prints the data of each node.
When running the code with the given array [10, 20, 30, 40, 50], the output will be:
Linked List:
10 20 30 40 50This demonstrates the process of converting an array into a singly linked list in Go. By creating nodes for each array element and updating the next pointers, we can construct a linked list representation of the array data.
4. Add a Node at the End & Beginning
Adding a node at the end or beginning of a linked list involves creating a new node and adjusting the pointers of the existing nodes to incorporate the new node.
To add a node at the end of a linked list, we traverse the list until we reach the last node, update its next pointer to point to the new node, and make the new node the new tail of the list.
To add a node at the beginning of a linked list, we create a new node, set its next pointer to the current head node, and update the head pointer to point to the new node.
Here’s an example code snippet in Go that demonstrates adding a node at the end and beginning of a singly linked list:
package main
import "fmt"
type Node struct {
data int
next *Node
}
func AddNodeAtEnd(head *Node, data int) *Node {
newNode := &Node{
data: data,
next: nil,
}
if head == nil {
return newNode
}
currentNode := head
for currentNode.next != nil {
currentNode = currentNode.next
}
currentNode.next = newNode
return head
}
func AddNodeAtBeginning(head *Node, data int) *Node {
newNode := &Node{
data: data,
next: head,
}
return newNode
}
func PrintLinkedList(head *Node) {
currentNode := head
for currentNode != nil {
fmt.Printf("%d ", currentNode.data)
currentNode = currentNode.next
}
fmt.Println()
}
func main() {
var head *Node
// Add nodes at the end
head = AddNodeAtEnd(head, 10)
head = AddNodeAtEnd(head, 20)
head = AddNodeAtEnd(head, 30)
fmt.Println("Linked List (after adding nodes at the end):")
PrintLinkedList(head)
// Add a node at the beginning
head = AddNodeAtBeginning(head, 5)
fmt.Println("Linked List (after adding a node at the beginning):")
PrintLinkedList(head)
}In the above code, we define a Node struct with data and next fields. The AddNodeAtEnd function adds a new node at the end of the linked list by traversing the list until the last node and updating the pointers accordingly. The AddNodeAtBeginning function adds a new node at the beginning of the list by creating a new node, setting its next pointer to the current head, and updating the head pointer.
The PrintLinkedList function is used to traverse the linked list and print the data of each node.
When running the code, the output will be:
Linked List (after adding nodes at the end):
10 20 30
Linked List (after adding a node at the beginning):
5 10 20 30This demonstrates how to add a node at the end and beginning of a singly linked list in Go. By adjusting the pointers of the existing nodes and updating the head or tail pointers if necessary, we can insert new nodes at desired positions within the list.
5. Delete Node with the Specified Value
Deleting a node with a specified value from a linked list involves traversing the list, finding the node with the desired value, and updating the pointers of the adjacent nodes to bypass the node to be deleted.
To delete a node with a specified value, we need to handle two scenarios: the node to be deleted is the head node and the node to be deleted is a non-head node.
If the node to be deleted is the head node, we update the head pointer to point to the next node, effectively removing the current head node.
If the node to be deleted is a non-head node, we traverse the list until we find the node with the specified value. Once found, we update the next pointer of the previous node to skip the node to be deleted and point directly to the node after it.
Here’s an example code snippet in Go that demonstrates deleting a node with a specified value from a singly linked list:
package main
import "fmt"
type Node struct {
data int
next *Node
}
func DeleteNode(head *Node, value int) *Node {
// Check if the head node itself holds the value
if head != nil && head.data == value {
return head.next
}
currentNode := head
var prevNode *Node
// Traverse the list to find the node with the specified value
for currentNode != nil && currentNode.data != value {
prevNode = currentNode
currentNode = currentNode.next
}
// If the node is found, update the pointers to bypass it
if currentNode != nil {
prevNode.next = currentNode.next
}
return head
}
func PrintLinkedList(head *Node) {
currentNode := head
for currentNode != nil {
fmt.Printf("%d ", currentNode.data)
currentNode = currentNode.next
}
fmt.Println()
}
func main() {
var head *Node
// Create a linked list: 10 -> 20 -> 30 -> 40 -> 50
head = &Node{data: 10}
head.next = &Node{data: 20}
head.next.next = &Node{data: 30}
head.next.next.next = &Node{data: 40}
head.next.next.next.next = &Node{data: 50}
fmt.Println("Linked List (before deletion):")
PrintLinkedList(head)
// Delete a node with value 30
head = DeleteNode(head, 30)
fmt.Println("Linked List (after deletion):")
PrintLinkedList(head)
}In the above code, we define a Node struct with data and next fields. The DeleteNode function takes the head of the linked list and the value of the node to be deleted. It traverses the list to find the node with the specified value and updates the pointers to bypass the node.
The PrintLinkedList function is used to traverse the linked list and print the data of each node.
When running the code, the output will be:
Linked List (before deletion):
10 20 30 40 50
Linked List (after deletion):
10 20 40 50This demonstrates how to delete a node with a specified value from a singly linked list in Go. By finding the node to be deleted and updating the pointers accordingly, we can remove the node from the list while maintaining the integrity of the remaining nodes.
6. Insert a Node After & Before a Node with X Data
Inserting a node after or before a specific node with a given value in a linked list involves creating a new node and adjusting the pointers of the adjacent nodes to incorporate the new node in the desired position.
To insert a node after a specific node with a given value, we traverse the list until we find the node with the desired value. Once found, we create a new node, update the pointers to link the new node appropriately, and maintain the integrity of the list.
To insert a node before a specific node with a given value, we need to consider two scenarios: the node to be inserted is the head node and the node to be inserted is a non-head node.
If the node to be inserted is the head node, we create a new node, set its next pointer to the current head, and update the head pointer to point to the new node.
If the node to be inserted is a non-head node, we traverse the list until we find the node with the desired value. Once found, we create a new node, update the pointers to link the new node appropriately, and maintain the integrity of the list.
Here’s an example code snippet in Go that demonstrates inserting a node after and before a node with a specific value in a singly linked list:
package main
import "fmt"
type Node struct {
data int
next *Node
}
func InsertNodeAfter(head *Node, value int, newData int) *Node {
currentNode := head
for currentNode != nil {
if currentNode.data == value {
newNode := &Node{
data: newData,
next: currentNode.next,
}
currentNode.next = newNode
break
}
currentNode = currentNode.next
}
return head
}
func InsertNodeBefore(head *Node, value int, newData int) *Node {
if head == nil {
return head
}
if head.data == value {
newNode := &Node{
data: newData,
next: head,
}
return newNode
}
currentNode := head
var prevNode *Node
for currentNode != nil {
if currentNode.data == value {
newNode := &Node{
data: newData,
next: currentNode,
}
prevNode.next = newNode
break
}
prevNode = currentNode
currentNode = currentNode.next
}
return head
}
func PrintLinkedList(head *Node) {
currentNode := head
for currentNode != nil {
fmt.Printf("%d ", currentNode.data)
currentNode = currentNode.next
}
fmt.Println()
}
func main() {
var head *Node
// Create a linked list: 10 -> 20 -> 30 -> 40 -> 50
head = &Node{data: 10}
head.next = &Node{data: 20}
head.next.next = &Node{data: 30}
head.next.next.next = &Node{data: 40}
head.next.next.next.next = &Node{data: 50}
fmt.Println("Linked List (before insertion):")
PrintLinkedList(head)
// Insert a node with value 25 after the node with value 20
head = InsertNodeAfter(head, 20, 25)
fmt.Println("Linked List (after insertion after node with value 20):")
PrintLinkedList(head)
// Insert a node with value 5 before the node with value 10
head = InsertNodeBefore(head, 10, 5)
fmt.Println("Linked List (after insertion before node with value 10):")
PrintLinkedList(head)
}In the above code, we define a Node struct with data and next fields. The InsertNodeAfter function inserts a new node with a specified value after a node with a given value in the linked list. It traverses the list, finds the node with the desired value, and adjusts the pointers to incorporate the new node.
The InsertNodeBefore function inserts a new node with a specified value before a node with a given value in the linked list. It handles two scenarios: the node to be inserted is the head node and the node to be inserted is a non-head node. It traverses the list, finds the node with the desired value, and adjusts the pointers to incorporate the new node.
The PrintLinkedList function is used to traverse the linked list and print the data of each node.
When running the code, the output will be:
Linked List (before insertion):
10 20 30 40 50
Linked List (after insertion after node with value 20):
10 20 25 30 40 50
Linked List (after insertion before node with value 10):
5 10 20 25 30 40 50This demonstrates how to insert a node after and before a specific node with a given value in a singly linked list in Go. By creating a new node, adjusting the pointers of the adjacent nodes, and maintaining the integrity of the list, we can insert new nodes at desired positions within the list.
7. Print All Elements by Order & Reverse Order
To print all elements of a linked list in both the original order and reverse order, we can use two different approaches: iterative and recursive.
Iterative Approach: For printing elements in the original order, we traverse the linked list starting from the head node and print the data of each node until we reach the end.
For printing elements in reverse order, we can use a stack to store the data of each node as we traverse the linked list. Once we reach the end, we pop the elements from the stack and print them, resulting in the reverse order.
Here’s an example code snippet in Go that demonstrates printing all elements of a singly linked list in both the original order and reverse order using the iterative approach:
package main
import (
"fmt"
"strings"
)
type Node struct {
data int
next *Node
}
func PrintLinkedList(head *Node) {
currentNode := head
var elements []string
for currentNode != nil {
elements = append(elements, fmt.Sprintf("%d", currentNode.data))
currentNode = currentNode.next
}
fmt.Println("Linked List (Original Order):")
fmt.Println(strings.Join(elements, " "))
fmt.Println("Linked List (Reverse Order):")
for i := len(elements) - 1; i >= 0; i-- {
fmt.Printf("%s ", elements[i])
}
fmt.Println()
}
func main() {
var head *Node
// Create a linked list: 10 -> 20 -> 30 -> 40 -> 50
head = &Node{data: 10}
head.next = &Node{data: 20}
head.next.next = &Node{data: 30}
head.next.next.next = &Node{data: 40}
head.next.next.next.next = &Node{data: 50}
PrintLinkedList(head)
}In the above code, we define a Node struct with data and next fields. The PrintLinkedList function uses an iterative approach to traverse the linked list, store the data of each node, and print it in both the original order and reverse order.
When running the code, the output will be:
Linked List (Original Order):
10 20 30 40 50
Linked List (Reverse Order):
50 40 30 20 10This demonstrates how to print all elements of a linked list in both the original order and reverse order using the iterative approach in Go.
Recursive Approach: For printing elements in the original order recursively, we can define a recursive function that takes the current node as a parameter. It prints the data of the current node and then calls itself recursively with the next node until it reaches the end.
For printing elements in reverse order recursively, we can define a recursive function that takes the current node as a parameter. It calls itself recursively with the next node and then prints the data of the current node, resulting in the reverse order.
Here’s an example code snippet in Go that demonstrates printing all elements of a singly linked list in both the original order and reverse order using the recursive approach:
package main
import (
"fmt"
"strings"
)
type Node struct {
data int
next *Node
}
func PrintLinkedList(head *Node) {
fmt.Println("Linked List (Original Order):")
printOriginalOrder(head)
fmt.Println("Linked List (Reverse Order):")
printReverseOrder(head)
fmt.Println()
}
func printOriginalOrder(node *Node) {
if node != nil {
fmt.Printf("%d ", node.data)
printOriginalOrder(node.next)
}
}
func printReverseOrder(node *Node) {
if node != nil {
printReverseOrder(node.next)
fmt.Printf("%d ", node.data)
}
}
func main() {
var head *Node
// Create a linked list: 10 -> 20 -> 30 -> 40 -> 50
head = &Node{data: 10}
head.next = &Node{data: 20}
head.next.next = &Node{data: 30}
head.next.next.next = &Node{data: 40}
head.next.next.next.next = &Node{data: 50}
PrintLinkedList(head)
}In the above code, we define a Node struct with data and next fields. The PrintLinkedList function calls two recursive helper functions, printOriginalOrder and printReverseOrder, to print the linked list in the original order and reverse order, respectively.
When running the code, the output will be the same as in the previous example:
Linked List (Original Order):
10 20 30 40 50
Linked List (Reverse Order):
50 40 30 20 10This demonstrates how to print all elements of a linked list in both the original order and reverse order using the recursive approach in Go.
