Linked List in Javascript (Data Structures)

Short and Precise Js code to create a singly linked list.

Photo by Crispin Jones on Unsplash

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from the head to the last node (tail). Every node contains some data and a pointer to the next node of the same data type. The node contains a pointer to the next node means that the node stores the address of the next node in the sequence.

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 a pointer.

Linked List:

Push: adding a node at the end of the linked list

1. The function should accept a value.
2. Create a new node using the value passed to the function.
3. If there is no head property on the list, set the head and tail to be the newly created node.
4. Otherwise set the next property on the tail to the new node and set the tail property on the list to be the newly created node.
5. Increment the length by one.
6. Return the linked list.

Pop: removing a node from the end of the linked list

1. If there are no nodes in the linked list, return undefined.
2. Loop through the list until you reach the tail.
3. Set the next property of the second last node to be null.
4. Set the tail to be the second last node.
5. Decrement the length of the list by one.
6. Return the value of the node removed.

Unshift: adding a new node at the beginning of the linked list

1. This function should accept a value.
2. Create a new node using the value passed to the function.
3. If there is no head property on the list, set the head and tail to be the newly created node.
4. Otherwise set the newly created node’s next property to be the current head on the list.
5. Set the head property on the list to be that newly created node.
6. Increment the length of the list by one.
7. Return the linked list.

Shift: removing a new node from the beginning of the linked list

1. If there isn’t any node in the linked list, return undefined.
2. Store the current head property in a variable.
3. Set the head property to be the current head’s next property.
4. Decrement the length by one.
5. Return the value of the node removed.

Get: retrieving a node by its position in the linked list.

1. The function should accept an index.
2. If the index is less than zero or greater than or equal to the length of the list, return null.
3. Loop through the list until you reach the index and return the node at that specific index.

Set: changing the value of a node based on its position in the linked list.

1. The function should accept a value and an index.
2. Use the get function to find the specific node.
3. If the node is not found, return false.
4. If the node is found, set the value of that node to be the value passed to the function and return true.

Insert: adding a node to the linked list at a specific position

1. If the index is less than zero or greater than the length, return false. (index < 0 || index > length)
2. If the index is the same as the length, push a new node to the end of the list. (index == length)
3. If the index is zero, unshift a new node to the start of the list. (index == 0)
4. Otherwise, using the get method, access the node at the index-1.
5. Set the next property on that node to be the new node.
6. Set the next property on the new node to be the previous next.
7. Increment the length.
8. Return true.

Remove: remove a node from the linked list at a specific position

1. If the index is less than zero or greater than the length, return undefined. (index < 0 || index > length)
2. If the index is the same as the length-1, pop. (index = length-1)
3. If index = 0, shift.
4. Otherwise using the get method, access the node at the index-1.
5. Set the next property on that node to be the next of the next node.
6. Decrement the length by one.
7. Return the value of the node removed.

Time Complexity of Singly Linked List:

• Access: O(n)
• Search: O(n)
• Insertion: O(1)
• Removal: O(1) (in some cases O(n))

Summary:

Singly Linked Lists are excellent alternatives to arrays when insertion and deletion at the beginning are frequently required.