Linked Lists in Go

What is a Linked List?
Types of Linked Lists
Implementing a Singly Linked List
Implementing a Doubly Linked List
Common Operations
Performance Analysis
Use Cases
Linked Lists vs. Arrays and Slices
Best Practices

Linked lists are fundamental data structures that provide dynamic, flexible storage for collections of data. Unlike arrays and slices, which store elements in contiguous memory locations, linked lists use nodes that reference each other, allowing for efficient insertions and deletions. In this comprehensive guide, we'll explore linked lists in Go, from basic concepts to advanced implementations and practical applications.

What is a Linked List?

A linked list is a linear data structure consisting of a sequence of elements, called nodes. Each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists don't require contiguous memory allocation, making them more flexible for dynamic data storage.

The key components of a linked list are:

Node: The basic unit of a linked list, containing data and a reference to the next node
Head: A reference to the first node in the list
Tail (optional): A reference to the last node in the list

Linked lists offer several advantages:

Dynamic size (can grow and shrink during execution)
Efficient insertions and deletions (when you have a reference to the position)
No need for contiguous memory allocation
Efficient implementation of other data structures like stacks, queues, and graphs

However, they also have some disadvantages:

No random access (must traverse from the beginning to reach a specific position)
Extra memory overhead for storing references
Poor cache locality compared to arrays
More complex implementation than arrays and slices

Types of Linked Lists

There are several types of linked lists, each with its own characteristics and use cases:

Singly Linked List

In a singly linked list, each node contains data and a reference to the next node in the sequence. The last node points to nil (or null), indicating the end of the list.

type Node struct {
    Data int
    Next *Node
}

type SinglyLinkedList struct {
    Head *Node
    Size int
}

Singly linked lists are simple and memory-efficient, but they only allow traversal in one direction (from head to tail).

Doubly Linked List

In a doubly linked list, each node contains data and references to both the next and previous nodes. This allows for bidirectional traversal.

type Node struct {
    Data int
    Next *Node
    Prev *Node
}

type DoublyLinkedList struct {
    Head *Node
    Tail *Node
    Size int
}

Doubly linked lists are more versatile than singly linked lists, as they allow traversal in both directions and make certain operations (like deletion) more efficient. However, they require more memory due to the additional reference in each node.

Circular Linked List

A circular linked list is a variation where the last node points back to the first node, creating a circle. This can be implemented with either singly or doubly linked lists.

// Circular Singly Linked List
type CircularSinglyLinkedList struct {
    Head *Node
    Size int
}

// The last node's Next points to Head instead of nil

// Circular Doubly Linked List
type CircularDoublyLinkedList struct {
    Head *Node
    Size int
}

// The last node's Next points to Head, and Head's Prev points to the last node

Circular linked lists are useful for applications where you need to cycle through elements repeatedly, such as round-robin scheduling.

Implementing a Singly Linked List

Let's implement a basic singly linked list in Go, with methods for common operations:

package main

import (
    "fmt"
)

// Node represents a node in a singly linked list
type Node struct {
    Data interface{}
    Next *Node
}

// SinglyLinkedList represents a singly linked list
type SinglyLinkedList struct {
    Head *Node
    Tail *Node
    Size int
}

// NewSinglyLinkedList creates a new empty singly linked list
func NewSinglyLinkedList() *SinglyLinkedList {
    return &SinglyLinkedList{}
}

// IsEmpty checks if the list is empty
func (list *SinglyLinkedList) IsEmpty() bool {
    return list.Size == 0
}

// Append adds a new node with the given data to the end of the list
func (list *SinglyLinkedList) Append(data interface{}) {
    newNode := &Node{Data: data, Next: nil}
    
    if list.IsEmpty() {
        list.Head = newNode
        list.Tail = newNode
    } else {
        list.Tail.Next = newNode
        list.Tail = newNode
    }
    
    list.Size++
}

// Prepend adds a new node with the given data to the beginning of the list
func (list *SinglyLinkedList) Prepend(data interface{}) {
    newNode := &Node{Data: data, Next: list.Head}
    
    if list.IsEmpty() {
        list.Tail = newNode
    }
    
    list.Head = newNode
    list.Size++
}

