Ruby Programming Tutorial - Lesson 31 - Doubly Linked list

in #ruby7 years ago

doubly-linked-list.gif

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

Screenshot from 2018-03-21 08-55-39.png

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

Screenshot from 2018-03-21 09-33-30.png
Screenshot from 2018-03-21 09-33-50.png

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..

Screenshot from 2018-03-21 09-38-54.png

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 :)

Sort:  

When the RPG maker boom was strong in Youtube, i was very interested in Ruby on Rails, since it was the language the program used, and while i never ultimately pursued that interest, your videos definitely make it so understanding the basics of this language seem more accessible for beginners like me. Thank you :)

Hopefully you will become an awesome ruby programmer in future :) I will continue publishing more material ..

Wow! This is great content! You have received a free upvote from the Minnows Freedom Project for being a good Steemian and posting original content. To learn more about us or to support us, please visit @minnows-freedom. You can also find us on Discord. Stay cool, create good content and have a nice day!

plz upvote comment & follow

@bilal-haider You are a programmer!
can you detect someone who has hacked someone's steemit. because there is my friend who was hit by his steemit hack.

I can't, my own account @bilalhaider was hacked :D :p

Ok, thank you
but if you get the answer to my question please inform me. ok

Good job brother:)

glad you like it :) <3

Please votes me and follow