Doubly Linked list

In previous article, we learned to create singly linked list, every node in singly linked list has in it the information of next node. but it does not have information about previous node..
Which makes traversal go from head to tail direction and not backwards.

e.g We can not start from tail and go back to head.. that kind of exploration of nodes is not possible with singly linked list

Doubly list

doubly linked list is a data structure, which consists upon nodes linked together in a way that every node contains reference to its both neighbor nodes (e.g previous and next), which makes it possible to traverse the list in both ways, backwards and forward

Lets start by creating a Node

class Node
    attr_accessor :val, :next, :prev
  
    def initialize(prev_node, val, next_node)
        @prev = prev_node
        @val  = val
        @next = next_node
    end
end

Once we have the node, we can start changing our singly list's code to convert into doubly list ..
notice that doubly list allows us to add few more methods

• We can add a new node at the tip of chain
• We can add a new node at the tail of chain
• We can add a new add at any random local of the chain
• We can traverse the chain from head to tail, and from tail back to head
• we can go forward and backward at any node

Here is the code

require_relative 'node'

class DoublyList
    def initialize(val)
        @head = Node.new(nil, val, nil)
        puts @head.val
    end
    
    def add_to_tail(val)
        current = @head
        while current.next != nil
          current = current.next
        end
        current.next = Node.new(current, val, nil)
    end
    def add_to_tip(val)
        current           = @head
        new_node          = Node.new(current, val, current.next)
        current.next.prev = new_node
        current.next = new_node
    end
    def return_list
        elements = []
        current = @head
        while current.next != nil
          elements << current
          current = current.next
        end
        elements << current
    end
  
    def display_list
        puts "Going from Head to Tail"
        current = @head
        while current.next != nil
            puts current.val
            current = current.next
        end
        puts current.val

        puts "Going from Tail to Head"
        while current.prev != nil
            puts current.val
            current = current.prev
        end
        puts current.val
    end
end

Notice that I did not created method to add in the middle of the list. but you can implement the method to do so,
we can add a data member called :id that is similar to blockchain's height variable.
but you can add a floating number, so when you need to add a node in the middle of chain. you can add it
based upon height .. and change the height of new node to 2.1 which can be added between 2 and 3 height nodes

Now lets see how we coded main.rb program to use this list

require_relative 'doublylist'

_data = {username: "bilalhaider", age: "27", salary: 0.00, reward: 50}
puts "Genesis Node Data: #{_data}"

_mylist = DoublyList.new(_data)

while $entry.to_i != 5
    print "1 - Insert new at Tail\n2 - Insert new data at Tip\n3 - Display List\n4 - Return List\n5 - Exit\n Your Choice: "
    $entry = gets.chomp 

    if $entry.to_i == 1
        print "Insert your Name: "
        _username = gets.chomp
        
        print "Insert your age: "
        _age      = gets.chomp
        
        print "Insert your salary: "
        _salary   = gets.chomp
        _data = {username: _username, age: _age, salary: _salary, reward: 50}
        puts "Data Inserted at Tail: #{_data}"

        _mylist.add_to_tail(_data)
    elsif $entry.to_i == 2
        print "Insert your Name: "
        _username = gets.chomp
        
        print "Insert your age: "
        _age      = gets.chomp
        
        print "Insert your salary: "
        _salary   = gets.chomp
        _data = {username: _username, age: _age, salary: _salary, reward: 50}
        puts "Data Inserted at Tip: #{_data}"

        _mylist.add_to_tip(_data)
    elsif $entry.to_i == 3
        puts _mylist.display_list
    elsif $entry.to_i == 4
        puts _mylist.return_list
    elsif $entry.to_i == 5 
        puts "Exiting .... "
    else 
        puts "Invalid choice "
    end
end

Finally when we execute our program, we have 5 options to choose from ..
Notice that our chain is fully intact..

Its difficult to explain all the methods one by one.

Couple of notes

• When adding a node to the tip of chain, first we need to get reference of @head node.

  • Create a new node, and update references so that its connected to the chain
  • Update the head's next node to new_node, new_node's previous to head's node, new_node's next to @head's next
  • and finally the next's node's previous to new_node's ..
  • That way node is successfully added to the chain, and its connected perfectly

• When adding a node to tail is less tricky, you traverse the list until tail is reached. then create a new node

  • New node's previous should be set to last node , and last node's next should be set to new node
  • Finally new node's next should be nil , as there is no next node ..

This data structure can come handy when building a blockchain which allows to insert nodes at any height :)