SearchāŒ˜ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Go

Doubly Linked List Operations

Explore how to implement and manage doubly linked lists in Go, focusing on traversal, insertion, and deletion operations. Understand the role of dual pointers in efficient navigation and maintenance of list integrity while practicing essential coding techniques for these core data structures.

We'll cover the following...

By now, you are introduced to the structure of a doubly linked list and how each node stores two pointers: one to the next node and one to the previous node.

You have already implemented the core linked list operations for singly linked lists, including traversal, insertion, and deletion. The overall ideas behind these operations remain the same in a doubly linked list. However, because each node now stores an additional prev pointer, some extra pointer updates are required to keep the structure consistent.

Letā€™s revisit the three core operations and understand how they work in a doubly linked list, and what changes they entail compared to singly linked lists.

Traversal in a doubly linked list

Traversal in a doubly linked list is primarily the same as traversal in a singly linked list. The process begins at the head node and repeatedly follows the next pointer until the end of the list is reached.

As in a singly linked list, a temporary pointer, such as current, is used during traversal so that the head pointer remains unchanged. At each step, the data stored in the current node can be processed, such as printing the value with fmt.Print or comparing it with a target.

The main difference is that a doubly linked list also supports backward traversal, because each node stores a pointer to the previous node.

In summary:

  • Forward traversal works exactly like it does in a singly linked list by following the next pointers.

  • Backward traversal becomes possible by following the prev pointers.

Backward traversal

To traverse backward in a doubly linked list:

  1. First move to the last node in the list.

  2. Process the data stored in the current node.

  3. Move to the previous node using current = current.prev.

  4. Repeat this process until current becomes nil, which indicates that the beginning of the list has been passed.

Letā€™s look at the following interactive visualizer for the doubly linked list traversal.

Go implementation of traversal in a doubly linked list

The following code shows a simple implementation of a doubly linked list and its traversal methods in Go.

Go (1.24.2)
package main
import "fmt"
type ListNode struct {
	data int
	prev *ListNode // Points to the previous node
	next *ListNode // Points to the next node
}
type DoublyLinkedList struct {
	head *ListNode // Points to the first node
}
func (list *DoublyLinkedList) traverseForward() {
	current := list.head // Start from the head
	for current != nil {
		fmt.Printf("%d -> ", current.data) // Process current node
		current = current.next             // Move to the next node
	}
	fmt.Println("nil") // End of list
}
func (list *DoublyLinkedList) traverseBackward() {
	current := list.head // Start from the head
	if current == nil {
		return
	}
	// First move to the last node
	for current.next != nil {
		current = current.next
	}
	for current != nil {
		fmt.Printf("%d -> ", current.data) // Process current node
		current = current.prev             // Move to the previous node
	}
	fmt.Println("nil") // Beginning of list reached
}
func main() {
	// Create a doubly linked list manually: 10 <-> 20 <-> 30
	sampleList := &DoublyLinkedList{}
	first := &ListNode{data: 10}
	second := &ListNode{data: 20}
	third := &ListNode{data: 30}
	sampleList.head = first
	first.next = second
	second.prev = first
	second.next = third
	third.prev = second
	// Show the difference between forward and backward traversal
	fmt.Print("Forward traversal: ")
	sampleList.traverseForward()
	fmt.Print("\nBackward traversal: ")
	sampleList.traverseBackward()
}
Doubly linked list traversal

  • Time complexity: Traversal takes O(n)O(n) time because each node is visited once.

  • Space complexity: Traversal uses O(1)O(1) ...