Implement a Linked List in Ruby

What is linked list? Linked list is a fundamental data structure that can store and manage data. Linked list, as it sounds like, is a linear collection of elements. Linked list stores data in a specific way: it’s linked by nodes. Each node is composed of two sections: the data section and a pointer section. Obviously, the data section is the place to store data, and the pointer section will point to the next node.Press enter or click to view image in full sizea simple nodeWe can have plenty of nodes storing all kinds of data like integer, float, hash table, even class instance!Alright, after we are familiar with nodes, let’s link them together to build a linked list!Press enter or click to view image in full sizea linked listAbove is the format of a simple singly-linked list. Every linked list is linked by nodes. And it must have a starting point, which points to the head node in the beginning. With each following node points to the next node, we’ve built a linked list! That’s easy! Why do we need linked list? We’ve been work with array for thousands of times. Array has pretty good performance in storing and managing data. Why we still need a linked list? Well, keep reading!When we create an array, the memory will give specific space for it. This space of memory is fixed when an array is initialized. This characteristic limits array’s performance in managing data.For example, if we want to insert a new element to an array, it will take O(n) time to process(n is the length of this array). The same running time applies to delete, merge, etc.Press enter or click to view image in full sizean example of inserting an element to the front of an arrayLinked list has much better performance in managing data. Due to it’s dynamically stored in memory, linked list can be reorganized, merged, inserted easily with O(1) running time! How to implement linked list in Ruby? In order to implement a linked list, we need to create the node class first.Here’s the code I wrote to implement the node class:Remember that node has two sections: data and next. When we build a node with a pass-in data, the node will be initialized with:@data = data @next = nil 🥳 🥳 🥳 Now, we’re ready to build a linked list 🥳 🥳 🥳Oh, wait 🤔Before starting to code, let’s do some design first: what are the functionality that linked list needs?Well, if we treat our linked list as an array, then we might want to do the following tasks: Adding new data at the front/end of the linked listRemove the element from the front/end of the linked listCount the size of a linked listPrint a linked listClear the whole linked list 👩‍💻 Cool! Let’s code 👩‍💻class LinkedList #is_empty?: return true if the linked list is empty def is_empty? if @head == nil return true else return false end end #push: given a data, add a new node in the end def push(data) if self.is_empty? @head = Node.new(data) else current_node = @head new_node = Node.new(data) while current_node.next != nil current_node = current_node.next end current_node.next = new_node end end #unshift: add a new node in the front def unshift(data) if self.is_empty? @head = Node.new(data) else curr_head = Node.new(data) curr_head.next = @head @head = curr_head end end #pop: remove the last node and return it def pop if self.is_empty? return "This list is currently empty" else current_node = @head while current_node.next.next != nil current_node = current_node.next end last_node = current_node.next current_node.next = nil end last_node end #shift: remove the first node and return it def shift if self.is_empty? return "This list is currently empty" else curr_head = @head new_head = @head.next @head.next = nil @head = new_head end curr_head end #size: return the length of linked list def size if self.is_empty? count = 0 else count = 1 current_node = @head while current_node.next != nil current_node = current_node.next count += 1 end end count end #pretty_print: print the current linked list as an array def pretty_print array = [] current_node = @head if self.is_empty? return array else while current_node.next != nil array << current_node.data current_node = current_node.next end array << current_node.data end array end #clear: clear the whole linked list def clear @head = nil endendAbove is my implementation of a linked list. You can play with it by creating several nodes and lists, see what happens when you apply methods on them!Check out the code on GitHub! Let’s run some tests! Let’s create a new linked list instance first:list = LinkedList.new=> #<LinkedList:0x00007fcd4c2fc6e8>Looks good! Our list is empty now, let’s add some items to it:> list.push(1)=> #<Node:0x00007fcd4d013cf0 @data=1, @next=nil>> list.push(2)=> #<Node:0x00007fcd4c99c340 @data=2, @next=nil>> list.push(3)=> #<Node:0x00007fcd4c9ac718 @data=3, @next=nil>> list.push(4)=> #<Node:0x00007fcd4c1157f8 @data=4, @next=nil>> list=> #<LinkedList:0x00007fcd4c2fc6e8 @head=#<Node:0x00007fcd4d013cf0 @data=1, @next=#<Node:0x00007fcd4c99c340 @data=2, @next=#<Node:0x00007fcd4c9ac718 @data=3, @next=#<Node:0x00007fcd4c1157f8 @data=4, @next=nil>>>>>We can also add an item in the beginning:> list.unshift(0)=> #<Node:0x00007fcd4c2857c8 @data=0, @next= #<Node:0x00007fcd4d013cf0 @data=1, @next= #<Node:0x00007fcd4c99c340 @data=2, @next= #<Node:0x00007fcd4c9ac718 @data=3, @next=#<Node:0x00007fcd4c1157f8 @data=4, @next=nil>>>>>> list=> #<LinkedList:0x00007fcd4c2fc6e8 @head=#<Node:0x00007fcd4c2857c8 @data=0, @next=#<Node:0x00007fcd4d013cf0 @data=1, @next=#<Node:0x00007fcd4c99c340 @data=2, @next=#<Node:0x00007fcd4c9ac718 @data=3, @next=#<Node:0x00007fcd4c1157f8 @data=4, @next=nil>>>>>>It’s too complicated to understand what’s inside our list. We can utilize #pretty_print method to take a look:> list.pretty_print=> [0, 1, 2, 3, 4]> list.size=> 5Now it’s more clear!You can try other methods to better understanding the linked list 🤓