Linked Lists (Singly, Doubly, Circular)

Overview

A linked list stores data in nodes where each node contains data and one or more references to other nodes. Unlike arrays, linked lists do not require contiguous memory allocation. Each element (node) exists independently in memory and connects to other nodes through pointers or references.

Three primary variants exist:

Singly Linked Lists: Each node contains data and a reference to the next node. Traversal occurs in one direction from head to tail.

Doubly Linked Lists: Each node contains data and references to both the next and previous nodes. Traversal occurs in both directions.

Circular Linked Lists: The last node points back to the first node, creating a cycle. Both singly and doubly linked variants can be circular.

Linked lists appear throughout computer science: operating system task schedulers use them, memory allocators track free blocks with them, and graph algorithms represent adjacency lists with them. The Linux kernel extensively uses doubly linked lists for data structure management. Most high-level languages hide linked list implementations behind abstraction layers, but understanding their mechanics reveals fundamental trade-offs between memory layout and access patterns.

Ruby's built-in Array class uses contiguous memory (dynamic arrays), not linked lists. However, understanding linked lists clarifies why certain operations perform differently and when custom linked structures offer advantages.

Key Principles

A linked list consists of nodes. Each node holds two components: data and references. The data component stores the actual value. The reference component (called a pointer in languages like C, or a reference in Ruby) stores the memory address or object reference of the next node.

Node Structure

In a singly linked list, a node contains:

• Data field: holds the value
• Next field: references the next node (nil/null if no next node exists)

In a doubly linked list, a node contains:

• Data field: holds the value
• Next field: references the next node
• Previous field: references the previous node

Head and Tail

The head references the first node in the list. Without the head reference, accessing the list becomes impossible. The tail references the last node, though many implementations track only the head and traverse to find the tail when needed.

Traversal Mechanics

Traversal begins at the head. The algorithm accesses the current node's data, then follows the next reference to the subsequent node. This process continues until reaching a node where next equals nil, indicating the list's end.

In doubly linked lists, traversal works in both directions. Moving forward uses next references, while moving backward uses previous references.

Circular References

Circular linked lists eliminate the nil terminator. In a singly circular list, the last node's next field points to the head. In a doubly circular list, the last node's next points to the head, and the head's previous points to the last node.

Circular lists require careful handling to avoid infinite loops. Traversal algorithms must track visited nodes or count iterations to detect when they've completed a full cycle.

Memory Characteristics

Each node exists independently in memory at non-contiguous locations. Ruby's garbage collector automatically reclaims unreferenced nodes, but in manual memory management languages, failing to free deleted nodes causes memory leaks.

The reference fields consume additional memory beyond the data itself. A singly linked list requires one reference per node (next), while a doubly linked list requires two references per node (next and previous).

Ruby Implementation

Ruby's object system simplifies linked list implementation. Creating a Node class encapsulates data and references, while the linked list class manages the overall structure.

Singly Linked List Node

class SinglyNode
  attr_accessor :data, :next_node
  
  def initialize(data)
    @data = data
    @next_node = nil
  end
end

Singly Linked List Implementation

class SinglyLinkedList
  attr_reader :head
  
  def initialize
    @head = nil
  end
  
  # Insert at beginning - O(1)
  def prepend(data)
    new_node = SinglyNode.new(data)
    new_node.next_node = @head
    @head = new_node
  end
  
  # Insert at end - O(n)
  def append(data)
    new_node = SinglyNode.new(data)
    
    if @head.nil?
      @head = new_node
      return
    end
    
    current = @head
    current = current.next_node while current.next_node
    current.next_node = new_node
  end
  
  # Delete first occurrence - O(n)
  def delete(data)
    return if @head.nil?
    
    if @head.data == data
      @head = @head.next_node
      return
    end
    
    current = @head
    while current.next_node
      if current.next_node.data == data
        current.next_node = current.next_node.next_node
        return
      end
      current = current.next_node
    end
  end
  
  # Search - O(n)
  def find(data)
    current = @head
    while current
      return current if current.data == data
      current = current.next_node
    end
    nil
  end
  
  # Display all elements
  def to_a
    elements = []
    current = @head
    while current
      elements << current.data
      current = current.next_node
    end
    elements
  end
end

