Linked Lists
Damely Tineo
Mar 27·6 min read
Linked lists are data structures used to store linear data.
Unlike arrays, linked lists do not have indexes. Instead, they have nodes. A Node is a basic unit of a data structure with no particular index. In linked lists, nodes connect or link to other nodes via pointers forming a linked chain-like structure. In singly-linked lists, these pointers connect one-directionally [from one node to the next]. In doubly-linked lists, pointers connect both ways [to and from].
Properties: The head of the linked list references the first node, the tail references the last node, and the length, like in arrays, the total number of elements or nodes.
const linkedList = {head: {
value: 4
next: {
value: 6
next: {
value: 8
next: {
value: 2
next: null
}
}
}
}
}
};
The Good:
Linked lists are really good at insertion and deletion. Unlike in arrays, where inserting at the front of a list, for example, requires us to shift/push back following elements, in a linked list, when inserting at the front of the list, all we have to do is make the new element/node the head of our list and have it point to the old head:
The Bad & The Ugly:
Given an index, we can easily search for the associated elements within an array. However, linked lists, unlike arrays, do not have indexes. In order to access a specific element or node within a linked list, we must search the list sequentially, starting from the very first node, as you can imagine, not the most efficient data structure for performing search operations!
Implementation
Start by defining the linked list and node classes and constructor methods. Then assign the nodes to the linked list as such:
Linked List:class linkedList {
constructor[head = null] { //head defaults to null
this.head = head
}
}Node:
class node {
constructor[data] {
this.data = data; //holds the data of a node
this.next = null; //holds the pointer to the next node
}
}Adding it all together:
let node1 = new node[4]
let node2 = new node[6]
node1.next = node2let list = new linkedList[node1]
Class Methods
We said linked lists are good for inserting but bad for searching, yet unfortunately, we can't insert in the middle of the linked list without searching.
Inserting/adding a new element to a linked list:
Notice how the new node squeezes its way between 91 and 23?
When inserting, typically, we are given an index and value, index being where we want to insert the value provided. We simply write a function that accepts these values, inserts the value at the index provided, and increments the lists length property by 1. Easy! Not so fast
How do we access the index/point at which we are inserting? How about when removing? Remember, with linked lists, we cant rely on index pointing to a specific node/element; instead, we must search for the desired location or node manually.
Are you ff? No. Are you ff? No. Are you ff? No. Are you ff? No. Are you ff? No. Are you ff? Yes. Finally!
Furthermore, what happens to our connections or links???
When inserting
here are some important things to consider:
- Is the given index 0? Add the element at the front of the list and make it the new head.
- Is the given index the last element of our list? Append the element at the end of the list, making it the new tail.
- What about if it is in between? An in between scenario is a little more complex. This requires us to iterate over to the index given and insert the element at that index WITHOUT replacing or losing the current node. To avoid resetting the node at the given index we need to make space for it while keeping track of the node that will be in front of it and of the node that will behind it. When we delete or insert an existing or new node we are severing its links/relationships therefore we need to reassign these too. Above, ff would no longer be the next of t5, instead ac would be.
let count = 0;
let current = this.head;
while [count < index] {
current = current.next;
count++;
}
return current;
} insert[index, value] {
if [index > 0 || index < this.length] {
let newNode = new Node[value];
let previousNode = this.get[index - 1];
let nextNode = previousNode.next; //Reassignment
previousNode.next = newNode;
newNode.next = nextNode;
this.length++;
return true;
}
}
Similar to inserting here are some things to consider hen deleting
- Is the given index 0? Remove the head and make the next node the new head.
- Is the given index the last element of our list? Remove the tail from the list and make the previous node the new tail.
- If it is in betweentraverse the list until finding the node previous to the element to be deleted, save its next connection as the element that is being deleted, sever this connection, then patch the hole/gap by connecting it to the deleted nodes next connection.
Doubly Linked Lists
Doubly-linked lists are like singly-linked lists with the exception of an additional pointer. In doubly-linked lists, pointers point to a next node as well as to a previous one.
Note: An additional pointer means more flexibility [to move up and down our list] but also more memory!
Implementation:
Linked List:class doublyLinkedList {
constructor[] {
this.head = null;
this.tail = null;
this.length = 0;
}
}Node:
class node {
constructor[data] {
this.data = data;
this.next = null;
this.prev = null;
}
}Adding it all together:
let node1 = new node[4]
let node1 = new node[4];
let node2 = new node[6];
node1.next = node2;
node2.prev = node1;let list = new linkedList[node1];
Doubly-linked lists are almost always a better option over singly-linked lists when having to get or find an element in a list. With a doubly-linked list, we can optimize our function to include searching from the end of the list the tail. If the index is greater than half of the length of the list: instead of looping through every element, we can start from the tail and save iterations.
class DoublyLinkedList {... get[index] {if [index < 0 || index >= this.length] return null; let count, current;
if [index