Doubly Linked List in Javascript (Data Structures)

Short and Precise Js code to create a doubly linked list

Photo by Kaley Dykstra on Unsplash

Almost identical to the singly-linked lists, except every node has another pointer, to the previous node. It provides more flexibility over singly-linked lists.

Todos:

1. Push and Pop

2. Unshift and Shift

3. Get and Set

4. Insert and Remove

Creating a Node: It contains a value and two pointers next, prev.

Doubly Linked List: three important things - head, tail, length

Push: Adding a node to the end of the doubly linked list

1. This function will accept a value. Create a new node with the value passed to the function.
2. If the head property is null, then set the head and tail to be the new node.
3. If not, set the next property on the tail of DLL to that node.
4. Set the previous property on the new node to be the tail.
5. Set the tail to be the newly created node.
6. Increment the length of the DLL by one.
7. Return DLL.

Pop: removing a node from the end of the DLL.

1. If there is no head, return undefined.
2. Store the current tail in a variable to return later.
3. If length is one, set the head and tail to be null;
4. Update the tail to be the previous node.
5. Set the new tail’s next value to null.
6. Decrement the length by one.
7. Return the removed value.

Unshift: adding a new node to the beginning of the DLL.

1. This function should accept a value and create a new node using that value.
2. If the length of the DLL is zero, set the head and tail to be the new node.
3. Otherwise,

• Set the prev property on the head of the list to be the new node.
• Set the next property on the new node to the current head.
• Update the head of the DLL to be the newly created node.

4. Increment the length by one.

5. Return the list.

Shift: removing a node from the beginning of the DLL.

1. If length is zero, return undefined.
2. Store the value of the head in a variable.
3. If length is one, set the head and tail to null.
4. Update the head to be the next of the old head.
5. Set the head's previous property to null.
6. Set the old heads next to null.
7. Decrement the length by one.
8. Return old head.

Get: accessing a node in a DLL.

1. This function will accept an index. If the index is less than 0 (zero) or ≥ (gte) to the length, return null.
2. If the index is ≤ (lte) half of the length of the list.

• Loop through the list starting from the head and loop towards the middle.
• Return the node once it's found.

3. If the index is ≥ (gte) half of the length of the list.

• Loop through the list starting from the tail and loop towards the middle.
• Return the node once it is found.

Set: replacing the value of the node to the index in a DLL.

1. Create a variable which is the result of the get method at the index passed to the function.

• If the get method returns a valid node, set the value of that node to be the value passed to the function.
• Return true.

2. Otherwise, return false.

Insert: adding a node in a DLL at a certain position.

1. If the index is less than zero or ≥ (gte) the length return false.
2. If the index is zero, unshift.
3. If the index is the same as the length, push.
4. Use the get method to access the index-1.
5. Set the next and prev property on the correct nodes to link everything together.
6. Increment the length by one.
7. return true.

Remove: removing a node in the DLL from a certain position.

1. If the index is less than 0 or ≥ (gte) the length return undefined.
2. If the index is zero, shift.
3. If the index is the same as the length-1, pop.
4. Use the get method to retrieve the item to be removed.
5. Update the next and previous properties to remove the found node from the list.
6. Set next and previous to null on the found node.
7. Decrement the length by one.
8. Return the removed node.

Time Complexity of Doubly Linked List:

• Access: O(N)
• Search: O(N)
• Insertion: O(1)
• Removal: O(1)

Summary:

1. Almost identical to SLL except there is an additional pointer to the previous node.
2. Better at finding nodes and can do it in half time compared to SLL.
3. They need more memory considering the extra pointer.