A dummy’s guide to Linked Lists: Part 1
Hello reader! Data structures are one of the most fundamental concepts in computer science. They essentially determine the way we persist and manage data within our software applications.
Some of the common data structures you may have come across are arrays, stacks, and hash tables. Each of them has different implementations and they perform well in different scenarios.
In this article, I will be sharing with you a data structure called linked list. It forms the basis of more complex structures like hash tables and trees.
My goal is to build/strengthen your fundamental understanding of a linked list. Before writing any code related to a linked list, it is important for you to know its building block like the back of your hand.
I assume you have been exposed to basic programming concepts like arrays and variable assignments. Knowledge about pointers and memory representation would be beneficial (but not necessary).
Let’s get started! 🏃
What is a Linked List?
Linear vs Non-Linear Data Structure
Like an array, a linked list is a linear data structure. A linear data structure is one where its elements are arranged sequentially in order.
On the other hand, the elements of a non-linear data structure are not arranged in any order, i.e. non-sequentially.
Memory Representation
A linked list differs from an array in the way that it stores data in memory. Unlike an array, it is NOT necessary for the elements of a linked list to be placed next to each other.
To help you understand the statement above, I have magically created my own programming language that implements Array and LinkedList.
# For demonstration purposes only
# Both array and linked_list stores numbers 1 to 5array = Array<1, 2, 3, 4, 5>linked_list = LinkedList<1, 2, 3, 4, 5>
Underneath the hood, when array of five elements is created, five blocks of memory will be allocated to it. These memory blocks are contiguous, which is just a formal way of saying they are next to each other.
On the other hand, when linked_list is created, its elements will be scattered around in a pool of memory. The memory blocks assigned to linked_list do not have to be contiguous.
An array has a contiguous block of memory because its size must be determined at compile-time, i.e. before the program runs. It cannot grow and shrink freely when the program is running. In formal terms, an array is a static data structure.
On the other hand, the size of a linked list does not have to be predetermined. It can grow and shrink freely. New memory can be added to it at runtime, i.e. when the program is running. This makes linked list a dynamic data structure.
Node and Pointer
Wait… if the elements of a linked list are scattered around in memory, how is it a data structure? There is no “structure” at all!
Unlike an array, a linked list stores more than just the data of interest. Each element of a linked list is called a node. A node is made up of two parts: one part holds the data and the other holds a pointer.
A pointer is nothing more than an address that points to a specific block of memory. You can think of it as a house number in your neighborhood. Bob’s house is located at no. 101, Bob Street. 101 is the pointer to Bob’s house.
The nodes in a linked list connect to each other sequentially with pointers. This forms a chain of nodes, which is what a linked list is all about. In the example below, node 1 has a pointer of 107 as it is pointing to node 2 that lives on memory 107.
This looks more like a data structure! If I trace my linked list starting from the first element, I would be able to access every single element after that by following the pointers. It feels almost like the “connect the dots activity” for children!
Head and Tail
Now that we know how a linked list is represented, how do we work with it? To be specific, in the code below, what is assigned to the variable linked_list?
# For demonstration purposes onlylinked_list = LinkedList<1, 2, 3, 4, 5>
Unlike an array, we cannot directly access the elements in a linked list. Instead, we need to step into the linked list, node by node, starting from the head node.
A head node is the first node of a linked list. When we create a linked list, we must be given access to a head pointer, which is just a pointer to the head node. Without it, you won’t be able to access the data in a linked list.
You can think of a head pointer as your hand holding a string of items. If you let go (i.e. lose head pointer), you will lose all your items!
Meanwhile, the last node of a linked list is called a tail node. A tail node is special in the sense that it points to nothing. In some programming languages, this can be interpreted as pointing to null, or a null pointer.
Linked Lists Upgrades
Combining the concepts above, we can finally create our first linked list. This is the simplest variation of a linked list and it is known as a singly linked list.
Looking at the linked list above, how can we improve it? What are its limitations?
Doubly Linked List
Notice the direction of arrows in a singly linked list.
The pointers are unidirectional. A node has only a pointer to the next node, not the node before. Hence, we can only move forward in one direction, which restricts our flexibility in traversing through the list.
To support bidirectional movement, we can give our list node an upgrade. Instead of storing only the pointer to the next node, the node will also store a pointer to the previous node.
Nodes with two pointers create a doubly linked list. In a doubly linked list, we can move forward and backward flexibly from one node to another. Note that the “previous pointer” of the head node points to null.
Tail Pointer
To access a node in a singly linked list, we must start from the head node pointed by the head pointer. If we wish to access the tail node, we need to step through the nodes one by one until the end.
This could be costly if the list is extremely long!
To solve this problem, we can add another entry point to our linked list. In fact, it is common to add a tail pointer that points to the tail node! With that, we can enter a linked list at the front and back.
A tail pointer can be added to a doubly linked list as well, which makes the linked list versatile to different requirements. A tail pointer is extremely useful in optimizing several linked list operations, which we will discuss in Part 2 of this series.
Circular Linked List
To be honest, I have never worked with a circular linked list before, but it is still worth a mention. It is an advanced variation of linked list where the tail node points to the head node instead of null.
In the case of a circular, doubly linked list, the head node also has a pointer that points to the tail node.
Final Thoughts
In this article, I have explained the building blocks of a linked list and the upgrades that they can receive.
A linked list is more complex than an array since it involves pointers. As you can imagine, working with a linked list requires you to think creatively in handling these nasty pointers.
But don’t worry! Fret not — in Part 2 of this series, I will be diving deep into the operations you can perform on a linked list (adding a node, deleting a node, etc) using pointers.
I hope you are as excited as me, so stay tuned!
Thank you for reading. Peace ✌️!
