After arrays, Linked Lists are one of the first taught Data Structures as the concepts presented within them serve as the basis for other node-based Data Structures. In fact, Data Structures such as stacks and queues especially mirror much of the functionality seen in Linked Lists.

Assumptions:

Knowledge of <a href="https://www.devmaking.com/learn/algorithms/big-o-notation/" target="_blank" style="color:inherit;">Big-O Notation</a>
Basic Programming proficiency

What is a Linked List?

A linked list is a linear Data Structure where the elements are "Linked' to one another in a chain of <strong>Nodes</strong>. A Linked List Node usually contains 2 pieces of information: it's value, and a pointer to the next node in the chain*.

> *There is a variation on Linked Lists called Doubly Linked Lists, where each node contains a "pointer" to the next node as well as the previous node.

The Node Class

As just mentioned, Linked Lists are a chain of nodes, where each node points to the next. Except for the instance of a Doubly Linked List, Linked List Nodes contain 2 elements: the value and the next node, and usually looks like this in programming languages:

 /* pseudo-code */
 class Node {
     // The value doesn't need to be an integer, it can be anything!
     int value;
     // Holds a (reference) to the next node in the linked list.
     Node next;
 }

And that's it! As you begin to explore more data structures, you might find that the term "node" is passed around often. In a nutshell, the node is at the center of most data structures like Linked Lists, Binary Trees, Graphs, and is utilized by certain hashing structures.

Conceptualizing Linked Lists

Imagine a group of strangers who are all in a single-file line. Each person has a piece of paper in their pocket with a number on it. The person in front, who we'll say is at the "head", wants to find out if someone in the line has a certain number in their pocket. However, each person can only talk to the next person in line.

The goal: To find out if someone in the line has the number 5.

To do this, the person in front would ask the next in line, and if that person does not have it, they ask the next in line behind them. This continues until someone in line says they have the number, or until we reach the end — the "tail" — of the line. This example shows two concepts of Linked Lists in action: a line where each person (the node) contains a number (the value) and can only talk to the next person in line (the next node), and the act of each person in the line asking one by one to find a person who has that value (searching).

Linked List Searching

As with unordered arrays, to find if a linked list contains a specific element, we must manually check each node against what we are searching for. One drawback of linked lists is that we cannot apply algorithms such as Binary Search like we can with arrays. However, other data structures such as Binary Trees are designed to be more efficient at those tasks.

In the best case scenario, searching a linked list is O(1), while at worst case is O(n). This is because at best, the element you're looking for might be at the beginning of the list, and at worst might be at the end of the list.

 /* pseudo-code */
 // The root (head) 'pointer' of the linked list.
 Node root;

 function contains(int key){
   // Create a temporary node to 'point' to an element.
   // Starting at the root node.
   Node tmp = root;
   // While there is another node in the list, keep going.
   while( tmp is not null ) {
     if(tmp.value equals key){
       // We found a match, so we return true.
       return true;
     }
     // Iterate to the next node.
     tmp = tmp.next;
   }
   // No match found, the list does not contain the key.
   return false;
 }

Linked List Insertion

How we go about inserting elements into a linked list can vary based on what type of insertion we want to perform. Most commonly, linked lists utilize two insertion functions, addFirst and addLast, and will additionally support more specific operations like addBefore and addAfter, which adds a node into a list after or before a specific value or node.

Add First

Adding a node to the beginning of the linked list follows a similar logic pattern to swapping two integers using a third temporary integer. Conceptually, to add a node to the beginning of the linked list, we want to create a new node, make its next node point to the root node of the linked list, and then assign that node as the new root of the linked list. The following pseudo code displays this in a mode programming-wise sense:

 /* pseudo-code */
 Node root;

 function addFirst(int value){
   Node newRootNode = new Node(value).
   newRootNode.next = root;
   // Assign the root reference to the new node.
   root = newRootNode;
 }

Here we can visualize what is occurring in this operation:

Add Last

When we add a node to the end of a linked list, all we need to do is start on the root node, and continuously look at the 'next' node until we find a node that doesn't have another node after itself. In some implementations of Linked List, in addition to having a root pointer, there will sometimes be an additional tail pointer that references the end of the list, which would make this an O(1) operation instead of the traditional O(n) operation. For example purposes though, lets assume we only have a root node.

 /* pseudo-code */
 // Our root reference.
 Node root;

 function addLast(int value){
   // Create a temporary node to traverse the list.
   Node tmpNode = root;
   // Iterate our temp node as long as it has a next node.
   while(tmpNode.next is not null){
     tmpNode = tmpNode.next;
   }

   // We are at the end of the linked list.
   // So, let's add a new node.
   tmpNode.next = new Node(value);
 }