# Usage
list = SinglyLinkedList.new
list.prepend(3)
list.prepend(2)
list.append(4)
list.prepend(1)
list.to_a
# => [1, 2, 3, 4]

Doubly Linked List Node

class DoublyNode
  attr_accessor :data, :next_node, :prev_node
  
  def initialize(data)
    @data = data
    @next_node = nil
    @prev_node = nil
  end
end

Doubly Linked List Implementation

class DoublyLinkedList
  attr_reader :head, :tail
  
  def initialize
    @head = nil
    @tail = nil
  end
  
  # Insert at beginning - O(1)
  def prepend(data)
    new_node = DoublyNode.new(data)
    
    if @head.nil?
      @head = new_node
      @tail = new_node
      return
    end
    
    new_node.next_node = @head
    @head.prev_node = new_node
    @head = new_node
  end
  
  # Insert at end - O(1) with tail pointer
  def append(data)
    new_node = DoublyNode.new(data)
    
    if @tail.nil?
      @head = new_node
      @tail = new_node
      return
    end
    
    new_node.prev_node = @tail
    @tail.next_node = new_node
    @tail = new_node
  end
  
  # Delete node - O(1) with node reference
  def delete_node(node)
    return if node.nil?
    
    if node == @head
      @head = node.next_node
      @head.prev_node = nil if @head
    elsif node == @tail
      @tail = node.prev_node
      @tail.next_node = nil if @tail
    else
      node.prev_node.next_node = node.next_node
      node.next_node.prev_node = node.prev_node
    end
  end
  
  # Traverse forward
  def to_a_forward
    elements = []
    current = @head
    while current
      elements << current.data
      current = current.next_node
    end
    elements
  end
  
  # Traverse backward
  def to_a_backward
    elements = []
    current = @tail
    while current
      elements << current.data
      current = current.prev_node
    end
    elements
  end
end

# Usage
dlist = DoublyLinkedList.new
dlist.append(1)
dlist.append(2)
dlist.append(3)
dlist.to_a_forward
# => [1, 2, 3]
dlist.to_a_backward
# => [3, 2, 1]

Circular Singly Linked List

class CircularSinglyLinkedList
  attr_reader :head
  
  def initialize
    @head = nil
  end
  
  def append(data)
    new_node = SinglyNode.new(data)
    
    if @head.nil?
      @head = new_node
      new_node.next_node = @head
      return
    end
    
    current = @head
    current = current.next_node while current.next_node != @head
    current.next_node = new_node
    new_node.next_node = @head
  end
  
  # Traverse with limit to avoid infinite loop
  def to_a(max_iterations = 100)
    return [] if @head.nil?
    
    elements = []
    current = @head
    iterations = 0
    
    loop do
      elements << current.data
      current = current.next_node
      iterations += 1
      break if current == @head || iterations >= max_iterations
    end
    
    elements
  end
  
  def size
    return 0 if @head.nil?
    
    count = 1
    current = @head.next_node
    
    while current != @head
      count += 1
      current = current.next_node
    end
    
    count
  end
end

# Usage
clist = CircularSinglyLinkedList.new
clist.append(1)
clist.append(2)
clist.append(3)
clist.to_a
# => [1, 2, 3]
clist.size
# => 3

Circular Doubly Linked List

class CircularDoublyLinkedList
  attr_reader :head
  
  def initialize
    @head = nil
  end
  
  def append(data)
    new_node = DoublyNode.new(data)
    
    if @head.nil?
      @head = new_node
      new_node.next_node = new_node
      new_node.prev_node = new_node
      return
    end
    
    tail = @head.prev_node
    
    tail.next_node = new_node
    new_node.prev_node = tail
    new_node.next_node = @head
    @head.prev_node = new_node
  end
  
  def rotate_forward
    @head = @head.next_node if @head
  end
  
  def rotate_backward
    @head = @head.prev_node if @head
  end
  
  def to_a(max_iterations = 100)
    return [] if @head.nil?
    
    elements = []
    current = @head
    iterations = 0
    
    loop do
      elements << current.data
      current = current.next_node
      iterations += 1
      break if current == @head || iterations >= max_iterations
    end
    
    elements
  end
end

