Linked List

Linked List comes in three basic varieties: singly, doubly, and circular.

Singly linked list are linear lists where each element ‘points’ to the element that follows it in the list. The first element in a singly linked list is known as the head. While the last element in the list is known as the tail.

With the exception of the tail. All elements point to the next element in the list. While the tail has a null link. A visual of a singly linked list is shown below in figure 2.1

Since an element in a singly linked list only points to the next element, the list can only be traversed in the forward direction. Because of this limitation, a complete traversal of the list must start with the first element. In other words, when traversing the list in figure 2.1, we need to start at the head. If we do not, all elements in the list will not be traversed.

Doubly linked list forgoes the prior mentioned limitation that a singly linked list has.

Shown below in figure 2.2, each element in a doubly linked list points to the next and previous elements. However, the head element will not have a link to a previous element and the tail will not have a link to a next element.

Circular linked lists are singly in structure or doubly in structure and have no head nor tail. Meaning, regardless of a singly or doubly linked list, each element will point to another element.

In-regards to a circular linked list that is singly in structure. Next links will always have a value and will never be null. See figure 2.3.

In the case of a circular doubly linked list, next and previous will always have a value and will never be null. See figure 2.4.

The challenge with circular linked lists is how to avoid cycling through the list infinitely. To overcome this challenge, when traversing a circular list, we will need to track where we start our traversal.

Linked List
in-Action with Alto.js

Our data structure to describe an element in a linked list will be a javascript object literal. Specifically, our element for a singly linked list will have two properties: data, and next.

Once we have a LinkedList generated, we can ‘walk’ the list by storing the value of the current element to a variable and reassigning the variable with the returned element from element.next. This pattern is repeated until all of the elements are touched and the tail element is found. See figure 2.5.

Walking the linked list in such a fashion is not of much use. Let us extend the functionality of our LinkedListAlgorithms class. Ultimately we will want an api to search, insert (before/after), and delete (all/one) elements. Let us start by adding a way to find an element within a linked list.

Since we are working on an api for singly linked list. We will prefix our find method with the letter ’s’. Going forward all methods in our linked list api will follow this naming pattern.

sFind is a straight forward operation. Given a value to lookup and the head of a linked list, return the matched element. The pitfall here is traversing the entire linked list without finding the provided value. See figure 2.6.

sInsertBefore is more involved thansFind: given a value to insert, a lookup to insert the new value before, and the head of a linked list return the updated linked list. As with our find method, the pitfall here is traversing the entire linked list without finding the provided lookup. Additionally, we need to handle the edge-case of inserting before the head. See figure 2.7.

sInsertAfter: given a value to insert, a lookup to insert the new value after, and the head of a linked list, return the updated linked list. As we traverse through the list, we pass back the current element as head. There are two logical paths to watch out for and one edge case.

The first is when the data matches our lookup and we are not at a tail element, meaning head has a non-null next value. We will create a new element, assign its next value to the current head.next then assign the element to the next value of our current head.

The second case if when our data matches the lookup and it is our tail element. Here we create a new element, assign null to the new elements next value, and replace the current head.next to the new element.

And last we handle the case of reaching the tail but not finding a matching lookup.

sDelete: given a lookup to match, and the head of a linked list, return the updated linked list minus our match to the lookup.

Before traversing the linked list, create a new value for head as element to delete, check if the element to delete matches our lookup. When there is a match, meaning we want to delete the head of the list, move the head to the next node, null out the element to delete and return the updated head.

When the element to delete is not the head of the list, check to see if we reached the tail element with no match. If so, throw a no match found error. If we are not at the tail, and our current element to delete next value matches our lookup, move the head.next to the next.next element, null out the element to delete, and return the updated head.

sDeleteList: given the head of a linked list, delete the list.

Dealing with deletion of a list isn’t as straight forward as we may think. The natural process is to use a single reference while traversing the list and remove items we go. The challenge here is, “Do we move head first or remove the element first?” Both options will not work.

We cannot move the value first, dletion will be impossible since we no longer have the current head value to delete. And we cannot delete the element first, moving to the next head will be impossible since we no longer have an element with a next value. The solution is to use two values for head: one for tracking head and another for the element to delete.