// InsertAt inserts a new node with the given data at the specified position
func (list *SinglyLinkedList) InsertAt(data interface{}, position int) error {
    if position < 0 || position > list.Size {
        return fmt.Errorf("position out of bounds")
    }
    
    if position == 0 {
        list.Prepend(data)
        return nil
    }
    
    if position == list.Size {
        list.Append(data)
        return nil
    }
    
    current := list.Head
    for i := 0; i < position-1; i++ {
        current = current.Next
    }
    
    newNode := &Node{Data: data, Next: current.Next}
    current.Next = newNode
    list.Size++
    
    return nil
}

// RemoveAt removes the node at the specified position
func (list *SinglyLinkedList) RemoveAt(position int) (interface{}, error) {
    if list.IsEmpty() {
        return nil, fmt.Errorf("list is empty")
    }
    
    if position < 0 || position >= list.Size {
        return nil, fmt.Errorf("position out of bounds")
    }
    
    var data interface{}
    
    if position == 0 {
        data = list.Head.Data
        list.Head = list.Head.Next
        
        if list.Size == 1 {
            list.Tail = nil
        }
    } else {
        current := list.Head
        for i := 0; i < position-1; i++ {
            current = current.Next
        }
        
        data = current.Next.Data
        
        if current.Next == list.Tail {
            list.Tail = current
        }
        
        current.Next = current.Next.Next
    }
    
    list.Size--
    return data, nil
}

// Get returns the data at the specified position
func (list *SinglyLinkedList) Get(position int) (interface{}, error) {
    if list.IsEmpty() {
        return nil, fmt.Errorf("list is empty")
    }
    
    if position < 0 || position >= list.Size {
        return nil, fmt.Errorf("position out of bounds")
    }
    
    current := list.Head
    for i := 0; i < position; i++ {
        current = current.Next
    }
    
    return current.Data, nil
}

// IndexOf returns the position of the first occurrence of the specified data
func (list *SinglyLinkedList) IndexOf(data interface{}) int {
    if list.IsEmpty() {
        return -1
    }
    
    current := list.Head
    position := 0
    
    for current != nil {
        if current.Data == data {
            return position
        }
        current = current.Next
        position++
    }
    
    return -1
}

// Contains checks if the list contains the specified data
func (list *SinglyLinkedList) Contains(data interface{}) bool {
    return list.IndexOf(data) != -1
}

// Clear removes all nodes from the list
func (list *SinglyLinkedList) Clear() {
    list.Head = nil
    list.Tail = nil
    list.Size = 0
}

// ToSlice converts the list to a slice
func (list *SinglyLinkedList) ToSlice() []interface{} {
    result := make([]interface{}, list.Size)
    
    current := list.Head
    for i := 0; i < list.Size; i++ {
        result[i] = current.Data
        current = current.Next
    }
    
    return result
}

// String returns a string representation of the list
func (list *SinglyLinkedList) String() string {
    if list.IsEmpty() {
        return "[]"
    }
    
    result := "["
    
    current := list.Head
    for current != nil {
        result += fmt.Sprintf("%v", current.Data)
        
        if current.Next != nil {
            result += " -> "
        }
        
        current = current.Next
    }
    
    result += "]"
    return result
}

func main() {
    list := NewSinglyLinkedList()
    
    // Append elements
    list.Append(1)
    list.Append(2)
    list.Append(3)
    
    fmt.Println("List after appending 1, 2, 3:", list)
    
    // Prepend an element
    list.Prepend(0)
    fmt.Println("List after prepending 0:", list)
    
    // Insert at position
    list.InsertAt(1.5, 2)
    fmt.Println("List after inserting 1.5 at position 2:", list)
    
    // Remove at position
    removed, _ := list.RemoveAt(2)
    fmt.Println("Removed:", removed)
    fmt.Println("List after removing element at position 2:", list)
    
    // Get element at position
    element, _ := list.Get(2)
    fmt.Println("Element at position 2:", element)
    
    // Check if list contains an element
    fmt.Println("List contains 3:", list.Contains(3))
    fmt.Println("List contains 5:", list.Contains(5))
    
    // Convert to slice
    slice := list.ToSlice()
    fmt.Println("List as slice:", slice)
    
    // Clear the list
    list.Clear()
    fmt.Println("List after clearing:", list)
}