# Usage
cdlist = CircularDoublyLinkedList.new
cdlist.append('A')
cdlist.append('B')
cdlist.append('C')
cdlist.to_a
# => ['A', 'B', 'C']
cdlist.rotate_forward
cdlist.to_a
# => ['B', 'C', 'A']

Practical Examples

Browser History Navigation

A doubly linked list naturally models browser history. Each page becomes a node. The back button traverses to the previous node, while the forward button moves to the next node.

class BrowserHistory
  def initialize(homepage)
    @current = DoublyNode.new(homepage)
    @current.next_node = nil
    @current.prev_node = nil
  end
  
  def visit(url)
    new_page = DoublyNode.new(url)
    new_page.prev_node = @current
    @current.next_node = new_page
    @current = new_page
  end
  
  def back(steps)
    steps.times do
      return @current.data if @current.prev_node.nil?
      @current = @current.prev_node
    end
    @current.data
  end
  
  def forward(steps)
    steps.times do
      return @current.data if @current.next_node.nil?
      @current = @current.next_node
    end
    @current.data
  end
  
  def current_url
    @current.data
  end
end

history = BrowserHistory.new("homepage.com")
history.visit("page1.com")
history.visit("page2.com")
history.current_url
# => "page2.com"
history.back(1)
# => "page1.com"
history.forward(1)
# => "page2.com"

Music Playlist with Repeat

A circular linked list implements a music playlist that loops automatically. When the last song finishes, playback continues from the first song.

class MusicPlaylist
  def initialize
    @playlist = CircularSinglyLinkedList.new
    @current = nil
  end
  
  def add_song(title)
    @playlist.append(title)
    @current = @playlist.head if @current.nil?
  end
  
  def play_next
    return nil if @current.nil?
    
    song = @current.data
    @current = @current.next_node
    song
  end
  
  def current_song
    @current&.data
  end
end

playlist = MusicPlaylist.new
playlist.add_song("Song A")
playlist.add_song("Song B")
playlist.add_song("Song C")

playlist.play_next
# => "Song A"
playlist.play_next
# => "Song B"
playlist.play_next
# => "Song C"
playlist.play_next
# => "Song A" (loops back)

LRU Cache

An LRU (Least Recently Used) cache uses a doubly linked list combined with a hash map. The doubly linked list maintains access order, while the hash map provides O(1) lookups.

class LRUCache
  def initialize(capacity)
    @capacity = capacity
    @cache = {}
    @list = DoublyLinkedList.new
  end
  
  def get(key)
    return nil unless @cache.key?(key)
    
    node = @cache[key]
    # Move to front (most recently used)
    @list.delete_node(node)
    @list.prepend(node.data)
    @cache[key] = @list.head
    
    node.data[:value]
  end
  
  def put(key, value)
    if @cache.key?(key)
      node = @cache[key]
      @list.delete_node(node)
      @cache.delete(key)
    end
    
    if @cache.size >= @capacity
      # Remove least recently used (tail)
      lru_key = @list.tail.data[:key]
      @list.delete_node(@list.tail)
      @cache.delete(lru_key)
    end
    
    @list.prepend({key: key, value: value})
    @cache[key] = @list.head
  end
end

cache = LRUCache.new(2)
cache.put(1, 'A')
cache.put(2, 'B')
cache.get(1)
# => 'A'
cache.put(3, 'C') # Evicts key 2
cache.get(2)
# => nil

Implementing Undo/Redo

A doubly linked list tracks editor states for undo and redo operations. Each edit creates a new node. Moving backward implements undo, while moving forward implements redo.

class EditorHistory
  def initialize
    @history = DoublyNode.new("")
    @current = @history
  end
  
  def add_state(content)
    new_state = DoublyNode.new(content)
    new_state.prev_node = @current
    @current.next_node = new_state
    @current = new_state
  end
  
  def undo
    return @current.data if @current.prev_node.nil?
    
    @current = @current.prev_node
    @current.data
  end
  
  def redo
    return @current.data if @current.next_node.nil?
    
    @current = @current.next_node
    @current.data
  end
  
  def current_content
    @current.data
  end
end

editor = EditorHistory.new
editor.add_state("Hello")
editor.add_state("Hello World")
editor.add_state("Hello World!")
editor.current_content
# => "Hello World!"
editor.undo
# => "Hello World"
editor.undo
# => "Hello"
editor.redo
# => "Hello World"

