Have you ever wondered how linked lists work 💭? Imagine with me for a moment, you're planning a treasure hunt 🗺️, but instead of giving your friends all the directions at once, you leave them a series of hints. Each clue leads to the next location, but they can only find the next hint if they follow the instructions from the current one.
The first clue, hidden inside a book 📚, reads:
"Find the next hint where you store your shoes 👟."
Your friends head to the closet, where they find the next clue, which points them to another location. Each clue has two parts: a message and a pointer to the next spot. They follow the trail until the last clue, which directs them to the treasure 💎.
This treasure hunt is like a linked list:
- Each clue is like a "node" 📍.
- The message is the "data" in that node 📝.
- The pointer to the next location is the "next" reference ➡️.
- The first clue is the "head" 🏁, and the last clue is the "tail" 🏁.
Just like your friends can't skip ahead in the hunt, in a linked list, you traverse one step at a time, moving through each node in sequence.
In essence, working with a linked list is like guiding data through a digital treasure hunt! 🕵️♂️
Course Outline
- Introduction
- What is a Linked List?
- Common Terminologies
- Linked List vs Array
- Linked Lists in Memory
- Types of Linked Lists
- Operations on Linked Lists
- Applications of Linked Lists
- Conclusion
Introduction
In this article, we'll take a look at what a linked list is, the common terminologies associated with it, the difference between linked lists and arrays, how they are stored in memory, the types of linked lists, and the operations that can be performed on them. We won't be going into the implementation details until the next article where we'll be focusing on implementing a Singly Linked List using JavaScript.
What is a Linked List?
A Linked List is a data structure consisting of a sequence of elements (similar to an array but more efficient than arrays), where each element (called a node) is connected to the next element through a link or pointer. Each node contains at least two components (for singly linked list): 1. the data it stores and 2. a reference to the next node in the sequence. Unlike arrays, linked list elements can be placed anywhere in memory, not necessarily in contiguous locations. This non-contiguous storage makes linked lists more memory-efficient, especially when dealing with dynamic data. The elements are accessed sequentially by following the links from one node to the next, rather than by their physical placement in memory.
A big benefit with using linked lists is that nodes are stored wherever there is free space in memory 🧠, the nodes do not have to be stored contiguously right after each other like elements are stored in arrays. Another nice thing with linked lists is that when adding or removing nodes, the rest of the nodes in the list do not have to be shifted.
Common Terminologies
While dealing with linked lists, there are some common terminologies that you need to be familiar with. They are:
| Term | Description |
|---|---|
| Node | The basic building block of a linked list. It contains data and a pointer to the next node. |
| Head | The first node in a linked list. |
| Tail | The last node in a linked list. |
| Next Pointer | A pointer in a node that points to the next node in the linked list. |
| Previous Pointer | A pointer in a node that points to the previous node in the linked list. |
| Current Node | The node that is currently being pointed to by the next pointer. |
Linked List vs Array
Before we move further, it is important to understand the difference between linked lists and arrays. While both are linear data structures, they have different characteristics:
| Linked List | Array |
|---|---|
| Does not have a fixed size in memory | Has a fixed size in memory |
| Nodes are stored in random memory locations | Elements are stored in contiguous memory locations |
| Adding or removing nodes does not require shifting elements | Adding or removing elements requires shifting elements |
| Accessing and Searching for elements is sequential | Accessing and Searching for elements is random |
| Insertion and deletion are efficient | Insertion and deletion are less efficient |
Linked Lists in Memory
We've established that linked lists are more efficient than arrays but the question is WHY? 🤔 What makes linked list more efficient than arrays?
To understand this, let's take a look at how arrays and linked lists are stored in memory.
How Arrays are stored in Memory
When an array is created, the elements are stored in contiguous memory locations. The size of the array is fixed at the time of creation. What this means is that all the elements are stored next to each other in memory with a fixed size.
To understand this better, let's take a look at two different arrays of different lengths:
const shortArray = [1, 2, 3, 4, 5];
const longArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
From the above code, we can see that the elements of the array are stored in contiguous memory locations. The size of the array is fixed at the time of creation.
How Linked Lists are stored in Memory
In linked lists, nodes are stored wherever there is free space in memory. When a node is created, it is stored in a random memory location. The node contains a pointer to the next node in the list.
Linked lists are used in many scenarios, like dynamic data storage, stack and queue implementation or graph representation, to mention some of them.
Types of Linked Lists
There are three basic types of linked lists each having slight variations that make them unique:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Singly Linked List
In a Singly Linked List, each node points to the next node in the sequence. The last node points to null. That means you can only traverse the list in one direction (forward), since not node points to the previous node.
A singly linked list is the simplest kind of linked lists. It takes up less space in memory because each node has only one address to the next node, like in the image below.
Doubly Linked List
In a Doubly Linked List, each node points to both the next and previous node in the sequence. The last node points to null. That means you can traverse the list in both directions (forward and backward), since each node has a pointer to the previous node.
A doubly linked list has nodes with addresses to both the previous and the next node, like in the image below, and therefore takes up more memory. But doubly linked lists are good if you want to be able to move both up and down or left and right in the list.
Circular Linked List
In a Circular Linked List, the last node points to the first node, creating a circular loop. This structure is useful for scenarios where you want to traverse the list repeatedly.
A circular linked list is like a singly or doubly linked list with the first node, the "head", and the last node, the "tail", connected. A circular linked list can be either singly or doubly linked. Check out the images below to see how it look like.
Singly Circular Linked List >
Doubly Circular Linked List >
Operations on Linked Lists
There are four main operations that you can perform on a linked list, each with its own time complexity and level of difficulty:
- Insertion
- Deletion
- Searching
- Traversing
In our next article, we'll take a look at how to implement these operations in a Singly Linked List using JavaScript.
Applications of Linked Lists
Linked lists have a wide range of applications, including:
- Implementing stacks and queues
- Graph traversal algorithms
- Hash table implementation
- Undo/Redo functionality in text editors
- Managing free memory in computer systems
Conclusion
In this article, we've taken a look at what a linked list is, the common terminologies associated with it, the difference between linked lists and arrays, how they are stored in memory, the types of linked lists, and the operations that can be performed on them.
In our next article, we'll take a look at how to implement these operations in a Singly Linked List using JavaScript.
Stay Updated and Connected
To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:
Stay tuned and happy coding 👨💻🚀
Top comments (1)
I understand linked lists, how to implement them etc.... But...
I've been a professional developer for 30 years and have never once used one in a 'real' project, been asked about them in interviews, or asked an interviewee about them.