This implementation provides a basic singly linked list with common operations. It uses the interface{} type for data, making it generic and able to store any type of data.

Implementing a Doubly Linked List

Now, let's implement a doubly linked list, which allows for bidirectional traversal:

package main

import (
    "fmt"
)

// Node represents a node in a doubly linked list
type Node struct {
    Data interface{}
    Next *Node
    Prev *Node
}

// DoublyLinkedList represents a doubly linked list
type DoublyLinkedList struct {
    Head *Node
    Tail *Node
    Size int
}

// NewDoublyLinkedList creates a new empty doubly linked list
func NewDoublyLinkedList() *DoublyLinkedList {
    return &DoublyLinkedList{}
}

// IsEmpty checks if the list is empty
func (list *DoublyLinkedList) IsEmpty() bool {
    return list.Size == 0
}

// Append adds a new node with the given data to the end of the list
func (list *DoublyLinkedList) Append(data interface{}) {
    newNode := &Node{Data: data, Next: nil, Prev: list.Tail}
    
    if list.IsEmpty() {
        list.Head = newNode
    } else {
        list.Tail.Next = newNode
    }
    
    list.Tail = newNode
    list.Size++
}

// Prepend adds a new node with the given data to the beginning of the list
func (list *DoublyLinkedList) Prepend(data interface{}) {
    newNode := &Node{Data: data, Next: list.Head, Prev: nil}
    
    if list.IsEmpty() {
        list.Tail = newNode
    } else {
        list.Head.Prev = newNode
    }
    
    list.Head = newNode
    list.Size++
}

// InsertAt inserts a new node with the given data at the specified position
func (list *DoublyLinkedList) InsertAt(data interface{}, position int) error {
    if position < 0 || position > list.Size {
        return fmt.Errorf("position out of bounds")
    }
    
    if position == 0 {
        list.Prepend(data)
        return nil
    }
    
    if position == list.Size {
        list.Append(data)
        return nil
    }
    
    // Determine whether to start from head or tail based on position
    var current *Node
    if position <= list.Size/2 {
        // Start from head
        current = list.Head
        for i := 0; i < position; i++ {
            current = current.Next
        }
    } else {
        // Start from tail
        current = list.Tail
        for i := list.Size - 1; i > position; i-- {
            current = current.Prev
        }
    }
    
    newNode := &Node{Data: data, Next: current, Prev: current.Prev}
    current.Prev.Next = newNode
    current.Prev = newNode
    list.Size++
    
    return nil
}

// RemoveAt removes the node at the specified position
func (list *DoublyLinkedList) RemoveAt(position int) (interface{}, error) {
    if list.IsEmpty() {
        return nil, fmt.Errorf("list is empty")
    }
    
    if position < 0 || position >= list.Size {
        return nil, fmt.Errorf("position out of bounds")
    }
    
    var current *Node
    
    if position == 0 {
        // Remove head
        current = list.Head
        list.Head = current.Next
        
        if list.Head == nil {
            // List becomes empty
            list.Tail = nil
        } else {
            list.Head.Prev = nil
        }
    } else if position == list.Size-1 {
        // Remove tail
        current = list.Tail
        list.Tail = current.Prev
        list.Tail.Next = nil
    } else {
        // Determine whether to start from head or tail based on position
        if position <= list.Size/2 {
            // Start from head
            current = list.Head
            for i := 0; i < position; i++ {
                current = current.Next
            }
        } else {
            // Start from tail
            current = list.Tail
            for i := list.Size - 1; i > position; i-- {
                current = current.Prev
            }
        }
        
        current.Prev.Next = current.Next
        current.Next.Prev = current.Prev
    }
    
    list.Size--
    return current.Data, nil
}

