Doubly Linked List Basics

excerpt: The topics covered are traverse and add nodes to a doubly linked list. tags: doubly-linked-list-traversal

In a doubly linked list, the nodes have links that point to both the next and previous nodes in the list. Sentinels for head and tail can make it easier to manipulate the list from either end. For example, you can add and remove nodes from either end in O(1) time.

Doubly Linked List

The node for a doubly linked list has previous and next links.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Node
  attr_accessor :nxt
  attr_reader :val
  
  def initialize(val, previous, nxt)
    @val = val
    @previous = previous
    @nxt = nxt
  end
  
end

The class for double linked list has the traverse method.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

require_relative 'node'

class DoubleLinkedList

  def traverse(node)
    while node
      p node.val
      node = node.nxt
    end
  end  
  
end

sentinel = Node.new(0, nil, nil)

first = Node.new(1, sentinel, nil)
sentinel.nxt = first

second = Node.new(2, first, nil)
first.nxt = second

list = DoubleLinkedList.new
list.traverse(sentinel)

The traverse method will print: 0,1,2.

Add a Node

The basic operations for manipulating doubly linked lists are similar to singly linked list. Except that we must do some extra work to manage the previous links.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Node
  attr_accessor :nxt
  attr_reader :val
  attr_accessor :previous
  
  def initialize(val, previous, nxt)
    @val = val
    @previous = previous
    @nxt = nxt
  end
  
end

The node class now has getters and setters for previous and nxt links. Implement insert method to insert a node after a given node in the DoubleLinkedList class.

1
2
3
4
5
6
7
8
9

 def insert(after, node)
   # update the next links
   node.nxt = after.nxt
   after.nxt = node
   
   # update previous links
   node.previous = after
   node.nxt.previous = node  
 end

Any any point in time, we have to keep track of which links have been updated. The code:

1

after.nxt.previous = node

will not work. The reason is the link after.nxt has already been updated to point to the new node. The fix is to use node.nxt.