### Neil Berg twitter logo github logo Jun 9 '19・11 min read

When working with arrays, finding the point of insertion/deletion is constant in time but performing the insertion/deletion is O(n). This potentially costly operation happens since elements in arrays are allocated contiguously in memory, leading to a reorganization of the structure while performing the insertion/deletion.

On the flip side, linked lists, which are comprised of nodes containing a data value and a pointer to the next node (and previous node in the case of doubly linked lists), allow for constant-time insertion/deletion of elements. This performance gain - relative to arrays - occurs since we only need to track the current pointer in memory during traversal and re-assign that pointer when the target element is added or removed.

In other words, regardless of the linked list size, the act of insertion/deletion requires a single action of pointer reassignment, i.e., O(1) time complexity. Though, the traversal to find the element to add/remove has a complexity of O(n). In summary, the time complexities of insertion/deletion between arrays and linked lists are:

Arrays

• Finding the point of insertion/deletion: O(1)
• Performing the point of insertion/deletion: O(n)

• Finding the point of insertion/deletion: O(n)
• Performing the point of insertion/deletion: O(1)

Let's leap into the world of singly and doubly linked lists.

Singly linked lists are defined by nodes, which are plain objects, that contain two properties:

1. A value, such as an integer or a string
2. A pointer to the next node in the list, or null if at the end of the list.

The list itself also has two properties:

1. A head whose value points to the first node in the list
2. A length

For instance, a singly linked list with three nodes containing the values of 5, 8, and 13 looks like: #### Creating Node and SinglyLinkedList Classes

Using ES6 classes as syntactic sugar for prototypal inheritance, we can start by defining classes for nodes and the singly linked list structure.

Each `Node` in the list is instantiated with some value (e.g. an integer) and an initial `next` property set to `null`.

``````class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
``````

A new instance of `Node` is created with the `new` operator and the desired value passed into it:

``````const node = new Node(5);
console.log(node);
// Node { value: 5, next: null }
``````

The list is instantiated by defining two properties: a `head` that initially is set to null and a `length` that is initially zero.

``````class SinglyLinkedList {
constructor() {
this.length = 0;
}

// Methods to be added next
remove(value) {}
removeAt(k) {}
indexOf(value) {}
nodeAt(k) {}
}

console.log(sll);
``````

A new instance of SinglyLinkedList is created with the `new` operator:

``````const sll = new SinglyLinkedList();
``````

Adding a node at the end of a singly linked list takes the following steps:

1. Create a new node with the inputted value.
2. Check if the list is empty, i.e., the `head` is `null`.
3. If empty, set the list's head to the new node.
4. If not empty, traverse the list until the last node (which has a `next` value of `null`) is found, then set the last node's `next` property to point to the new node.
5. Increment the list's length.
``````add(value) {
const node = new Node(value);

} else {
while (current.next) {
current = current.next;
}
current.next = node;
}
this.length++;
}

//
console.log(JSON.stringify(sll, null, 4))
// {
//         "value": 5,
//         "next": {
//             "value": 8,
//             "next": {
//                 "value": 13,
//                 "next": null
//             }
//         }
//     },
//     "length": 3
// }
``````

#### Adding Node at Index k

Adding a node at an index k is accomplished with the following steps:

1. Ensure that index k is non-negative and less than the list's length.
2. Create a new node with the inputted value.
3. If k = 0, set the new node's `next` value to the initial `next` value of the list's `head` and reassign the `head` to the new node.
4. If k > 0, loop k times starting at the `head` and track the `previous` and `current` nodes during the traversal. These nodes are used to bracket the new node in the next step.
5. Set the `previous` node's `next` value to the new node and the new node's `next` value to the `current` node.
6. Increment the list's length.
``````  addAt(k, value) {
if (k < 0 || k > this.length) {
return false;
}

const node = new Node(value);
if (k === 0) {
} else {
let previous = undefined;
for (let i = 0; i < k; i++) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
}
this.length++
}

// Example --
console.log(JSON.stringify(sll, null, 4));
// {
//         "value": 5,
//         "next": {
//             "value": 8,
//             "next": {
//                 "value": 10,
//                 "next": {
//                     "value": 13,
//                     "next": null
//                 }
//             }
//         }
//     },
//     "length": 4
// }
``````

#### Removing Nodes

Removing nodes with a specific value is accomplished in the following steps:

