Linked List Basics Part II

excerpt: Implement find_previous_node, add_at_beginning and add_at_end methods in a singly linked list. tags: sentinel

Find Previous Node

The dataset used in creating the linked list is the same as the previous article. Define a find_previous_node methodin the LinkedList class. It takes the target value as the parameter. The method must return the node before the given target value. If the target value is not found in the linked list it will return nil.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def find_previous_node(target)
  current = @head

  while current.link 
    if current.link.value == target
      return current
    end
  
    current = current.link
  end
end

The current pointer is initialized to the head of the linked list. The while loop keeps traversing the linked list as long as the current.link is not nil. This means we stop searching after the last node. Because the last node points to nil. The comparison check if the next node value is the same as the target, if it is it returns the current node. Before the start of the next iteration, the current pointer moves to the next node.

1
2

previous = list.find_previous_node(18)
p previous.value

This will print the value of the previous node which is 20. However, this implementation of the find_previous_node will crash if the target value is the value of the first node. Because we do not have any node before the first node. This can be demonstrated by running the code:

1
2

previous = list.find_previous_node(20)
p previous.value

Sentinel Node

The code can be simplified and made crash proof by using a sentinel node. The code for creating the linked list can be modified to include a dummy node to the beginning of the linked list.

1
2
3
4
5
6
7

# Create the linked List
last = Node.new(14, nil)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)

list = LinkedList.new(sentinel)

The sentinel node has 0 as the value for the node. The next node of the sentinel nodes is the head node. Now the implementation offind_previous_nodewill work without crashing if we pass in the head node value as the target. The sentinel node will be returned as the previous node for the head. The main advantage of sentinel node is that we don’t need to check for nilsimplifying the while loop.

Add at the Beginning

Implement the add_at_beginningmethod in the LinkedList class. It takes the node to be inserted as the parameter. The implementation of inserting a node to the beginning of the linked list is shown below:

1
2
3
4

def add_at_beginning(node)
  node.link = @head.link
  @head.link = node
end

The linked list values before inserting the new node and after inserting the node is displayed in the code.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

last = Node.new(14, nil)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)

list = LinkedList.new(sentinel)
list.traverse

node = Node.new(25, nil)
list.add_at_beginning(node)
list.traverse

The sentinel node makes adding a new node to the beginning easier to implement.

Add at the End

Implement the add_at_end method in the LinkedListclass. It takes the node to be added to the end of the linked list as the parameter. The implementation for adding a node to the end of the linked list class is shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def add_at_end(node)
  current = @head

  while current.link
    current = current.link
  end

  current.link = node
  node.link = nil
end

The method can be tested by running:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

last = Node.new(14, nil)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)

list = LinkedList.new(sentinel)
list.traverse

node = Node.new(25, nil)
list.add_at_end(node)
list.traverse

The new node with value 25 will be added to the end of the linked list.

Insert After a Node

Implement the insert method in the LinkedList class. It takes two parameters, after and node. The after node is the first parameter, we need to insert the second parameter called node after this node.

1
2
3
4

def insert(after, node)
  node.link = after.link
  after.link = node
end

The insert method can be tested by running the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

last = Node.new(14, nil)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)

list = LinkedList.new(sentinel)
list.traverse

node = Node.new(25, nil)
list.insert(second, node)
list.traverse

The output will show that node 25 was inserted after the node 18. In this example, the after node is second element in the linked list. In practice, we have to find the node where we need to insert after, this can take O(N) time.

Deleting a Node

The previous link of the node before the node to be deleted will point to the next node of the node to be deleted. Implement the delete method that takes the node to be deleted as the parameter.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def delete(node)
  current = @head
  
  while current.link.value != node.value
    current = current.link
  end
  
  current.link = node.link
  node.link = nil
end

The delete method can be tested by running the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

last = Node.new(14, nil)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)

list = LinkedList.new(sentinel)
list.traverse

list.delete(second)
list.traverse

The output shows that node 18 is deleted from the linked list.

Sorted Linked List

The items in the singly linked list can be kept in a sorted order. Sometimes this is convenient. The position for the new node to be added must be found by searching through the list and the links must be updated to insert the new node at the appropriate position. Implement the sorted_insert method in the SingleLinkedList class.

1
2
3
4
5
6
7

def sorted_insert(node)
  while @head.link && @head.link.value < node.value
    @head = @head.link
  end  

  insert(@head, node)
end

The existing insert method is reused in the sorted_insert method implementation. The method can be tested with the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

last = Node.new(14, nil)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)

list = LinkedList.new(sentinel)
list.traverse

node = Node.new(15, nil)
list.sorted_insert(node)
list.traverse

A sentinel node can be added to the end of the list to simplify the loop.

1
2
3
4
5
6
7

def sorted_insert(node)
  while @head.link.value < node.value
    @head = @head.link
  end  

  insert(@head, node)
end

The while has no check for nil value of link pointer. The code can be tested with:

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

tail = Node.new(Float::INFINITY, nil)
last = Node.new(14, tail)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)

list = LinkedList.new(sentinel)
list.traverse

node = Node.new(15, nil)
list.sorted_insert(node)
list.traverse

Circular Linked List

A circular linked list is a linked list in which the last link points back to the first item in the list. Interleaving is an effective study technique in which you switch between topics in the sequence: ABC CBA ACB. The ABC CBA and ACB represent three study sessions. Generating the sequence can organize the problems to practice. Circular linked lists let a program easily loop through a sequence of objects indefinitely. The sequence numbers for the problems for a given category can be generated by using a counter.

A - 1, 6, 7, 10, 15, 16, 19, 24, 25, 28, 33, 34, 37, 42, 43, 46, 51
B - 2, 5, 9, 11, 14, 18, 20, 23, 27, 29, 32, 36, 38, 41, 45, 47, 50
C - 3, 4, 8, 12, 13, 17, 21, 22, 26, 30, 31, 35, 39, 40, 44, 48, 49

The problems can be sequenced based on the generated numbers.

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

require_relative 'node'

class CicularLinkedList
  def initialize(head)
    @counter = 0
    @head = head
  end
  
  # Iterate Over the List and 
  # Generate the Interleaving Sequence
  def traverse
    current = @head
    @counter = 1
    
    while @counter != 251
      p "#{@counter}, #{current.value} "
      current = current.link
      @counter += 1
    end
  end
end

Create the circular linked List

ninth = Node.new('B', nil)
eight = Node.new('C', ninth)
seventh = Node.new('A', eight)
sixth = Node.new('A', seventh)
fifth = Node.new('B', sixth)
fourth = Node.new('C', fifth)
third = Node.new('C', fourth)
second = Node.new('B', third)
head = Node.new('A', second)
ninth.link = head # make it circular

list = CicularLinkedList.new(head)
list.traverse

This generates an interleaving sequence for three topics up to 250.