Data Structures: Linked Lists — Behind the Scenes Visual Tour

Powerful Data Structures for Developers.

👋 Meet Linked Lists!

Welcome to the world of Linked Lists! These are awesome data structures that waste no memory and let you add and remove nodes extremely efficiently from the beginning and end of the list.

Sounds exciting, right? Let’s begin! 🎆

✅ The Building-Blocks

The basic building-blocks of a linked list are:

• Nodes: they represent the elements stored in the list. You can create Nodes using Object-Oriented Programming. First, you need to define a Node class and then create an instance for each Node that you want to include in the linked list.

Sample Node Class in Python. More Details on self.next Below :)

• Links Between Nodes Via Pointers: one the main characteristics of Linked Lists is that Nodes are connected via pointers. Each node stores a reference to its “neighbors” so they can be accessed easily and sequentially.

Without pointers, nodes are not connected.

Pointers create the magic of linked lists.

For example, in the Linked List shown above, the green node in the middle would have these two attributes (defined in the Node class):

self.next # Pointer to the right node (next node)(blue node)
self.prev # Pointer to the left node (previous node)(purple node)

💡 Note: Using Python, the HEAD node would have None as self.prev because since it’s the first node in the list, it doesn’t have a node located immediately to its left. Similarly, the TAIL node would have None as self.next because it doesn’t have a node located immediately to its right.

This way, you can go from one node to another (traverse the list) using the pointers that connect them until you find the node that you are looking for.

✅ Advantages of Linked Lists 😃

• It takes constant time ❤️ O(1) to insert or remove elements at the beginning and end of the list. This means that even if the list gets really large, the time required to perform these operations will not increase! 🎆
• No memory is wasted, in contrast with Arrays in which memory is allocated even before storing new data causing it to be underutilized until it’s full. With Linked Lists, you create nodes dynamically when they are needed and only rearrange the pointers to update the data structure.

✅ Disadvantages of Linked Lists 😢

• It takes linear time 💔 O(n) to find an element (even if the list is sorted) because the elements are not stored contiguously in memory; therefore, you need to go through the list sequentially until you find the element you are looking for or reach the end of the list if the element doesn't exist.

✅ Types of Linked Lists

• Singly-Linked Lists: In this type of Linked List, nodes only have a pointer pointing to the node that is located immediately to their right (notice the arrows in the diagram below). Therefore, the list can only be traversed (read) in ONE direction.

• Doubly-Linked Lists: In this type of Linked List, nodes have pointers to the nodes located immediately to their left (before) and to their right (after). Therefore, the list can be traversed in BOTH directions, starting from HEAD or from TAIL.

✅ Linked List Attributes

You should keep a reference to the head and tail nodes in your LinkedList class to insert new nodes very efficiently at these positions.

class LinkedList(object):
      def __init__(self):
           self.head = None // Keep a reference to the HEAD node
           self.tail = None // Keep a reference to the TAIL node

✅ Inserting a Node

How would you insert a node into a linked list? Let’s see the logic in detail!

Inserting?

There are three cases for insertion:

• HEAD: Make the new node the HEAD node by rearranging the pointers.
• TAIL: Make the new node the TAIL node by rearranging the pointers.
• Middle: Traverse the list until you reach the node that will become the PREVIOUS node after the insertion (you will see why in the diagrams below) and then update the necessary pointers.

Update the Pointers:

Let’s say that you want to insert a node at index 2 of a doubly-linked list. See the diagrams below as you read the explanation to have a visual intuition of the process 👍.

• First, you reach the node at index 1 (green node) using the existing pointers. This is the node that is located immediately before the insertion site.

Step 1. Reach the previous node (index 1, green node).

• Then, you start updating the pointers. You will need to use the existing pointers from the green node, so let’s see this in more detail!

Step 2

1️⃣ New Node

• The blue node used to be self.next for the green node because they were directly connected. But now the blue node will be self.next for the new node (yellow node) because it will be located immediately to its right. The green node will no longer be directly connected to the blue node after the insertion.
• The green node will now be self.prev for the new node (yellow node) because after the insertion, the green node will be located immediately to the left of the yellow node (see the diagram below).

2️⃣ Green Node

• You will also need to update the pointers of the green node. self.next for this node will now be the new node (yellow) because it will be located immediately to its right.

3️⃣ Blue Node

• Finally, self.prev for the blue node must be updated to point to the new node (yellow node) because the yellow node will now be immediately to its left.

Final Linked List After Insertion

✅ Finding an Element

To find an element, you start from the HEAD node and compare the value of each node with the value that you want to find until you reach the node you seek or until you reach the TAIL node and return a specific value that you define to indicate that the element was not found.

💡 Note: If you have a doubly-linked list, like in the diagrams above, you can start from the TAIL as well and traverse the list until you reach HEAD.

Diagram of the Process of Finding an Element in a Singly-Linked List

✅ Removing an Element

To remove an element, you first reach the index that is located immediately before the deletion site. Let’s see how we can remove the node at index 2 in the diagram below. 👍

👉 Rearranging Pointers

• self.next for the green node will now point to the yellow node because we are removing the blue node that is in between.
• self.prev for the yellow node needs to be updated to point to the green node as well.
• This way, as you can see in the diagrams below, the blue node is no longer connected to the Linked List and was successfully removed!

Original Linked List.

Rearranging Pointers.

Final Linked List After Removal.

💡 Note: You will need to make sure that the node that you just removed is also removed from memory; otherwise, it could cause a memory leak because you are only rearranging the pointers to remove it from the data structure. We are not actually deleting the node itself, we are “isolating” it from the data structure so it won’t be accessed when the list is traversed (read).

✅ Last, But Not Least… Linked Lists in Context!😉

❤️ Data Structures are really awesome. You want to use Linked Lists for operations that require inserting and/or removing from the end and/or start of the list.

Each data structure has unique advantages and disadvantages, and you need choose the appropriate one(s) for your project. For example, Doubly-Linked Lists are used to implement Double-Ended Queues or Deques (used to implement Stacks and Queues). They use the advantages that Linked Lists provide: constant-time insertion and deletion operations at the start and end of the list.

Here are some interesting discussions on the applications of Linked Lists:

• When would you use a linked list? — Quora
• In which cases should I prefer a linked list over any other data structure? — Quora
• What is an application of linear linked list data structures? — Quora

Keep exploring these awesome data structures and dive deeper into the wonderful world of computer science! 😍

👋 Thank you for reading my article!

I really appreciate your claps 👏👏👏 if you liked my article and you would like to see more! 😃 Follow Techmacademy on Medium | Twitter