1. If the target value is the value of the `head`, point the `head` to the `next` value of the `head` and decrement the list's length.
2. Otherwise, traverse the list - tracking the `previous` and `current` nodes - until the target node's value is reached.
3. Set the `previous` node's `next` value to the `current` node's `next` value.
4. Decrement the list's length.
``````remove(value) {
this.length--;
} else {
let previous = undefined;
while (current.next) {
// Traverse until target value found or end of list when current.next === null
if (current.value === value) {
previous.next = current.next;
this.length--;
break;
}
}
}
}
// Example --
sll.remove(8);
console.log(JSON.stringify(sll, null, 4));
// {
//         "value": 5,
//         "next": {
//             "value": 10,
//             "next": {
//                 "value": 13,
//                 "next": null
//             }
//         }
//     },
//     "length": 3
// }
``````

#### Removing Nodes at Index k

Removing nodes at index k is accomplished in the following steps:

1. Ensure that k is non-negative and less than the list's length.
2. If k === 0, re-set the `head` to point to it's `next` value and decrement the list's length.
3. If k > 0, traverse the list k times - keeping track of the `previous` and `current` node - and then set the `previous` node's `next` value to the `current` node's next value. Decrement the list.
``````removeAt(k) {
if (k < 0 || k > this.length) {
return false;
}

if (k === 0) {
this.length--;
} else {
let previous = undefined;
for (let i = 0; i < k; i++) {
previous = current;
current = current.next;
}
previous.next = current.next;
this.length--;
}
}
// Example --
sll.removeAt(1);
// {
//         "value": 5,
//         "next": {
//             "value": 13,
//             "next": null
//         }
//     },
//     "length": 2
// }
``````

#### The Index of a Value

Locating the index associated with a certain value is accomplished by simply traversing the list until the target value is found and returning how many steps the traversal required. If no value is found we can return -1 or something similar.

``````indexOf(value) {
let i = 0;
while (i < this.length) {
if (current.value === value) {
return i;
}
current = current.next;
i++;
}
return -1;
}

// Example --
console.log(sll.indexOf(5)); // 0
console.log(sll.indexOf(8)); // 1
console.log(sll.indexOf(13)); // 2
``````

#### The Node at Index k

Locating the node at a particular index is accomplished by simply traversing the list k times and returning the resulting node. As done before, we also first check to make sure a valid index is provided.

``````nodeAt(k) {
if (k < 0 || k > this.length - 1) {
return false;
}
for (let i = 0; i < k; i++) {
current = current.next;
}
return current;
}

// Example --
console.log(JSON.stringify(sll.nodeAt(1), null, 4));
// {
//     "value": 8,
//     "next": {
//         "value": 13,
//         "next": null
//     }
// }
``````

We saw that only forward traversal (starting at the head) was possible in singly linked lists. Enabling forward and backward traversal is possible by adding a `previous` or `prev` property to each node and a `tail` property to the linked list. The result is a doubly linked list and conceptually looks like: #### Creating Node and DoublyLinkedList Classes

Each `Node` in the list is instantiated with some value (e.g., an integer) and `next` and `prev` properties set to `null`.

``````class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
``````

The list is instantiated by defining three properties: a `head` and `tail` that initially are set to null and a `length` that is initially zero.

``````class SinglyLinkedList {
constructor() {
this.tail = null;
this.length = 0;
}

// New methods to be added next
display() {}

removeAtTail() {}
removeAtIndex(k) {}
removeAtElement(element) {}
}

console.log(dll);
``````

#### Displaying the List

Logging a doubly linked list to the console is a bit tricky due to the circuitous nature of the the `prev` pointers. I prefer to display the `head`, `tail`, and each `node` on new lines surrounded by arrows representing their `prev` and `next` properties:

``````display() {
let dataString = 'Head => ' + '\n';
while (current !== null) {
dataString += '<-' + current.value + '->' + '\n';
current = current.next;
}
dataString += '<= Tail';
return dataString;
}
``````

Adding nodes at the head of the list is accomplished in the following steps:

1. If the list is empty, point the head and tail to the new node.
2. If the list is not empty:
• Set the new node's `next` property to the head's current value (i.e., the current first node in the list).
• Set the current first node's `prev` property (`this.head.prev`) to the new node.
• Reset the head to point to the new node.
3. Increment the list's length.
``````addAtHead(value) {
let node = new Node(value);
// First node
this.tail = node;
} else {
}
this.length++;
}
// -- Example
console.log(dll.display());
// <-5->
// <-8->
// <-13->
// <= Tail
``````

#### Addings Nodes at the Tail

