So to keep the trend of my previous blogs, this week we’ll be going over linked lists. More specifically singly linked lists and a few common associated functions! With the name of “singly”, you can take a guess that there could also be something called a doubly linked list, but that won’t be our topic today. Take a look below to get a visual idea of what it is.
The picture could be explained as nodes that points too or references another object. The head simply means where the linked lists begins, and a tail (not shown) just means where it ends or when the last cell points to null. Also notice how each box is segmented into two cells, with the data portion, and a “next” portion. Let’s say the letters within the picture (A, B, C, D) represents some “data” and that’s the role of the first cell. The second cells role is to “point” at another node.
What and why are linked lists useful?
Well, often times, arrays are simple data structures that can are compared to linked lists because they’re easy to understand. Arrays have very big advantages when used in ways that it was designed for and that goes the same way for linked lists. In a general high level explanation, arrays are very good for direct element access whereas linked lists are useful for when you have to do a lot of modifications to the list itself. Both time and space complexity are used as a “benchmark”, take a look below.
- Adding an element => linked lists operation cost is O(1) whereas an array requires memory reallocation O(n). All you need for a linked list is to find a space in memory, point the original tail to the new element and voila!
- Removing an element => linked lists only requires redirecting the pointer which is an O(1) operation. In an array (if not first or last element) you still have to reallocate memory space for the array change.
- Access to a known element => this is where arrays shine with an O(1) operation! Linked lists on the other hand, you’ll have to traverse starting from the head to whichever element you need access to, O(n).
These were very basic comparisons and of course, there are more deeper technical examples between the two, but I believe these distinctions are important to know.
Okay let’s build one out in Javascript!
First things first, let’s make two classes, one for nodes and one for the list itself. The flow is that we’ll make nodes, then create a list, and start attaching them within the list class so we have access to class functions as well.
Notice that we when we create a new node, the next value doesn’t point to anything yet, that’ll change later on! For now let’s add some class functions in the linkedList class to be able to “do things”.
The tricky thing that took me a bit of time to conceptualize was the “this.head” value. Best way for me to put it is that when you traverse a linked list, whatever value you’re currently on is the “head”. For example, in the display() function, we start at node = this.head, and while loop our way through “jumping” from head to head as on line 31. We do this and know that we’ll reach the end or tail when node.next = null. Okay, now let’s do some more functions for insertions!
This one’s a doozy, but I highly recommend you read through and really try to digest the code. Inserting at the beginning or end is relatively easy, create a new node, set the previous head as the new nodes.next, then set the head as the newly created node. When inserting at the end, traverse through until you find the tail, and set the newly created node as the tail.next.
Let’s break down the insert at a specific point and index helper function
The helper function is highly recommended because you can use it later on for a specific deletion or removal, but the main purpose is to get index of the node that you wish to access. When inserting at a specific point, you need to know what comes before and after in order to put the node in between. I left comments in the code to help you decipher the process, but I’m hoping this blog helped you tackle the linked list data structure! Take a look below on how to actually create and implement it so you can play around with the data structure.