Design Considerations

Arrays vs Linked Lists

Arrays store elements in contiguous memory locations, enabling constant-time random access through indexing. Linked lists store elements in dispersed memory locations, requiring sequential traversal for access.

Choose arrays when:

• Random access patterns dominate usage
• Memory locality matters for cache performance
• Fixed or rarely changing size
• Memory overhead per element must stay minimal

Choose linked lists when:

• Frequent insertions and deletions at arbitrary positions
• Unknown or highly variable size
• No need for random access
• Middle insertion/deletion must perform efficiently

Ruby's Array class uses dynamic arrays, not linked lists. Arrays in Ruby provide better performance for most use cases due to CPU cache optimization and lower per-element overhead.

Singly vs Doubly Linked Lists

Singly linked lists consume less memory per node (one reference instead of two) but only support forward traversal. Deleting a node requires traversing from the head to find the previous node.

Doubly linked lists enable bidirectional traversal and constant-time deletion when holding a node reference. The additional reference per node increases memory consumption.

Choose singly linked lists when:

• Memory constraints exist
• Only forward traversal occurs
• Deleting nodes with prior traversal (already have previous node)

Choose doubly linked lists when:

• Backward traversal required
• Node deletion without prior traversal
• Implementing deques or LRU caches
• Need to remove node with only node reference

Circular vs Linear Linked Lists

Circular linked lists connect the last node back to the first, creating a cycle. This structure suits round-robin scheduling, playlists, and buffer implementations.

Circular lists complicate termination detection. Traversal algorithms must track starting points or iteration counts to avoid infinite loops.

Choose circular linked lists when:

• Cyclic data access patterns
• Round-robin or rotating structures
• No natural beginning or end
• Ring buffer implementations

Linear linked lists have clear termination points (nil references), simplifying traversal logic but requiring explicit handling of boundary conditions.

When to Build Custom Implementations

Ruby's built-in collections (Array, Hash, Set) handle most use cases efficiently. Custom linked list implementations make sense when:

• Studying data structure concepts
• Implementing specific algorithms requiring linked structures (graph adjacency lists)
• Performance profiling reveals array operations as bottlenecks
• Building data structures not in standard library (skip lists, XOR linked lists)

Third-party gems rarely provide linked list implementations because Ruby's dynamic arrays perform better for typical usage patterns.

Performance Considerations

Time Complexity Analysis

* O(1) if maintaining tail pointer
** Assuming tail pointer maintained
*** Amortized O(1) with dynamic array resizing
**** O(1) with direct node reference, O(n) to find node

Space Complexity

Singly linked lists require one reference per node beyond data storage. For n elements storing integers, memory usage approximates n * (integer_size + reference_size).

Doubly linked lists require two references per node, roughly doubling the overhead compared to singly linked lists.

Arrays require no per-element overhead beyond the data itself, though dynamic arrays allocate extra capacity for growth.

In Ruby, object references typically consume 8 bytes on 64-bit systems. The overhead becomes significant for small data types. Storing 1000 integers in a doubly linked list requires approximately 16KB additional memory for references alone.

Cache Performance

Modern CPUs fetch memory in cache lines (typically 64 bytes). Arrays benefit from spatial locality—accessing array[i] often loads array[i+1] into cache automatically.

Linked lists scatter nodes throughout memory. Traversing a linked list triggers cache misses frequently, as each node likely resides in a different cache line or memory page.

Benchmarks show arrays outperform linked lists for sequential access by factors of 10x or more, primarily due to cache effects rather than algorithmic complexity.

Memory Allocation

Creating linked list nodes individually triggers multiple memory allocation operations. Each allocation incurs overhead from the memory allocator.

Arrays allocate one contiguous block, reducing allocation overhead. Dynamic array growth requires reallocation, but amortized analysis shows this remains efficient.

Ruby's garbage collector must track linked list nodes separately, potentially increasing GC pressure compared to single array objects.

Optimization Techniques

Memory pooling allocates multiple nodes in a single block, reducing allocation overhead. The application manages node reuse rather than repeatedly allocating and freeing.

