A Beginner’s Guide to the Linked List Data Structure
As a Full-Stack Web Development bootcamp graduate, I’ve been preparing for interviews and have been studying all of the major data structures and their various applications. Some, such as hashes and arrays, were already familiar to me through my coursework at Lighthouse Labs. Others were less familiar or entirely new. In my opinion, one of the most confusing data structures is linked lists. I’ll sum up my research of linked lists and share some real-world examples and information that helped me wrap my head around them. For better explanation in this post, we will be using Python programming language for demonstration of exercises.
What is a data structure and how many types of data structures are there?
“A data structure is a collection of data type ‘values’ which are stored and organized in such a way that it allows for efficient access and modification.”
— Mark McDonnell
We, as software engineers, divide data structures into 4 main categories:
- Linear: arrays, lists
- Tree: binary, heaps, space partitioning etc.
- Hash: distributed hash table, hash tree etc.
- Graphs: decision, directed, acyclic etc.
Let’s dive deep into the lists data structure and see how useful it can be in our day-to-day lives.
A linked list is a linear data structure that contains a sequence of nodes, in which each node contains data and a pointer to another node. The most commonly used instance is a singly linked list, where each node contains a piece of data and a pointer to the next list, as shown in the diagram below.
The main difference between a linked list and an array is that you can access an array by pointing at its index. For example, to display the value of element C we would write
import logginglogging.debug(arr); // output: C
Unfortunately, this method is impossible to achieve in a linked list. In order to access an element in a linked list, we would have to traverse the linked list and continue to access the next value of every single node until we reach our desired element.
Another popular version of a linked list is a doubly linked list. Each node in a doubly-linked list contains a path to the previous node:
How to define a node class in linked list:
# Node class
class Node:# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null# Linked List class
# Function to initialize the Linked List object
self.head = None
Pros and Cons of Using Linked Lists
When I first encountered this data structure type, I just couldn’t see the benefits of using linked lists. The fact that I had to traverse the entire list to access a single element seemed time-consuming at the time. What I haven’t considered is the efficiency of linked lists when it comes to memory and storage.
Arrays are fixed in size, which means that the number of elements used has to be explicitly defined before storing the array. This often creates extra memory that is not used since the limit of elements is never reached. In addition, computers initialize a new object in memory if the limit of elements is exceeded.
Another feature that makes linked lists superior is insertion of a new data element. If you want to insert a new string
'B'into an array
['A', 'C', 'D'], you would have to move both ‘C’ and ‘D’ elements by an item, so you can insert ‘B’ in between strings ‘A’ and ‘C’. This trait that belongs to arrays make insertion a costly operation in terms of memory.
In a linked list, on the other hand, an individual can simply create a new node with the value
data: 'B' that points to the node with the value of ‘C’. This is a much cost-effective approach when it comes to data insertion.
Even though linked lists are so useful, there are scenarios where using them can be inefficient. For example, accessing a specific value of a linked list is more costly in terms of time than in arrays because we have to traverse the whole list until it reaches our desired value.
It’s imperative to grasp the advantages and cons of linked lists when you’re considering whether or not to use them in a project.
G. (2021, February 03). Linked List vs Array. Retrieved from https://www.geeksforgeeks.org/linked-list-vs-array/
Data Structure and Algorithms — Linked List. (n.d.). Retrieved from https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm
What is the advantage of linked list over an array and vice versa? Retrieved from https://stackoverflow.com/questions/7496251/what-is-the-advantage-of-linked-list-over-an-array-and-vice-versa