Exploring linked lists

I’ve been playing with new data structures lately in preparation for interviews. Up to this point, I’ve been parsing, traversing, and CRUDing the DOM, arrays, and hashes — all lovely arrangements — but there other data structures that deserve due consideration because of performance issues, i.e., the efficiency by which one can execute CRUD actions on a data structure.

Currently, Im studying how to manipulate linked lists. A linked list is a simple data structure consisting of a sequence of nodes. Each node only knows about its subsequent neighbor. You might ask, why would I want to choose a linked list if its memory of itself is so shortsighted? The answer lies in performance.

IMG_8093

Compared with an array, it is much more efficient to insert or delete an element in a linked list because it can be done without reorganizing the entire data structure. You simply delete the link to the element you want to delete, or insert an element and shift the preceding node’s pointer to it (as well as point the new node to the previous node’s old neighbor).

On the flipside, arrays are much more efficient at selecting elements. If know the index of an element in an array you can immediately access it. To access a node in a linked list, you must traverse the list from the first position until you find it. In mathematical terms, we say that the access time for an array is O(1) and access time for a linked list is O(n).

Alas, in Ruby, there are no linked lists. So as a code challenge, I decided to build my own using Ruby classes and methods (partial credit to Katie Hoffman, an amazing, talented colleague who helped me whiteboard this problem the other day).

Having built Conway’s Game of Life in Ruby, I had a good idea of where to start from. Like a cell class that has knowledge of itself and its neighbors, I knew I needed a node class with similar intelligence.

Similarly, like a world class in Game of Life knows its two-dimensional geometry, I implemented a LinkedList class that knows itself as a straight line with a root position.

Next, within the LinkedList class, I built methods to add, find, and delete a node from the list.

To add an element to the end of the list, I built a method that sets the current position to the root of the list and takes one argument, the content of a new node. Knowing that the neighbor of the last cell is always nil, I built a loop to traverse the list UNTIL current.neighbor.nil? evaluates to true. In the meantime, with each loop I increment the position of current to the position of its neighbor. Once current.neighbor.nil? evaluates to true, the method sets the last node’s neighbor to the new_node created at the start of the method.

Likewise, to find a node in a list, I incremented the current node via an until loop. The delete method was trickier. That’s where my visual aid came in handy so I could keep track of both the current and previous positions in the list with each iteration. With deletion, its essential to store the previous node, because to delete its neighbor, you don’t actually delete its neighbor; instead, you delete the reference to its neighbor. To do that, you point previous to its neighbor’s neighbor, or the neighbor of the final current node in the loop.

Tricky stuff. Without a visual aide I would be totally lost.

P.S. Happy Graduation to all my Flatiron colleagues!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s