A linked list is a common and fundamental Abstract Data Type in computer science. It consists of nodes that point to other nodes of the same type, forming a chain:
When to Use Linked Lists
A linked list is often used in the implementation of other data structures, such as stacks, queues, and hash maps.
Let's take a look at the time complexity of common operations for linked lists:
The core of a linked list is a Node class, which can look like this:
class Node:
def __init__(self, value=None):
self.value = value
self.next = None
To make a linked list, you can create a series of Node objects and link them together using their next attribute:
task = Node("get dressed")
task.next = Node("go to work")
print(task.value) # get dressed
print(task.next.value) # go to work
In practice, you usually interact with a linked list using a LinkedList class rather than directly interacting with Node objects. The LinkedList class provides methods for adding and removing items from the list.
Dynamic Data Structure
A linked list is a dynamic data structure. This means that it can grow and shrink to fit the use case. It doesn't have size restrictions or sizing implications like other data structures. However, as a result of its structure, it also doesn't allow direct random access to any element. To find an element in a linked list, you must start at the head node and traverse the list until you find the element that you're looking for. This is why the worst time complexity for access and search lies at $`O(n)`$.
Head Node
When working with a LinkedList, the only node that you must always keep track of is the head node. The head node is the first node in the linked list. As long as you have access to the head node, you have access to the entire linked list that follows it. If you lose track of the head node, then you lose the possibility to access the linked list.
Info: Even if you saved a reference to a node somewhere in the middle of the linked list to a variable, you won't be able to access any earlier nodes with a singly-linked list. The references in this data type only go one way, even though there are different implementations that also reference previous nodes.
Delete a Node
To delete an element from a linked list, you point the preceding element to the element after the one you want to delete. Imagine you're starting with a linked list that consists of four nodes:
a = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")
a.next = b
b.next = c
c.next = d
If you want to delete the element "B" from the linked list A -> B -> C -> D, then you can do that by pointing "A" to "C":
a.next = a.next.next
This works because a.next, which originally pointed to "B", has its own next attribute, which points to "C". So you're saying that you want a.next to point to whatever b.next is currently pointing to.
Types of Python Linked Lists
There are different types of linked lists:
- Singly-linked lists point only in one direction.
- Doubly-linked lists point in both directions, using both a
nextand aprev(orprevious) attribute. - Circular linked lists which exist both in the singly-linked and doubly-linked variants. Circularly linked lists differ from other linked lists in that the tail node points again to the head node, thereby creating a circle.
Linked lists have a time complexity of $`O(1)`$ for insertions and deletions at the front of the list. However, they have a time complexity of $`O(n)`$ for access and search operations. They are a useful data structure when you need to add and remove items frequently, and you don't need to access or search the list very often.
Addition Resources
- Explore CodingNomads Data Structures and Algorithms course
- Learn more about Linked Lists
- See another Python Linked List explanation and implementation
In the next lesson, you'll practice your Python OOP skills and learn more about the linked list data structure by building one yourself.
Summary: The Linked List in Python
- A linked list is a common and fundamental Abstract Data Type in computer science
- Linked lists consist of nodes that point to other nodes of the same type, forming a chain
- A linked list is often used in the implementation of other data structures, such as stacks, queues, and hash maps
- The core of a linked list is the
Nodeclass - The head node is the only
Nodeyou need to follow - Delete a node by pointing the preceding element to the element after the one you want to delete
Types of Linked Lists
- Singly-linked lists
- Doubly-linked lists
- Circular linked lists