// Get returns the data at the specified position
func (list *DoublyLinkedList) Get(position int) (interface{}, error) {
    if list.IsEmpty() {
        return nil, fmt.Errorf("list is empty")
    }
    
    if position < 0 || position >= list.Size {
        return nil, fmt.Errorf("position out of bounds")
    }
    
    var current *Node
    
    // Determine whether to start from head or tail based on position
    if position <= list.Size/2 {
        // Start from head
        current = list.Head
        for i := 0; i < position; i++ {
            current = current.Next
        }
    } else {
        // Start from tail
        current = list.Tail
        for i := list.Size - 1; i > position; i-- {
            current = current.Prev
        }
    }
    
    return current.Data, nil
}

// IndexOf returns the position of the first occurrence of the specified data
func (list *DoublyLinkedList) IndexOf(data interface{}) int {
    if list.IsEmpty() {
        return -1
    }
    
    current := list.Head
    position := 0
    
    for current != nil {
        if current.Data == data {
            return position
        }
        current = current.Next
        position++
    }
    
    return -1
}

// Contains checks if the list contains the specified data
func (list *DoublyLinkedList) Contains(data interface{}) bool {
    return list.IndexOf(data) != -1
}

// Clear removes all nodes from the list
func (list *DoublyLinkedList) Clear() {
    list.Head = nil
    list.Tail = nil
    list.Size = 0
}

// ToSlice converts the list to a slice
func (list *DoublyLinkedList) ToSlice() []interface{} {
    result := make([]interface{}, list.Size)
    
    current := list.Head
    for i := 0; i < list.Size; i++ {
        result[i] = current.Data
        current = current.Next
    }
    
    return result
}

// ToSliceReverse converts the list to a slice in reverse order
func (list *DoublyLinkedList) ToSliceReverse() []interface{} {
    result := make([]interface{}, list.Size)
    
    current := list.Tail
    for i := 0; i < list.Size; i++ {
        result[i] = current.Data
        current = current.Prev
    }
    
    return result
}

// String returns a string representation of the list
func (list *DoublyLinkedList) String() string {
    if list.IsEmpty() {
        return "[]"
    }
    
    result := "["
    
    current := list.Head
    for current != nil {
        result += fmt.Sprintf("%v", current.Data)
        
        if current.Next != nil {
            result += " <-> "
        }
        
        current = current.Next
    }
    
    result += "]"
    return result
}

func main() {
    list := NewDoublyLinkedList()
    
    // Append elements
    list.Append(1)
    list.Append(2)
    list.Append(3)
    
    fmt.Println("List after appending 1, 2, 3:", list)
    
    // Prepend an element
    list.Prepend(0)
    fmt.Println("List after prepending 0:", list)
    
    // Insert at position
    list.InsertAt(1.5, 2)
    fmt.Println("List after inserting 1.5 at position 2:", list)
    
    // Remove at position
    removed, _ := list.RemoveAt(2)
    fmt.Println("Removed:", removed)
    fmt.Println("List after removing element at position 2:", list)
    
    // Get element at position
    element, _ := list.Get(2)
    fmt.Println("Element at position 2:", element)
    
    // Check if list contains an element
    fmt.Println("List contains 3:", list.Contains(3))
    fmt.Println("List contains 5:", list.Contains(5))
    
    // Convert to slice
    slice := list.ToSlice()
    fmt.Println("List as slice:", slice)
    
    // Convert to slice in reverse order
    sliceReverse := list.ToSliceReverse()
    fmt.Println("List as slice (reverse):", sliceReverse)
    
    // Clear the list
    list.Clear()
    fmt.Println("List after clearing:", list)
}

The doubly linked list implementation is similar to the singly linked list but includes bidirectional links and optimizations for operations that can benefit from traversing from the tail.

Common Operations

Let's explore some common operations on linked lists and their implementations:

Traversal

Traversing a linked list involves visiting each node in sequence:

// Traverse a singly linked list
func (list *SinglyLinkedList) Traverse(callback func(data interface{})) {
    current := list.Head
    for current != nil {
        callback(current.Data)
        current = current.Next
    }
}

// Traverse a doubly linked list in reverse
func (list *DoublyLinkedList) TraverseReverse(callback func(data interface{})) {
    current := list.Tail
    for current != nil {
        callback(current.Data)
        current = current.Prev
    }
}

