Singly Linked List
Linked List, like arrays, is a linear data structure. It contains head, tail and length properties. As shown below, each element in linked list is a node, which has a value and a reference to next node, or if it’s tail, points to null.
Why do we need linked list if we have arrays?
For data insertion and deletion, arrays can be expensive. Linked list, on the other hand, has dynamic size and makes insertion and deletion so easy. One disadvantage though, unlike arrays, elements in linked list doesn’t have indexes in order, which doesn’t allow random access.
There are different types of linked list, such as, singly linked list, doubly linked list and circular linked list. Since singly linked list is most common, let’s talk about singly linked list in JavaScript.
To have a clear understanding of singly linked list, I’ll implement SinglyLinkedList class in TypeScript (JavaScript).
Each node of Linked list will have two attributes: value & next, and linked list will have head, tail and length attribute.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}How can we push a new node into the end of our list? Let’s make a push function. First, we need to create a new node using the given value, check if the list has a head (is it empty?) and don’t forget to increment the size of the list.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(val: T): SinglyLinkedList<T> {
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail!.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
}With pushing, we need to think about popping, deleting the last element. If there is no node, return undefined, else, loop through the list until we reach the tail, set the next property of the second last node to be null, make the second last to be the tail, don’t forget to decrement the size of the list.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
pop(): Node<T> | undefined {
if (!this.head) return undefined;
let current: Node<T> | null = this.head;
let newTail: Node<T> | null = current;
while (current.next) {
newTail = current;
current = current.next;
}
this.tail = newTail;
if (this.tail) {
this.tail.next = null;
}
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
}For deleting the first element, shifting, as usual, check if the list is empty. First, store the current head in a variable, set the head to be the current head’s next, decrement the length.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
shift(): Node<T> | undefined {
if (!this.head) return undefined;
const currentHead: Node<T> | null = this.head;
this.head = currentHead.next;
this.length--;
if (this.length === 0) {
this.tail = null;
}
return currentHead;
}
}To insert a node at the beginning of the list, check if the list is empty, if not, we set the current head to be the next attribute of the incoming node, increment the size.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
unshift(val: T): SinglyLinkedList<T> {
const newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
}Even though linked list doesn’t have indexes, we are still able to find the node by given index. First make sure the given index is greater than zero and smaller or equal to the length of the list. Than we loop through the list until we reach the index.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
get(index: number): Node<T> | null {
if (index < 0 || index >= this.length) return null;
let counter = 0;
let current: Node<T> | null = this.head;
while (counter !== index) {
if (current) {
current = current.next;
} else {
// Handle unexpected null value in the middle of the list.
return null;
}
counter++;
}
return current;
}
}What if we want to change a node in our list? We find the node with get(), and set the node with given data.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
get(index: number): Node<T> | null {
if (index < 0 || index >= this.length) return null;
let counter = 0;
let current: Node<T> | null = this.head;
while (counter !== index) {
if (current) {
current = current.next;
} else {
// Handle unexpected null value in the middle of the list.
return null;
}
counter++;
}
return current;
}
set(index: number, val: T): boolean {
const foundNode: Node<T> | null = this.get(index);
if (foundNode) {
foundNode.val = val;
return true;
}
return false;
}
}When we want to insert a new node into the list, first check if the index is greater than 0 and smaller than the length. If index is the length, we just use push(), if the index is 0, we use unshift(). For other indexes, we need to get the node at the index-1, and set the next property of that node to be the new node, and the next property of the new node to be the previous next property, then we increment the length.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(val: T): SinglyLinkedList<T> {
const newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail!.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
unshift(val: T): SinglyLinkedList<T> {
const newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
get(index: number): Node<T> | null {
if (index < 0 || index >= this.length) return null;
let counter = 0;
let current: Node<T> | null = this.head;
while (counter !== index) {
if (current) {
current = current.next;
} else {
// Handle unexpected null value in the middle of the list.
return null;
}
counter++;
}
return current;
}
insert(index: number, val: T): boolean {
if (index < 0 || index > this.length) return false;
if (index === this.length) return !!this.push(val);
if (index === 0) return !!this.unshift(val);
const newNode = new Node(val);
const prev = this.get(index - 1);
const temp = prev!.next;
prev!.next = newNode;
newNode.next = temp;
this.length++;
return true;
}
}Unlike pop and unshift, remove function will remove the node by given index. As usual, check if the index is valid, if index equals to length-1 or 0, use pop or shift. Otherwise, we get the node at the index-1, set the next property on that node to be the next of the next property, after, we decrement the size.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
pop(): Node<T> | undefined {
if (!this.head) return undefined;
let current: Node<T> | null = this.head;
let newTail: Node<T> | null = current;
while (current.next) {
newTail = current;
current = current.next;
}
this.tail = newTail;
if (this.tail) {
this.tail.next = null;
}
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
shift(): Node<T> | undefined {
if (!this.head) return undefined;
let currentHead: Node<T> | null = this.head;
this.head = currentHead.next;
this.length--;
if (this.length === 0) {
this.tail = null;
}
return currentHead;
}
get(index: number): Node<T> | null {
if (index < 0 || index >= this.length) return null;
let counter = 0;
let current: Node<T> | null = this.head;
while (counter !== index) {
if (current) {
current = current.next;
} else {
// Handle unexpected null value in the middle of the list.
return null;
}
counter++;
}
return current;
}
remove(index: number): Node<T> | undefined {
if (index < 0 || index >= this.length) return undefined;
if (index === 0) return this.shift();
if (index === this.length - 1) return this.pop();
const previousNode: Node<T> | null = this.get(index - 1);
if (!previousNode || !previousNode.next) return undefined;
const removed: Node<T> | null = previousNode.next;
previousNode.next = removed.next;
this.length--;
return removed;
}
}The ultimate reverse question! How do we reverse the list? First, we swap head and tail, declare next and previous, set the previous as null. We loop through the list.
class Node<T> {
val: T;
next: Node<T> | null;
constructor(val: T) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList<T> {
head: Node<T> | null;
tail: Node<T> | null;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
reverse(): SinglyLinkedList<T> {
let node: Node<T> | null = this.head;
this.head = this.tail;
this.tail = node;
let next: Node<T> | null;
let prev: Node<T> | null = null;
for (let i = 0; i < this.length; i++) {
if (node) {
next = node.next;
node.next = prev;
prev = node;
node = next;
} else {
// Handle unexpected null value in the middle of the list.
return this;
}
}
return this;
}
}| Method | Time Complexity | Space Complexity |
|---|---|---|
| push(val) | O(1) | O(1) |
| pop() | O(n) (worst case) | O(1) |
| shift() | O(1) | O(1) |
| unshift(val) | O(1) | O(1) |
| get(index) | O(n) (worst case) | O(1) |
| set(index, val) | O(n) (worst case) | O(1) |
| insert(index, val) | O(n) (worst case) | O(1) |
| remove(index) | O(n) (worst case) | O(1) |
| reverse() | O(n) (worst case) | O(1) |
In practice, singly linked lists are particularly useful when you need fast insertions and deletions at the beginning of the list (constant time complexity) and when you don't require direct access to elements by index.