1. If the list is empty, point the head and tail to the new node.
2. If the list is not empty:
• Set the new node's `prev` property to the tail's current value (i.e., the current last node in the list)
• Set the current last node's `next` property (`this.tail.next`) to the new node.
• Reset the tail to point to the new node.
3. Increment the list's length.
``````addAtTail(value) {
let node = new Node(value);
if (!this.tail) {
// First node
this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.length++;
}
// -- Example
console.log(dll.display());
// <-5->
// <-8->
// <-13->
// <-22->
// <= Tail
``````

#### Adding Nodes at Index k

Adding new nodes at a specified index k is accomplished by:

1. Checking that the index is non-zero and less than the list's length
2. If k = 0, we're at the beginning of the list, so the new node is inserted at the head (see steps above for `addAtHead()`)
3. If k = the list's length, we're at the end of the list, so the new node is inserted at the tail (see steps above for `addAtTail()`)
4. Otherwise, traverse k steps forward from the head (as shown below) or backward from the tail and track the current head in each step. Then:
• Set the new node's `prev` property to the current head at the end of the traversal
• Set the new node's `next` property to the `next` property of the current node
• Set the current node's `next` property to the new node
5. Increment the list's length.
``````addAtIndex(k, value) {
const node = new Node(value);
if (k < 0 || k > this.length) return undefined;
if (k === 0) {
} else if (k === this.length - 1) {
// at tail
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
} else {
//somewhere in the body
let i = 1;
while (current.next) {
if (i === k) {
node.prev = current;
node.next = current.next;
current.next = node;
}
current = current.next;
i++;
}
}
this.length++;
}
// -- Example
console.log(dll.display());
// <-5->
// <-8->
// <-10->
// <-13->
// <-22->
// <= Tail
``````

#### Adding Nodes at an Element

Adding nodes at target element is even easier than adding at a target index. We simply traverse the list until the target element is found, tracking the current node at each step, and then:

1. Set the new node's `prev` property to the current node.
2. Set the new node's `next` property to the value current node's `next` property.
3. Set the current node's `next` value to the current node.
4. Increment the list's length.
``````addAtElement(element, value) {
const node = new Node(value);
while (current.value !== element && current.next) {
current = current.next;
}
node.prev = current;
node.next = current.next;
current.next = node;
this.length++;
}
// -- Example
console.log(dll.display());
// <-5->
// <-7->
// <-8->
// <-10->
// <-13->
// <-22->
// <= Tail
``````

#### Removing Nodes at the Head

To remove a node at the head, we essentially skip over the first element in the list. This is done by:

1. Moving the head to its `next` value.
2. Setting the `prev` property of the node that the head is now pointed at to `null`.
3. Decrementing the list's length.
``````removeAtHead() {
this.length--;
}
}
// -- Example
console.log(dll.display());
// <-8->
// <-13->
// <= Tail
``````

#### Removing Nodes at the Tail

To remove a node at the tail, we essentially skip over the last element in the list. This is done by:

1. Moving the tail to the tail's `prev` node.
2. Setting the `next` property of the node that the tail is now pointing at to `null`.
3. Decrementing the list's length.
``````removeAtTail() {
if (this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
this.length--;
}
}
// -- Example
dll.removeAtTail();
console.log(dll.display());
// <-5->
// <-8->
// <= Tail
``````

#### Removing Nodes at Index k

When removing nodes at a target index k, we first check to make sure k is non-negative and less than the list's length. Then:

1. If k = 0, we're at the head, call `removeAthead()`
2. If k = list's length, we're at the tail, call `removeAtTail()`
3. Otheriwse, traverse k steps, tracking the current node during each step, and then essentially skip over the node to be removed by:
• Setting the current node's `prev.next` value to the current node's `next` value.
• Setting the current node's `next.prev` value to the current node's `prev` value.
4. Decrement the list's length.
``````removeAtIndex(k) {
if (k < 0 || k > this.length - 1) {
return undefined;
}
if (k === 0) {
} else if (k === this.length - 1) {
// at the tail
this.removeAtTail();
} else {
for (let i = 0; i < k; i++) {
previous = current;
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
}
this.length--;
}
// -- Example
dll.removeAtIndex(1);
console.log(dll.display());
// <-5->
// <-13->
// <= Tail
``````

#### Removing Nodes at Target Element

Finally, we can remove at a desired element using the following steps:

1. If the element to be removed is attached to the node that the `head` is pointing to, call `removeAtHead()`
2. If the value to be removed is attached to the node that the `tail` is pointing to, call `removeAtTail()`
3. Otherwise, traverse the list until that element is found, tracking the current node during each step, and applying the same logic as above when removing at a desired index.
4. Decrement the list's length.
``````removeAtElement(element) {
} else if (element === this.tail.value) {
this.removeAtTail();
} else {
while (current.value !== element && current.next) {
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
this.length--;
}
}
// -- Example
dll.removeAtElement(8);
console.log(dll.display());
// <-5->
// <-13->
// <= Tail
``````
DISCUSS Sore eyes?

dev.to now has dark mode.

Go to the "misc" section of your settings and select night theme.

Classic DEV Post from Jun 5 '19

## Are we "developers" gatekeeping "knowledge" from our juniors and peers? 🤦  