Ruby Linked Lists
Last updated
Was this helpful?
Last updated
Was this helpful?
For this exercise, we will implement a simple version of a singly linked list. But first, let's learn what a linked list is, and why you should care.
A linked list a data structure, used for fast and memory efficient insertions and deletions. Unlike arrays, which are single objects, linked lists contain multiple 'node' objects that are linked together via references.
Linked lists can either be singly or doubly linked. We'll focus on singly linked lists for now.
If linked lists are multiple objects linked together, ideally we need a couple different objects.
A LinkedList object, which holds all of the objects in the list
A Node object, which contains the data for the element, as well as a reference to the next Node in the list.
In lower level languages, arrays are allocatd in blocks. Therefore, arrays are static in size and can only hold a specific data type. Linked lists store data in the heap, meaning that the data can be stored in an unorganized manner. Since each node points to the next one, it's still possible to maintain the list structure.
The best way to understand how linked lists work is to make one! Let's do so in Ruby. Here's the process.
Start by creating a Node Class. We will have attributes to represent the data (let's call this @data) and the reference to the next Node (let's call this @next).
Create a LinkedList class. This class will have two values, @head and @tail. These will represent the beginning and end of the list. Initialize both to nil for now. We have an empty list!
Now for incorporating the two classes together. Create a method on the LinkedList class called insert_front. The challenge is to add an item to the beginning of the list. This can be done by creating a new Node, then doing the following:
Store the value of @head into a temp variable
Set the @head to the newly created Node. Note that currently, its next reference is nil.
Think about what we would need to do if we're adding a new item to the beginning of a linked list. Consult the diagram (hint: we'll have to do something with the new node's next reference)
Lastly, handle the special case of the @tail. @tail should always be the last Node in the linked list.
Create another method on the LinkedList or Node called to_s in order to print the list to the console.
Use while loops to iterate over a linked lists. While loops are better than for loops here because Linked Lists don't have a length property. Instead of iterating for a certain number of times, we simply iterate while our current pointer is not nil.
Create a a local variable called current that starts off pointing to the list's root node. Inside the loop you can do two things:
access the value of the current node at current.data
point the current variable to the next item with current = current.next
BONUS: Create an insert_end method to add nodes to the end of the list.
SUPER BONUS: Create a more versatile insert method to add a node anywhere in the linked list, providing an index for the new item.