Add After

Sometimes you'll have situations where you'll want to add a node between two nodes, and with that you can utilize functions like addAfter or addBefore. Some situations where you might want to add in an element after a specific node are when you are managing an ordered linked list (this makes searching a little more efficient at the cost of longer insertions, but hey, a lot of development is about making compromises!).

The logic behind Add After consists of checking the value of each node against a 'key' value, and if you get a match, then insert a new node after that node. However, there is one catch to this which is that if you are not careful about your operation, you can potentially lose your reference to the rest of the list! The correct approach in this case is to make sure that the new node's next node points to the rest of the list before making the node that we matched the key to point next to the new node.

 /* pseudo-code */
 Node root;

 // key is the integer we want to find, then add our value after it.
 function addAfter(int key, int value){
   Node tmp = root;
   if( root is null ){
     // Some will exit, some will insert a new node.
   }
   while(tmp.next is not null){
     if( tmp.value equals key){
       // Create a new node.
       Node newNode = new Node(value);
       // Ensure the rest of the list isn't lost.
       newNode.next = tmp.next;
       // Put the new node after the key node.
       tmp.next = newNode;
       return;
     }
   }
   // some will insert a new node at the end of the list
   // some will exit the loop without adding a new node if the key isn't found.
 }

> Some implementations vary about what to do if we do not find the key node, some will exit, others will add to the end of the list, some might even throw an exception!

What happens if we incorrectly swap node references?

> If we assign the next node to the new node before assigning the new nodes 'next', we would lose the rest of the linked list! In modern languages such as Java that take care of Garbage Collection for us, this would mean the remainder of the linked list would be removed from runtime, while in lower-level languages such as C, it would mean we've created a memory leak!

Here is what this method might look like expressed visually:

Add Before

While the logic behind adding an element before a specific element might seem similarly implemented compared to adding an element after a specific node, there is a little more nuance required. In a singly linked list (a regular Linked List), we only have the reference to the next node in the chain and not the previous. To compensate for this, we can maintain two temporary nodes while we traverse the list: the current node and the previous node.

> Note: for this pseudo code example, two base cases have been left out to demonstrate the main case. To see how to handle the base case of an empty root and the root is the value, check the implementations in the Source Code section.

 /* pseudo-code */
 Node root;

 function addBefore(int key, int value){
   // Cover the base cases

   // Main case:
   // Watch two nodes starting at the first two elements.
   Node tmpPrev = root;
   Node tmp = root.next;

   while( tmp is not null ){
     if( tmp.value equals key){
       // Add the new node before the key.
       Node newNode = new Node(value);
       tmpPrev.next = newNode;
       newNode.next = tmp;
       return;
     }
     // otherwise, iterate.
     tmpPrev = tmp;
     tmp = tmp.next;
   }
 }

Like before, some implementations will vary based on whether or not the element will only be added if the key exists within the list. Here's another graphic of what this might look like visually:

Linked List Deletion

Removing an element from a linked list requires that we keep the same things in mind as when adding an intermediary node into the list: to make sure that we don't lose any of the trailing nodes after the element we want to remove.

To remove an element from the linked list, we want to traverse the list, checking that the next node is not null. If the value of the next node is the value we are looking to remove, then we change the pointer so that the current node's next node is the node after the next.

 /* pseudo-code */
 Node root;

 function remove(int key){
   // Base cases (check source code section for implementation).

   // Main case:
   Node tmp = root;

   while( tmp.next is not null ){
     if( tmp.next.value equals key ){
       // Make the next node point to the next next node.
       tmp.next = tmp.next.next;
       return;
     }
     tmp = tmp.next;
   }
 }

To see what this looks like visually:

When to use Linked Lists:

Usually, linked lists will be used in preference to arrays. The main advantage that linked lists have over arrays is that they do not need a fixed size. For example, when creating an array in most languages, you must specify the size of the array prior to placing any elements in it. While there are ways to get pseudo-expandable arrays like copying the elements into a new array of a larger size, linked lists are preferred when you want to have variable sized array-like structures.

Pros:

Can be varied in size as is needed.
Adding and removing elements is in place and does not require us to perform array shifts.
Saves ourselves from most out of boundary errors that might be encountered with arrays.

Cons:

We Sacrifice array-indexing, requiring O(n) time to traverse, even in ordered linked lists.
A linked list of size N requires more memory than an array of size N.
We can only traverse in a single direction, making some algorithms impractical with (singly) linked lists.