class NodePool
  def initialize(size)
    @pool = Array.new(size) { SinglyNode.new(nil) }
    @available = @pool.dup
  end
  
  def allocate(data)
    node = @available.pop
    return SinglyNode.new(data) if node.nil?
    
    node.data = data
    node.next_node = nil
    node
  end
  
  def release(node)
    @available.push(node)
  end
end

Skip lists add multiple "express lane" pointers to nodes, enabling O(log n) search in linked structures. This trades memory for improved search performance.

XOR linked lists reduce doubly linked list memory overhead by XORing previous and next addresses into a single field. This technique works in languages with pointer arithmetic but not in managed languages like Ruby.

Common Pitfalls

Off-by-One Errors in Traversal

Traversing to a specific index requires careful boundary checks. A common mistake iterates one too many or too few times.

# Incorrect - misses the target index
def get_at_index_wrong(index)
  current = @head
  index.times do
    return nil if current.nil?
    current = current.next_node
  end
  current&.data
end

# Correct implementation
def get_at_index(index)
  return nil if index < 0
  
  current = @head
  index.times do
    return nil if current.nil?
    current = current.next_node
  end
  current&.data
end

Losing References During Deletion

Deleting nodes requires updating references before losing access to nodes. A common error overwrites the reference needed to complete the operation.

# Incorrect - loses reference to rest of list
def delete_wrong(data)
  if @head.data == data
    @head = @head.next_node # Correct for head
    return
  end
  
  current = @head
  while current.next_node
    if current.next_node.data == data
      # BUG: This loses everything after the deleted node
      current.next_node = nil
      return
    end
    current = current.next_node
  end
end

# Correct - maintains chain
def delete(data)
  if @head.data == data
    @head = @head.next_node
    return
  end
  
  current = @head
  while current.next_node
    if current.next_node.data == data
      current.next_node = current.next_node.next_node
      return
    end
    current = current.next_node
  end
end

Infinite Loops in Circular Lists

Circular lists require termination conditions. Forgetting to check for cycle completion causes infinite loops.

# Dangerous - infinite loop potential
def print_all_wrong
  current = @head
  while current
    puts current.data
    current = current.next_node
  end
end

# Safe - tracks starting point
def print_all
  return if @head.nil?
  
  current = @head
  loop do
    puts current.data
    current = current.next_node
    break if current == @head
  end
end

Nil Pointer Dereferences

Accessing nil nodes crashes the program. Defensive checks prevent errors, especially at list boundaries.

# Unsafe - crashes on empty list
def get_second_wrong
  @head.next_node.data
end

# Safe - checks for nil
def get_second
  return nil if @head.nil? || @head.next_node.nil?
  @head.next_node.data
end

Incorrect Doubly Linked List Updates

Doubly linked lists require updating both next and previous references. Missing either update corrupts the list structure.

# Incorrect - only updates forward links
def insert_after_wrong(node, data)
  new_node = DoublyNode.new(data)
  new_node.next_node = node.next_node
  node.next_node = new_node
  # Missing: new_node.prev_node and next's prev_node updates
end

# Correct - updates all references
def insert_after(node, data)
  new_node = DoublyNode.new(data)
  new_node.next_node = node.next_node
  new_node.prev_node = node
  
  node.next_node.prev_node = new_node if node.next_node
  node.next_node = new_node
end

Memory Leaks in Manual Languages

Ruby's garbage collector automatically frees unreferenced nodes. Languages like C and C++ require explicit memory deallocation. Forgetting to free deleted nodes leaks memory.

Comparing References Instead of Values

Searching nodes requires comparing data values, not node object identities.

# Wrong - compares node objects, not data
def contains_wrong?(data)
  current = @head
  search_node = SinglyNode.new(data)
  
  while current
    return true if current == search_node # Always false
    current = current.next_node
  end
  false
end

# Correct - compares data values
def contains?(data)
  current = @head
  while current
    return true if current.data == data
    current = current.next_node
  end
  false
end

Reference

Linked List Type Comparison

* O(1) when maintaining tail pointer

Common Operation Complexity

* With tail pointer
** Amortized

Ruby Implementation Checklist

Node Structure Reference

Singly Linked Node:

data: any value
next_node: reference to next node or nil

Doubly Linked Node:

data: any value
next_node: reference to next node or nil
prev_node: reference to previous node or nil

Use Case Selection Guide