NextAI Labs
AI Research @ NextAI Labs
Subscribe to our newsletter for the latest AI trends and career insights.
AI Research @ NextAI Labs
If you've ever used an array, you know they're fast for looking things up. But what happens when you need to add an item right at the beginning? You have to shuffle everything else down—a slow and clunky process.
This is where the linked list shines. It's a fundamental data structure that's all about flexibility. Instead of a rigid, continuous block of memory, a linked list is more like a treasure hunt, where each item tells you exactly where to find the next one.
This tutorial will guide you through everything a beginner needs to know about linked lists.
A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, it consists of a sequence of nodes.
Each node is a small container with two parts:
The first node is called the head, and the next pointer of the last node points to null, signaling the end of the list.
The best way to understand the value of linked lists is to compare them to arrays.
| Feature | Arrays | Linked Lists |
|---|---|---|
| Memory | Stored in contiguous (touching) memory blocks. | Stored in non-contiguous memory; can be anywhere. |
| Element Access | Fast (O(1)). You can jump to any index instantly. | Slow (O(n)). You must traverse from the head to find an element. |
| Insertion/Deletion | Slow (O(n)). Adding/removing elements at the start or middle requires shifting all other elements. | Fast (O(1)). You just need to change a couple of pointers, no shifting required. |
| Size | Usually fixed. Resizing can be an expensive operation. | Dynamic. Can easily grow and shrink as needed. |
The bottom line: Choose arrays for fast access. Choose linked lists when you need fast insertion and deletion.
Linked lists come in a few flavors, but the two most common are singly and doubly linked lists.
This is the simplest form we've discussed so far. Each node has just one pointer: next.
Structure: Node(data, next)
Traversal: You can only move forward through the list, from the head to the tail. It's a one-way street.
Analogy: A conga line. Each person only knows who is directly in front of them.
A doubly linked list gives you more power by allowing two-way traversal. Each node has two pointers: next and previous.
Structure: Node(data, next, prev)
Traversal: You can move forward (next) and backward (prev) through the list.
Analogy: A web browser's history. You can go to the next page or the previous page.
Why use a doubly linked list? While it uses slightly more memory (for the extra prev pointer), it makes certain operations, like deleting a node, much easier because you don't have to manually track the previous node during traversal.
The best way to learn is by doing. Let's build a simple singly linked list from scratch and implement its core operations.
First, we define our building blocks.
# The Node class represents each element in the list
class Node:
def __init__(self, data):
self.data = data # The data value for the node
self.next = None # The pointer to the next node, initially None
# The LinkedList class manages the overall list structure
class LinkedList:
def __init__(self):
self.head = None # The head of the list, initially None
# A helper function to print the list
def print_list(self):
current_node = self.head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("None")This is the most efficient insertion operation for a linked list.
Complexity: O(1)
Logic: Create a new node, point its next to the current head, and then update the head to be the new node.
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_nodeYou need to traverse the entire list to find the last node.
Complexity: O(n)
Logic: If the list is empty, make the new node the head. Otherwise, go to the last node and point its next to the new node.
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_nodeTo delete a node, you find it and then "bypass" it by linking its previous node to its next node.
Complexity: O(n)
Logic: Search for the node containing the data. Keep track of the previous node. Once found, set previous.next = current_node.next.
def delete_node(self, key):
current_node = self.head
# Case 1: The node to delete is the head
if current_node and current_node.data == key:
self.head = current_node.next
current_node = None
return
# Case 2: Search for the key, keeping track of the previous node
prev = None
while current_node and current_node.data != key:
prev = current_node
current_node = current_node.next
# If the key was not found
if current_node is None:
return
# Unlink the node from the list
prev.next = current_node.next
current_node = None| Aspect | Singly Linked List | Doubly Linked List |
|---|---|---|
| Memory Usage | Less (one pointer per node) | More (two pointers per node) |
| Traversal | Forward only | Forward and backward |
| Deletion | Harder (you need a separate pointer to track the previous node) | Easier (the node itself knows its previous node) |
| Use Cases | Implementing a stack, simple scenarios. | Implementing a music playlist, browser history (undo/redo), a deque. |
General Rule: Start with a singly linked list. Only upgrade to a doubly linked list if you have a clear need for backward traversal or more efficient deletions of arbitrary nodes.
Congratulations! You've just explored one of the most important data structures in computer science.
Key Takeaways:
The best way to truly understand a linked list is to build one yourself. Try adding new features like a reverse() method or a way to find the middle element.
NextAI Labs is at the forefront of AI research, specializing in natural language processing and multimodal learning. With a team of experts in computational linguistics and machine learning, we contribute to several open-source projects and publish papers on efficient representation learning. When not exploring the frontiers of AI, our team enjoys hiking and playing the piano.
Master the array data structure with our complete guide. Learn about fundamental operations, time complexity, key DSA patterns like Two Pointers and Sliding Window, and solve must-do problems for your next coding interview.
Read More →Join thousands of professionals learning cutting-edge AI skills with our specialized courses.