Searching

Searching for a specific value in a linked list:

// Search for a value in a linked list
func (list *SinglyLinkedList) Search(data interface{}) *Node {
    current := list.Head
    for current != nil {
        if current.Data == data {
            return current
        }
        current = current.Next
    }
    return nil
}

Reversing

Reversing a linked list is a common interview question and a useful operation:

// Reverse a singly linked list
func (list *SinglyLinkedList) Reverse() {
    if list.IsEmpty() || list.Size == 1 {
        return
    }
    
    var prev, next *Node
    current := list.Head
    
    // Swap head and tail
    list.Tail = list.Head
    
    for current != nil {
        next = current.Next
        current.Next = prev
        prev = current
        current = next
    }
    
    list.Head = prev
}

// Reverse a doubly linked list
func (list *DoublyLinkedList) Reverse() {
    if list.IsEmpty() || list.Size == 1 {
        return
    }
    
    current := list.Head
    
    // Swap head and tail
    list.Head, list.Tail = list.Tail, list.Head
    
    for current != nil {
        // Swap Next and Prev pointers
        current.Next, current.Prev = current.Prev, current.Next
        
        // Move to the next node (which is now current.Prev due to the swap)
        current = current.Prev
    }
}

Detecting Cycles

Detecting cycles in a linked list using Floyd's Cycle-Finding Algorithm (also known as the "tortoise and hare" algorithm):

// Detect a cycle in a singly linked list
func (list *SinglyLinkedList) HasCycle() bool {
    if list.IsEmpty() || list.Size == 1 {
        return false
    }
    
    slow := list.Head
    fast := list.Head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next          // Move one step
        fast = fast.Next.Next     // Move two steps
        
        if slow == fast {
            return true  // Cycle detected
        }
    }
    
    return false  // No cycle
}

Finding the Middle Node

Finding the middle node of a linked list using the "slow and fast pointers" technique:

// Find the middle node of a singly linked list
func (list *SinglyLinkedList) FindMiddle() *Node {
    if list.IsEmpty() {
        return nil
    }
    
    slow := list.Head
    fast := list.Head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next          // Move one step
        fast = fast.Next.Next     // Move two steps
    }
    
    return slow  // Slow pointer will be at the middle when fast reaches the end
}

Merging Two Sorted Lists

Merging two sorted linked lists into a single sorted list:

// Merge two sorted singly linked lists
func MergeSortedLists(list1, list2 *SinglyLinkedList) *SinglyLinkedList {
    result := NewSinglyLinkedList()
    
    current1 := list1.Head
    current2 := list2.Head
    
    for current1 != nil && current2 != nil {
        if current1.Data.(int) <= current2.Data.(int) {
            result.Append(current1.Data)
            current1 = current1.Next
        } else {
            result.Append(current2.Data)
            current2 = current2.Next
        }
    }
    
    // Append remaining elements from list1
    for current1 != nil {
        result.Append(current1.Data)
        current1 = current1.Next
    }
    
    // Append remaining elements from list2
    for current2 != nil {
        result.Append(current2.Data)
        current2 = current2.Next
    }
    
    return result
}

Performance Analysis

Understanding the performance characteristics of linked lists is crucial for choosing the right data structure for your application.

Time Complexity

Operation	Singly Linked List	Doubly Linked List	Explanation
Access by Index	O(n)	O(n)	Must traverse from the beginning (or end for doubly linked lists) to reach the desired position
Insert at Beginning	O(1)	O(1)	Only need to update head pointer and a few references
Insert at End	O(1) with tail pointer, O(n) without	O(1)	With a tail pointer, insertion at the end is constant time
Insert at Middle	O(n)	O(n)	Must traverse to find the insertion point
Delete at Beginning	O(1)	O(1)	Only need to update head pointer
Delete at End	O(n)	O(1)	For singly linked lists, must traverse to find the node before the tail; for doubly linked lists, can use the tail's prev pointer
Delete at Middle	O(n)	O(n)	Must traverse to find the deletion point
Search	O(n)	O(n)	Must traverse to find the element

Space Complexity

The space complexity of linked lists is O(n), where n is the number of elements. However, linked lists have additional overhead compared to arrays:

