linked-list.asc

Linked List

A list (or Linked List) is a linear data structure where each node is "linked" to the next.

Linked Lists can be:

• Singly: every item has a pointer to the next node

• Doubly: every node has a reference to the next and previous node

• Circular: the last element points to the first one.

Singly Linked List

Each element or node is connected to the next one by a reference. When a node only has one connection, it’s called a singly linked list:

Figure 1. Singly Linked List Representation: each node has a reference (blue arrow) to the next one.

Usually, a Linked List is referenced by the first element called head (or root node). For instance, if you want to get the cat element from the example above, then the only way to get there is by using the next field on the head node. You would get art first, then use the next field recursively until you eventually get the cat element.

Doubly Linked List

When each node has a connection to the next item and also the previous one, then we have a doubly linked list.

Figure 2. Doubly Linked List: each node has a reference to the next and previous element.

With a doubly list, you can not only move forward but also backward. If you keep the reference to the last element (cat) you can step back and reach the middle part.

If we implement the code for the Node elements, it would be something like this:

Linked List Node Implementation

link:../../../src/data-structures/linked-lists/node.js[role=include]

Linked List vs. Array

Arrays allow you to access data anywhere in the collection using an index. However, Linked List visits nodes in sequential order. In the worst-case scenario, it takes O(n) to get an element from a Linked List. You might be wondering: Isn’t an array always more efficient with O(1) access time? It depends.

We also have to understand the space complexity to see the trade-offs between arrays and linked lists. An array pre-allocates contiguous blocks of memory. It has to create a larger array (usually 2x) and copy all the elements when it is getting full. It takes O(n) to copy all the items over. On the other hand, LinkedList’s nodes only reserve precisely the amount of memory they need. They don’t have to be next to each other, nor are large chunks of memory booked beforehand like arrays. Linked List is more on a "grow as you go" basis.

Another difference is that adding/deleting at the beginning on an array takes O(n); however, the linked list is a constant operation O(1) as we will implement later.

A drawback of a linked list is that if you want to insert/delete an element at the end of the list, you would have to navigate the whole collection to find the last one: O(n). However, this can be solved by keeping track of the last element in the list. We are going to implement that!

Implementing a Linked List

We are going to implement a doubly linked list. First, let’s start with the constructor.

Linked List’s constructor

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

  // ... methods go here ...
}

In our constructor, we reference the first and last node for performance reasons.

Searching by value

There’s no other way to find an element by value than iterating through the entire list.

Linked List’s searching by values

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

If we find the element, we will return the index otherwise undefined. The runtime for locating an item by value is O(n).

For finding elements by value or position, we are using the following helper function:

Find elements using a callback

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

1. We initialize two variables current to the first node and position to keep track of the index.

2. While the current node is not null, we keep going.

3. On each loop, we move to the next node and increment the index.

4. We invoke the callback passing the current position and node. If the callback returns something, then we stop and return that value.

5. Return whatever result we got from the callback. E.g., we can return the index or the node itself or any other calculation.

We are going to use this find method again to implement searching by index.

Searching by index

Searching by an index is very similar, we iterate through the list until we find the element that matches the position.

Linked List’s searching by index (position)

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

If there’s no match, we return undefined then. The runtime is O(n). As you might notice, the search by index and by position methods looks pretty similar; you want to take a look at the full implementation.

Insertion

In a linked list, you can add elements at the beginning, end, or anywhere in the middle of the list. So, let’s implement each case.

Inserting elements at the beginning of the list

We will use the Node class to create a new element and stick it at the beginning of the list, as shown below.

Figure 3. Insert at the beginning by linking the new node with the current first node.

To insert at the beginning, we create a new node with the next reference to the current first node. Then we first make the new node. In code, it would look something like this:

Add item to the beginning of a Linked List

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

As you can see, we create a new node and make it the first one.

Inserting element at the end of the list

Appending an element at the end of the list can be done very effectively if we have a pointer to the last item. Otherwise, you would have to iterate through the whole list.

Figure 4. Add element to the end of the linked list

Linked List’s add to the end of the list implementation

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

If there’s no element in the list yet, the first and last node would be the same. If there’s something, we go to the last item and add the reference next to the new node. That’s it! We got a constant time for inserting at the beginning and the end of the list: O(1).

Inserting element at the middle of the list

For inserting an element in the middle of the list, you would need to specify the position (index) in the collection. Then, you create the new node and update the references to it.

There are 4 references to update:

1. New node’s next.

2. New node’s previous.

3. New node’s previous next.

4. New node’s next previous.

Let’s do an example with the following doubly linked list:

art <-> dog <-> cat

We want to insert the new node in the 2^nd position. For that, we first create the "new" node and update the references around it.

Figure 5. Inserting node in the middle of a doubly linked list.

