When I started to become a programmer, I always wondered what’s the big deal about data structures. It kind of seemed like some abstract mumbo jumbo that you only need to know for job interviews. As I’ve been exposed to more software development, my horizons have been expanded to the importance of data structures. For example, the DOM and web scraping are a binary search tree. Google Maps is built on a graph. Schedulers are binary heaps.
As it turns out, data comes in all shapes and sizes and complexities. And often, the vanilla JS tools like objects, arrays, loops, conditionals, etc. are not enough to software code tools to handle the data complexity. By definition, data structures are collections of values, the relationships among them and the functions or operations that can be applied to them. As you spend more time as a software developer, you will inevitably need to use a variety of data structures in your code.
In this blog posts, I’m going to start with the first data structure of a singly linked list and will go into other data structures in other blog posts. For some reason, I absolutely love these computer science topics. So we know what an array is (they are indexed in order that it can be quickly referenced by a specific index). In an array, we know where all of the data values are at. Unlike an array, we can’t say give me the 4th index item in a linked list. In a linked list, it’s easier to expand our data values. If we want to access a value in one of the node objects of a linked list, we have to start at the head and work our way to our target value. At its core, a linked list is just an object nested within an object. It has a length property but it is not indexed like an array; it consists of plain ‘ole objects called nodes and each node has a value and a pointer to another node or null starting from a head and ending in a tail. So if you know how to insert into, remove from, and update properties/values in objects, then you know how to navigate a linked list.
The use case for singly linked lists include insertion and deletion performance (including fast insertion and removal of data at Big O constant time-complexity
O(1)). Access and search Big O performance is slower as an time-complexity
O(n). Comparatively, time-complexity for arrays have
O(1) access performance but an
O(n) for search, insertion and deletion. In terms of Big O space-complexity, linked lists actually take more space than arrays because we have to store both the pointers and the data values. We use linked lists by implementing a class applying a constructor method and instantiate an instance via the new keyword. The head and tail properties are objects initially set to null. When we add data to the linked list, the head and tail will point to the objects aka nodes we insert. Head will point to a node at the start of the chain of nodes and tail will point to the node at the end.
If we want to create new nodes, we can use ES6 classes and the constructor method.
Unlike arrays, we have to create
pop() instance methods to the LinkedList class because it’s not sitting on the global scope. For push() which inserts a newNode at the end, we’ll create a variable newNode as an instance on the Node class. If there is no head property on the list, we’ll set head to the new node and we’ll set
this.head. If a head property exists, we’ll set
this.tail.next to the newNode and then
this.tail to the newNode. Finally, we’ll increase the length by one and return this. For
pop() which removes a node from the end of the linked list, we’ll need to remove the tail by reassigning the tail but this means we’ll have to traverse all the way back to the beginning.
pop(), we’ll want to create a variable called current and assign it the value of
this.head. Next, we’ll want to create a variable called newTail and assign it the current object and while loop through
current.next so that newTail is assigned to current and current is moved forward one to
current.next (till it can’t move forward anymore).
Doubly linked lists are almost identical to singly linked lists but every node has another pointed (in addition to the next pointer) that points to the previous node. It’s more flexible than singly linked lists but takes more memory.