So, Tell Me About Linked Lists
Having recently graduated from a coding bootcamp, I’ve been deep into studying data structures and algorithms to better my fundamental knowledge. Linked lists are a relatively simple data structure, but is the basis for more complex data structures moving forward. This article will be discussing linked lists — their strengths, weaknesses, and how to implement them.
Data structures are, put simply, ways to organize, and hold data efficiently
What Are Data Structures?
Data structures are, put simply, ways to organize, and hold data efficiently. These allow us to hold information so that we can access them for later — searching for a specific item, or sorting them to have a certain order or even managing large datasets. JavaScript has data structures that you’re likely very familiar with — arrays and objects. These are primitive data structures that are native to the language. Non-primitive data structures are data structures that are defined by the programmer. Examples include stacks, queues, trees, graphs, and hash tables.
What Are Linked Lists?
A linked list is a linear data structure that holds elements in sequential order. Sound familiar? They’re similar to arrays but they’re not quite the same. Arrays are zero-indexed, meaning each index is mapped to a value, and the first element of the array starts at an index of 0. You can easily pull elements from the array, so long as you know the index.
On the other hand, a linked list consists of nodes that point to other nodes. Each node only knows itself and the next node. As a linear data structure, items are arranged in order. You could think about it as a train — each rail car is connected to the next rail car, and so on. Linked lists are not indexed, so you can’t access the 5th element directly. You’d have to start at the beginning, go to the next, and go to the next until you find the 5th element. The first node is called the head, and the last node is called the tail. There are various types of linked lists — singly linked list, doubly linked list, and circular linked list. For the sake of this article, I’ll be focusing on the singly linked list.
Accessing elements throughout the array is easier, but that comes at a cost.
Why Use Linked Lists Over Arrays?
You may be wondering — but why use this if I can access elements directly with arrays? This is true! Accessing elements throughout the array is easier, but that comes at a cost.
Arrays are indexed — so whenever you need to remove an element from the beginning or middle, all the following indices need to be shifted. This is also true if you need to insert an element — all following elements need to be reindexed. When inserting or removing elements from a linked list, you don’t need to reindex — all it cares about is the node it points to.
Implementing a Singly Linked List
There are various types of linked lists — singly, doubly, and circular. Singly linked lists are a type of linked list where each node has a value and a pointer to the next node (null if it’s the tail node). Doubly linked lists, on the other hand, have an additional pointer to the previous node. Circular linked lists are where the tail node points back to the head node.
Note: If you‘re a visual learner, VisuAlgo is a great place to play around and see the data structure go through changes.
If you want to skip ahead for the complete code: checkout this GitHub gist.
Creating a Node
Let’s start by building a node to use. It’ll have a value and a next pointer, which will indicate its subsequent neighbor.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}Create SinglyLinkedList Class
We’ll begin by building a class called SinglyLinkedList and give it a basis for the head, tail, and the length of the list.
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}Adding Node to the End
For adding a node to the end, we’ll check if there is a head already declared on the list. If not, set the head and tail to be the newly created node. If there already is a head property, set the next property on the tail to the new node, and the tail property to be the new node. We’ll increment length by 1.
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++;
return this;
}Removing Node at the End
For removing a node at the end, we must first check if there are nodes in the list. If there are nodes, then we have to loop through the list until we reach the tail. We’ll set the next property of the second to last node to be null, set the tail property to that node, decrement the length by 1, and return the value of the removed node.
pop() {
if (!this.head) return undefined;
var current = this.head
var newTail = current
while (current.next) {
newTail = current
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}Removing Node from the Beginning
To remove the node from the beginning, we check if there are nodes in the list. We’ll store the current head property in a variable, and set the head to be the current head’s next node. Decrement the length by 1 and return the value of the node removed.
shift() {
if (!this.head) return undefined
var oldHead = this.head;
this.head = oldHead.next;
this.length--
if (this.length===0) {
this.head = null;
this.tail = null;
}
return oldHead
}Add Node to the Beginning
To add a node to the beginning, we first create the node and check if there is a head property on the list. If so, set the next property of the newly created node to the current head, set head to the new node, and increment the length.
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++
return this
}Get Node Based on Position
To access a node based on its position in the list, we’ll first check if the index is a valid index. After, we’ll loop through the list, while keeping a counter variable. Once the counter variable matches the index, we’ll return the found node
get(idx) {
if (idx < 0 || idx >= this.length) return null
var counter = 0;
var current = this.head
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}Change Value of Node
To change a node’s based on its position, we first find the node, using the get method and set the value to the new value.
set(idx, val) {
var foundNode = this.get(idx)
if (foundNode) {
foundNode.val = val
return true;
}
return false;
}Insert a Node (in the middle)
To insert a node, we first check the index. If it’s equal to 0, we use our unshift method. If it’s equal to the length, we push it onto the list. Otherwise, we’ll get the before node by using the get method at one less than the index. Essentially, we need to keep track of the node before and after the selected index to ensure our pointers are directed toward the correct node.
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === 0) {
this.unshift(val)
return true;
};
if (idx === this.length) {
this.push(val);
return true;
};
var newNode = new Node(val);
var beforeNode = this.get(idx-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode;
newNode.next = afterNode;
this.length++;
return true;
}Remove a Node Based on Position
To remove a node based on position, we’ll use our get method again, and use the same principle that we used for inserting a node. By keeping track of the node previous to the chosen index, we can maneuver our pointers.
remove(idx) {
if (idx < 0 || idx > this.length) return undefined;
if (idx === this.length-1) {
this.pop()
}
if (idx === 0) {
this.shift()
}
var prevNode = this.get(idx-1)
var removeNode = prevNode.next
prevNode.next = removeNode.next
this.length--;
return removeNode;
}To see the complete code: checkout this GitHub gist.
Strengths of Linked Lists
The benefit of using a linked list is the ability to quickly insert and remove elements. Because linked lists aren’t indexed, inserting elements is relatively quick and easy.
Adding to the end of the linked list simply requires the old tail to point to the new node, and the tail property to be set to the new node. Adding to the beginning of the linked list is the same premise, but the new node points to the old head, and the head property is set to the new node. Fundamentally same actions, so insertion is O(1).
Note: Inserting in the middle of a linked list, requires searching through to find your node (O(N)) and then inserting the node (O(1)).
Removing a node from the linked list can be easy… but also not. This depends on where. Removing a node from the beginning of the list is simple — the second node becomes the new head, and we set the next pointer of the old head to null. Removing from the end is trickier because this requires going through the whole list and stopping at the second to last node. Worst-case O(N), and best case O(1).
Weaknesses of Linked Lists
Weaknesses of a linked list are caused by its lack of reindexing. Because you cannot access elements directly, it makes searching and accessing elements harder.
Searching & Accessing a node in a linked list requires starting at the beginning of the list and following the trail of breadcrumbs down the list. If we’re searching for the node at the end of the list, we will have to go through the whole linked list, effectively making time complexity O(N). As the list grows, the number of operations grows. Compared to an array that has random access — it takes constant time to access an element.
That’s it!
Linked lists are great alternatives to arrays when insertion and deletion at the beginning are key actions. Arrays are indexed, while linked lists are not. Linked lists are also the foundational data structure that stacks and queues are built off of, which I will be discussing in a later article. If you made it all the way here, kudos to you and I hope you learned a little nugget along with your programming journey!
