Doubly linked list in Go

Components of a doubly linked list

In a doubly linked list, a node is a fundamental element that constitutes the structure of the list. A doubly linked list is a linear data structure where each element is stored in a node, and each node contains three main components:

Data: The data component of a node holds the value or information associated with that particular node. This value can be of any data type, such as integers, strings, or complex objects.

Previous pointer: The previous pointer, also known as a reference or link, points to the previous node in the sequence. It establishes a bidirectionalBidirectional refers to the ability to move or operate in two directions. connection between nodes in the list, allowing navigation both forwards and backward.

Next pointer: The next pointer points to the next node in the sequence. It continues to establish the unidirectional flow from one node to the next, while the previous pointer enables bidirectional traversal.

An initial node is marked by the head pointer within the doubly linked list. To traverse the linked list in both directions, we initiate the process at the head pointer for forward traversal and at the tail pointer for backward traversal, and we end upon reaching a null value in either direction.

Code

Here's an example of how you can implement a doubly linked list in Go:

package main
import (
	"fmt"
)
// Define the Node structure for doubly linked list
type Node struct {
	data  int
	prev  *Node
	next  *Node
}
// Define the DoublyLinkedList structure
type DoublyLinkedList struct {
	head *Node
	tail *Node
}
// Initialize a new empty doubly linked list
func NewDoublyLinkedList() *DoublyLinkedList {
	return &DoublyLinkedList{}
}
// Add a new node at the end of the doubly linked list
func (dll *DoublyLinkedList) Append(data int) {
	newNode := &Node{data: data, prev: nil, next: nil}
	if dll.head == nil {
		dll.head = newNode
		dll.tail = newNode
		return
	}
	newNode.prev = dll.tail
	dll.tail.next = newNode
	dll.tail = newNode
}
// Display the doubly linked list in forward direction
func (dll *DoublyLinkedList) DisplayForward() {
	current := dll.head
	for current != nil {
		fmt.Printf("%d -> ", current.data)
		current = current.next
	}
	fmt.Println("nil")
}
// Display the doubly linked list in backward direction
func (dll *DoublyLinkedList) DisplayBackward() {
	current := dll.tail
	for current != nil {
		fmt.Printf("%d -> ", current.data)
		current = current.prev
	}
	fmt.Println("nil")
}
func main() {
	// Create a new doubly linked list
	dll := NewDoublyLinkedList()
	// Add elements to the doubly linked list
	dll.Append(10)
	dll.Append(20)
	dll.Append(30)
	// Display the doubly linked list in forward direction
	fmt.Println("Doubly Linked List (Forward):")
	dll.DisplayForward()
	// Display the doubly linked list in backward direction
	fmt.Println("Doubly Linked List (Backward):")
	dll.DisplayBackward()
}

This code defines a simple doubly linked list in Go. It includes the following features:

Lines 8–12: The Node struct represents each node in the linked list. Each node contains an integer value (data), a pointer to the next node (next) and a pointer to the previous node (prev).
Lines 15–18: The DoublyLinkedList struct represents the doubly linked list itself.
- Line 16: A pointer to the first node in the list (the head node).
- Line 17: A pointer to the last node in the list (the tail node).
Lines 21–23: The NewDoublyLinkedList function initializes and returns a new empty doubly linked list.
Lines 26–38: The Append method adds a new node with the given data to the end of the doubly linked list.
- Line 27: It first creates a new node with the provided data and initializes its prev and next pointers to nil.
- Lines 29–33: If the list is empty (head is nil), both head and tail are set to the new node.
- Lines 35–37: If the list is not empty, the next pointer of the current tail node is set to the new node, and the prev pointer of the new node is set to the current tail. Then, the tail is updated to the new node.
Lines 41–48: The DisplayForward method traverses and displays the doubly linked list in the forward direction.
- Lines 42–47: It starts from the head node and iterates through the list, printing each node's data followed by an arrow (->) until the end of the list is reached.
Lines 51–58: The DisplayBackward method traverses and displays the doubly linked list in the backward direction.
- Lines 52–57: It starts from the tail node and iterates through the list in reverse, printing each node's data followed by an arrow (->) until the beginning of the list is reached.

This code demonstrates the basic implementation of a doubly linked list, which allows bidirectional traversal of elements. It initializes, appends, and displays the elements of the doubly linked list, showcasing the ability to traverse the list both forwards and backward.

Time and space complexity

The provided doubly linked list implementation offers efficient insertion at the end of the list, achieved in constant time complexity $O(1)$ . Traversing the list forwards and backward for display operations requires linear time complexity $O(n)$ , visiting each node exactly once.

The space complexity is determined by the storage required for nodes, resulting in $O(n)$ due to a proportional increase in memory usage with the number of nodes. Additional variables used for traversal contribute negligible constant space $O(1)$ to the overall complexity.

Free Resources