Take a look into the implementation of LinkedList.add:

Linked List’s add to the middle of the list

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

1. If the new item goes to position 0, then we reuse the addFirst method, and we are done!

2. However, if we add to the last position, we reuse the addLast method and done!

3. Adding newNode to the middle: First, create the new node only if it exists. Take a look at Searching by index to see get implementation.

4. Set newNode previous reference.

5. Set newNode next link.

6. No other node in the list points to newNode, so we have to make the prior element point to newNode.

7. Make the next element point to newNode.

Take notice that we reused addFirst and addLast methods. For all the other cases, the insertion is in the middle. We use current.previous.next and current.next to update the surrounding elements and make them point to the new node. Inserting in the middle takes O(n) because we have to iterate through the list using the get method.

Deletion

Deleting is an interesting one. We don’t delete an element; we remove all references to that node. Let’s go case by case to explore what happens.

Deleting element from the head

Deleting the first element (or head) is a matter of removing all references to it.

Figure 6. Deleting an element from the head of the list

For instance, to remove the head (“art”) node, we change the variable first to point to the second node “dog”. We also remove the variable previous from the "dog" node, so it doesn’t point to the “art” node. The garbage collector will get rid of the “art” node when it sees nothing is using it anymore.

Linked List’s remove from the beginning of the list

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

As you can see, when we want to remove the first node, we make the 2nd element the first one.

Deleting element from the tail

Removing the last element from the list would require to iterate from the head until we find the last one, that’s O(n). But, if we have a reference to the last element, which we do, we can do it in O(1) instead!

Figure 7. Removing last element from the list using the last reference.

For instance, if we want to remove the last node “cat”. We use the last pointer to avoid iterating through the whole list. We check last.previous to get the “dog” node and make it the new last and remove its next reference to “cat.” Since nothing is pointing to “cat” it is out of the list and eventually is deleted from memory by the garbage collector.

Linked List’s remove from the end of the list

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

The code is very similar to removeFirst, but instead of first, we update last reference, and instead of nullifying previous, we nullify its next reference.

Deleting element from the middle

To remove a node from the middle, we make the surrounding nodes to bypass the one we want to delete.

Figure 8. Remove the middle node

In the illustration, we are removing the middle node “dog” by making art’s next variable to point to cat and cat’s previous to be “art,” totally bypassing “dog.”

Let’s implement it:

Linked List’s remove from the middle of the list

link:../../../src/data-structures/linked-lists/linked-list.js[role=include]

Notice that we are using the get method to get the node at the current position. That method loops through the list until it found the node at the specified location. This iteration has a runtime of O(n).

Linked List Complexity vs. Array Complexity

So far, we have seen two-liner data structures with different use cases. Here’s a summary:

Table 1. Big O cheat sheet for Linked List and Array

Data Structure	Searching By		Inserting at the			Deleting from			Space
	Index/Key	Value	beginning	middle	end	beginning	middle	end
Array	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(1)	O(n)
Linked List (singly)	O(n)	O(n)	O(1)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)
Linked List (doubly)	O(n)	O(n)	O(1)	O(n)	O(1)	O(1)	O(n)	O(1)	O(n)

If you compare the singly linked list vs. doubly linked list, you will notice that the main difference is inserting elements to and deleting elements from the end. For a singly linked list, it’s O(n), while a doubly-linked list is O(1).

Comparing an array with a doubly-linked list, both have different use cases:

Use arrays when:

• You want to access random elements by numeric key or index in constant time O(1).

• You need two-dimensional and multi-dimensional arrays.

Use a doubly linked list when:

• You want to access elements in a sequential manner only like part02-linear-data-structures.asc or part02-linear-data-structures.asc.

• You want to insert elements at the start and end of the list. The linked list has O(1) while array has O(n).

• You want to save some memory when dealing with possibly large data sets. Arrays pre-allocate a large chunk of contiguous memory on initialization. Lists are more “grow as you go.”

For the next two linear data structures part02-linear-data-structures.asc and part02-linear-data-structures.asc, we are going to use a doubly-linked list to implement them. We could use an array as well, but since inserting/deleting from the start performs better with linked-lists, we will use that.

Practice Questions

Merge Linked Lists into One

LL-1) Merge two sorted lists into one (and keep them sorted)

Seen in interviews at: Amazon, Adobe, Microsoft, Google

link:../../interview-questions/merge-lists.js[role=include]
  // write you code here
}

Solution: [linkedlist-q-merge-lists]

Check if two strings lists are the same

LL-2) Given two linked lists with strings, check if are the same

Seen in interviews at: Facebook

link:../../interview-questions/linkedlist-same-data.js[role=include]
  // write you code here
}

Solution: [linkedlist-q-linkedlist-same-data]