Interview prep with linked lists
I'm prepping for interviews, and it seems like one topic I'm going to be coming across is linked lists. I found a good gist of implementing a linked list. Linked lists are a data structure that have nodes that contain values. There is a null value before the head of the node, and one after the last node in the list. Each node has a connection to the values around it, but unlike in the case of arrays there is no index value with linked lists, so only push and pop operations are available. Furthermore, finding specific values require traversing the whole linked list.
Implementing a linked list requires two classes--one for the nodes and one for adding a value to the list. In this blog post, i'm only going to discuss the mechanism behind the push operation of the linked list, since the other methods have somewhat similar code behind them.
So the first step in creating a linked list is to create the nodes.
The nodes are a class, with attr_accessors value and next node. So, the value and next_node can change In order for a node to exist, it must have a value, so it is initialized with a value. It also must have the possibility for a node after it, to keep track of its position (unlike the diagram, these nodes only know about the node after them).
Next, we need to create the list.
The first thing to do is initialize the list. It's initialized with a head. If the head is nil, the first value is the value initialized with.
If the list doesn't have any values, then the added value will be the head value. Otherwise, you need to walk down the list using the next method until you reach the bottom of the list. At that point you will exit the while loop and the value at the end of the list is the value you are looking to add.
And that's it! Stay tuned for more interview news.