## DEV Community

Terrence Jung

Posted on • Updated on

# Implementing a Singly Linked List

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

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

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 $O(1)$ time. However, it takes $O(n)$ 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) → $O(1)$
• at specific position (due to traversal) → $O(n)$

Deletion:

• at beginning → $O(1)$
• at end → $O(n)$
• at specific position → $O(n)$

Traversal/Search: $O(n)$

### JavaScript Implementation

#### Classical OOP

class ListNode {
constructor(val, nextNode = null) {
this.val = val;
this.next = nextNode;
}
}

constructor() {
// sentinel node for easy operations on head
}

// get the value at the specified index.
get(index) {
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.
const newNode = new ListNode(val);
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 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 = [];
while (curr !== null) {
values.push(curr.val);
curr = curr.next;
}
return values;
}

// get the length of the list.
length() {
let length = 0;
while (curr !== null) {
length++;
curr = curr.next;
}
return length;
}
}


#### Prototype-Based OOP

function ListNode(val, nextNode = null) {
this.val = val;
this.next = nextNode;
}

this.head = new ListNode(-1); // Sentinel node
}

// get the value at the specified index
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
const newNode = new ListNode(val);
if (newNode.next === null) {
this.tail = newNode;
}
};

// insert a new value at the tail of the list
const newNode = new ListNode(val);
this.tail.next = newNode;
this.tail = newNode;
};

// remove the node at the specified index
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
const values = [];
while (curr !== null) {
values.push(curr.val);
curr = curr.next;
}
return values;
};

// get the length of the list