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 :)
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
ok sure
Good job brother:)
glad you like it :) <3
Please votes me and follow