Constructing a Singly-Linked-List (Ruby)
A brief and quick implementation with Ruby.
What is a Linked List?
A linked list is a data structure in which each element is a node and it contains two types of information.
1) It’s data
2) a reference/pointer to another node within a list.
To dive into more specifics, you can have a singly-linked-list where it would typically have the attributes:
value (data)
next (pointer)
And a doubly-linked-list in which it would have:
value (data)
next (pointer)
previous (pointer)
Creating a Singly-Linked-List in Ruby
In order to create a linked list from scratch you need to construct two classes.
1) Node Class
This should be able to create a node object that possesses the attributes: Value and Next.
2) LinkedList Class
This should be able to create a LinkedList object which will consist of Node Class objects and also possess the variable/attribute: Head (which is the starting point of our list)
Let’s talk about the LinkedList class and its methods
1). initialize →
This method creates a list object by creating a head node with a value and a next pointer being nil
2). append_to_tail →
This method iterates through the whole list to find the last node, by looping through the nodes until the next one is nil. When we reach the current node where its’ next node is nil, we replace nil with a new Node object.
3). delete_value →
This method starts by checking if the value to delete is the head itself. If it is, we just update @head to equal it’s next node. If the value we want to delete is not in the head, we will loop through the nodes until the next node is the value to delete. Once that Node is found set up the current Node’s pointer to equal the next next Node, or simply delete the matching node, if there is no next next Node.
4). print_list →
This method pushes each node into an array so that you can show the list in array form.
Putting it all together and Testing it out:
In the above we can see that our linked list is capable of deleting and adding onto itself!
Feel free to see the code yourself on my github!
Github Repo: https://github.com/alanbanks229/linked_lists/blob/master/singly_linked_list.rb