Linked Lists

A friend of mine gifted me the book, Cracking the Coding Interview by Gayle Laakmann, awhile back for my birthday. It’s probably one of the most famous books for studying for interviews. However, if you don’t have CS background like me, the problems can be a bit challenging as the book is not meant to be for studying the fundamentals (well.. granted it’s meant to be challenging for anyone studying). So I turned to Udemy and started on Learning Data Structures by Eric Traub. I really like the way he explains things and his pace so far. It covers a few important data structures, linked lists, binary search trees, and hash tables. Here is a summary of this morning’s learning on the first topic, linked lists. Detailed code summary can be found here: https://repl.it/IZ09/16

A linked list is a data structure that contains data elements, “nodes,” in a linear fashion. These nodes (objects) can be singly linked or doubly linked. Singly linked nodes have reference to the nodes next to them (can only go one way) and doubly linked nodes have access to nodes next to them as well as previous nodes (can go both ways). Linked lists also have two “pointers,” one that points at the very first node in the list, namely the “head node” and the other pointing at the last node, the “tail node.” We only have direct access to these pointers and data can only be added/removed from these nodes. This means that any nodes that reside somewhere in between the pointers have to be searched through, one by one, starting from either the head or the tail (no random access or adding a node next to, say the third node without going from the head or tail ). Our goal is then to create two constructor functions that 1) creates a linked list and 2) creates a new node. We also need a few methods to be added to the prototype of the linked list constructor function that do the following: add/remove from the head/tail & search the list for the value of interest.

1) LinkedList Constructor Function

Write a constructor function for creating a new linked list. Set “this.head” & “this.tail” to null since we are starting with an empty list with no nodes in them.

2) Node Constructor Function

Write a constructor function for creating a new node. This takes in three parameters, value, next (reference to next node), and prev (reference to previous node).

3) addToHead method

This method is added to the prototype of the linked list constructor function and takes in a value parameter. It creates a new instance of the Node constructor that takes in the value passed in as its “value”, the current head of the list (if any), this.head, as the “next” node, and null as the “prev” node (since the new node is the new head, no node comes before it).
If current “this.head” exists, meaning that the list is not empty, set its prev node to the new node, making it the new head.
Else, if the list is empty, set the new node as this.tail since it will be the first and only node in the list.
Finally, set the new node as the new “this.head” regardless the list is empty or not (purpose of this method).

Additionally, removeFromHead, addToTail/removefromTail (same as head methods but in reverse), and search method can be written. The search function takes in the value to be searched as its parameter and a loop is used to search for the matching value in the list (start from head or tail, your choice, and conditional loop). To start, save the head or tail node in a variable, say “currentNode,” and update it to the next/prev node as you move along the list.

The course gives a challenge problem at the end to find the index/position of the search value.

Hackerrank has good practice problems under Data Structures > Linked Lists. Linked lists seem pretty straightforward and simple to use. When are linked lists useful in real life over the other data structures? I’m assuming it has to do with memory and space, Big O, covered next in the course.

Happy learning!

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s