Singly linked lists: Each node requires extra space for the next pointer
Doubly linked lists: Each node requires extra space for both next and prev pointers

Memory Considerations

Linked lists have several memory-related characteristics to consider:

Dynamic allocation: Nodes are allocated individually, which can lead to fragmentation
Pointer overhead: Each node requires additional memory for pointers
Cache locality: Nodes may be scattered in memory, leading to poor cache performance compared to arrays
Garbage collection: In languages with garbage collection (like Go), removing nodes from a linked list doesn't immediately free memory

Use Cases

Linked lists are well-suited for certain applications:

When to Use Linked Lists

Frequent insertions and deletions: When you need to frequently insert or delete elements, especially at the beginning or middle of the collection
Unknown size: When the number of elements is not known in advance and may change significantly
Implementation of other data structures: As a building block for stacks, queues, and certain types of graphs
Memory allocation concerns: When memory is fragmented and contiguous allocation (as required by arrays) is not possible
Circular buffers: When implementing circular data structures, such as a circular buffer or round-robin scheduler

Real-World Applications

Browser history: Implementing forward and backward navigation (doubly linked list)
Music playlists: Managing songs with previous and next functionality
Undo functionality: Maintaining a history of operations that can be undone
Memory management: Managing free blocks of memory in operating systems
Hash tables with chaining: Using linked lists to handle collisions in hash tables
Polynomial representation: Representing polynomials with linked lists where each node contains a coefficient and exponent

Linked Lists vs. Arrays and Slices

Choosing between linked lists and arrays/slices depends on your specific requirements:

Feature	Linked Lists	Arrays/Slices
Memory allocation	Dynamic, non-contiguous	Static (arrays) or dynamic but contiguous (slices)
Random access	O(n)	O(1)
Insertion/deletion at beginning	O(1)	O(n)
Insertion/deletion at end	O(1) with tail pointer	O(1) amortized for slices
Insertion/deletion in middle	O(n) to find position, O(1) to insert/delete	O(n)
Memory overhead	Higher (extra pointers)	Lower
Cache performance	Poor (scattered memory)	Good (contiguous memory)
Implementation complexity	Higher	Lower

When to Choose Arrays/Slices Over Linked Lists

When you need fast random access
When the size is known and relatively stable
When memory usage is a concern
When cache performance is important
When you need simple, straightforward code

When to Choose Linked Lists Over Arrays/Slices

When you need frequent insertions and deletions, especially at the beginning or middle
When the size is unknown or highly variable
When you need to implement certain data structures (e.g., certain types of queues)
When memory fragmentation is a concern

Best Practices

Here are some best practices to follow when working with linked lists in Go:

Use Appropriate List Type

Choose the right type of linked list for your needs:

Use singly linked lists when you only need to traverse in one direction and memory efficiency is important
Use doubly linked lists when you need bidirectional traversal or efficient operations at both ends
Use circular linked lists when you need to cycle through elements repeatedly

Maintain Both Head and Tail Pointers

Keeping a reference to both the head and tail of the list allows for O(1) operations at both ends.

Handle Edge Cases

Always handle edge cases carefully:

Empty lists
Single-element lists
Operations at the beginning or end of the list
Invalid indices or positions

Use Generic Types

In Go, you can use interface{} to create generic linked lists, but be aware of type assertions when retrieving data.

Consider Thread Safety

If your linked list will be accessed by multiple goroutines, implement proper synchronization using mutexes or channels.

Implement Standard Interfaces

Implement standard Go interfaces like fmt.Stringer for better integration with the language.

Use Existing Libraries

Consider using existing libraries like Gods (Go Data Structures) instead of implementing linked lists from scratch for production code.

Conclusion

Linked lists are versatile data structures that excel in scenarios requiring frequent insertions and deletions. While they have some disadvantages compared to arrays and slices, they remain an important tool in a programmer's toolkit. By understanding their characteristics, operations, and best practices, you can effectively use linked lists in your Go programs.

In the next section, we'll explore stacks and queues, which are often implemented using linked lists as their underlying data structure.

Go Data Structures & Algorithms