Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell
Understanding Singly Linked Lists
A linked list is a data structure that represents a sequence of nodes. In a singly linked list, each node points to the next node.
In memory, these nodes do not need to be sorted contiguously (adjacent to one another) since we are not relying on indexing. When we iterate through a linked list, we pass through each reference of a node until we hit a null pointer.
Structure of a Node
In a singly linked list, each node typically contains two fields:
- data: the value or information contained in the node
- next: the reference (pointer) to the next node in the list
Head and Tail Pointers
The head is a reference to the first node in the list. It is essential because it allows access to the linked list’s start. It sometimes acts as a sentinel node (placed before the actual head node) for easier operations like inserting at the head. The tail is a reference to the last node in the list. It’s next pointer is null indicating the end of the list.
Memory Efficiency of Insertions/Deletions
Compared to arrays, linked lists are more memory efficient in terms of insertion/deletion since these operations do not require “shifting” of elements. The operation of adding or removing an element from anywhere in a linked list takes time. However, it takes time in the worst case to traverse through the linked list to then add/remove an element (does not apply for adding/removing first element).
It's worth pointing out that linked lists have extra memory overhead due to the storage of pointers along with data in each node.
Time Complexity Analysis
Insertion:
- at beginning or end (with head/tail pointers) →
- at specific position (due to traversal) →
Deletion:
- at beginning →
- at end →
- at specific position →
Traversal/Search:
JavaScript Implementation
Classical OOP
class ListNode {
constructor(val, nextNode = null) {
this.val = val;
this.next = nextNode;
}
}
class LinkedList {
constructor() {
// sentinel node for easy operations on head
this.head = new ListNode(-1);
this.tail = this.head;
}
// get the value at the specified index.
get(index) {
let curr = this.head.next;
let i = 0;
while (curr !== null) {
if (i === index) return curr.val;
curr = curr.next;
i++;
}
return -1;
}
// insert a new value at the head of the list.
insertHead(val) {
const newNode = new ListNode(val);
newNode.next = this.head.next;
this.head.next = newNode;
if (newNode.next === null) {
this.tail = newNode;
}
}
// insert a new value at the tail of the list.
insertTail(val) {
const newNode = new ListNode(val);
this.tail.next = newNode;
this.tail = newNode;
}
// remove the node at the specified index.
remove(index) {
let curr = this.head;
let i = 0;
while (i < index && curr.next !== null) {
i++;
curr = curr.next;
}
if (curr !== null && curr.next !== null) {
if (curr.next === this.tail) this.tail = curr;
curr.next = curr.next.next;
return true;
}
return false;
}
// get all values in the list as an array.
getValues() {
const values = [];
let curr = this.head.next;
while (curr !== null) {
values.push(curr.val);
curr = curr.next;
}
return values;
}
// get the length of the list.
length() {
let length = 0;
let curr = this.head.next;
while (curr !== null) {
length++;
curr = curr.next;
}
return length;
}
}
Prototype-Based OOP
function ListNode(val, nextNode = null) {
this.val = val;
this.next = nextNode;
}
function LinkedList() {
this.head = new ListNode(-1); // Sentinel node
this.tail = this.head;
}
// get the value at the specified index
LinkedList.prototype.get = function(index) {
let curr = this.head.next;
let i = 0;
while (curr !== null) {
if (i === index) return curr.val;
curr = curr.next;
i++;
}
return -1;
};
// insert a new value at the head of the list
LinkedList.prototype.insertHead = function(val) {
const newNode = new ListNode(val);
newNode.next = this.head.next;
this.head.next = newNode;
if (newNode.next === null) {
this.tail = newNode;
}
};
// insert a new value at the tail of the list
LinkedList.prototype.insertTail = function(val) {
const newNode = new ListNode(val);
this.tail.next = newNode;
this.tail = newNode;
};
// remove the node at the specified index
LinkedList.prototype.remove = function(index) {
let curr = this.head;
let i = 0;
while (i < index && curr.next !== null) {
i++;
curr = curr.next;
}
if (curr !== null && curr.next !== null) {
if (curr.next === this.tail) this.tail = curr;
curr.next = curr.next.next;
return true;
}
return false;
};
// get all values in the list as an array
LinkedList.prototype.getValues = function() {
const values = [];
let curr = this.head.next;
while (curr !== null) {
values.push(curr.val);
curr = curr.next;
}
return values;
};
// get the length of the list
LinkedList.prototype.length = function() {
let length = 0;
let curr = this.head.next;
while (curr !== null) {
length++;
curr = curr.next;
}
return length;
};
Top comments (0)