Linked lists are not an all purpose tool. In fact, the first time you play with a linked list will probably be to help develop your conceptual understanding of computer science theories. But you already, undoubtedly know a little bit about their functionality through other ruby data structures.
A linked list is a data structure used to sort and organize data. A linked list is similar to an array: it stores data at a particular value. However, it differs as each element in a linked list (called a node), has knowledge of the node that comes after it. You can think of a node object like this:
A node object contains the node itself as well as a pointer to the object that follows it (The link in linked list!). It therefore takes up more memory than an array. Here is what the node object looks like in ruby:
1 2 3 4 5 6 7 8 9
When the node is initialized, it has data as well as a pointer to the next node (this can be set to nil, if the proceeding node does not exist or is itself a nil value).
Now lets get in the console and play!
1 2 3 4 5
We have two nodes, but both node_1’s pointer and node_2’s pointer’s are nil. In order for them to be connected to create the beginning of a linked list we need to set node_1’s pointer to node_2 as such:
1 2 3 4
Now we can see that the object node_1 has knowledge of the node_2 object. This is the beginning of a linked list. You will commonly see the next method, used in place of a pointer. However, because next is a key word in ruby, we can’t initialize it in the node object–yet keep calm, we can alias the method as so:
1 2 3 4 5 6 7 8 9 10
This will allow us to call the next method through the node object itself. Therefore if I want to call the node_2 object. I can do it as such:
In a singly linked list there is a head, which represents the beginning of a linked list. To create this relationship, we will need a new object, our Linked List object, composed of our node objects.
1 2 3 4 5 6 7
Here we have our very own linked list, we can begin to add methods to–for example, we can create a method to store data at the beginning of our linked list:
lets say we have the following linked list that looked like this:
To insert the string “the abc’s” into the 0 index, we would need to first create a new node object with the data “the abc’s” and set our new node object’s pointer to a, the current head of our linked list.
This would give us:
That said, the method should look like this:
1 2 3 4 5
This adds a node object at the beginning of our linked list by first creating a new node object, and then setting it’s pointer to the current head object (the first object in the list).
Now, what if we wanted to insert a value in the center of our linked list?
Say we want our linked list to look as such:
To insert “psych” into the third index, we would have to move to the second index to get b, create a new node, “psych!”, set b’s pointer to “psych” and then set the pointer of our new node to c.
Our new code would look like this!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Please note, that this method will not work if you want to insert a new note at the beginning of the linked list, for this your user should be directed to the unshift method.
Now, onto the bigger questions: Why would we want to use a linked list instead of an Array?
Well, lets compare using a chart:
And there you have it. The hows and whys of linked lists. Good luck on your next and all future interviews!