Introduction to Linked Lists
Welcome to the world of linked lists, a fundamental data structure in computer science and an essential concept for any programmer. Unlike the built-in list in Python, which offers indexed access to its elements, linked lists introduce a different approach to storing and accessing data.
the image that depicts the concept of linked lists in contrast to the indexed list structure in Python.
Linked Lists vs. Python Lists
In Python, a list is a collection of elements stored in a contiguous block of memory, which allows for fast, indexed access to its contents – typically in O(1) time complexity. However, linked lists operate differently. They do not have indexes, and each element, known as a node, can be located anywhere in memory. These nodes are linked sequentially, with each node pointing to the next one, forming a chain of elements.
Here are sample source codes in Python that illustrate the difference between a built-in list and a linked list.
Python List Example:
# A Python list is a collection of elements stored in a contiguous block of memory.
# Here's how you can create and access elements in a Python list.
# Creating a list with some elements
python_list = [1, 2, 3, 4, 5]
# Accessing elements by index
first_element = python_list[0] # Accessing the first element
second_element = python_list[1] # Accessing the second element
# Printing elements
print(f"First element: {first_element}")
print(f"Second element: {second_element}")
# Output:
# First element: 1
# Second element: 2
Linked List Example:
# A linked list is a sequence of nodes where each node points to the next node in the list.
# Below is a simple implementation of a singly linked list in Python.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
if not self.head:
self.head = Node(data)
else:
current = self.head
while current.next:
current = current.next
current.next = Node(data)
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Creating a linked list and adding elements
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
linked_list.append(5)
# Displaying the linked list
linked_list.display()
# Output:
# 1 -> 2 -> 3 -> 4 -> 5 -> None
In the Python list example, elements can be accessed directly by their index, which is fast and efficient. In the linked list example, elements are accessed sequentially starting from the head of the list. Accessing elements by index is not possible in a linked list as they do not have a fixed index and are not stored contiguously in memory.
The Structure of a Linked List
The first node in a linked list is referred to as the ‘head’, and it marks the entry point to the list. The last node, called the ‘tail’, points to ‘None’, indicating the end of the list.
This structure allows for nodes to be efficiently added or removed without reorganizing the entire data structure, which can be advantageous over array-based lists when it comes to insertion and deletion operations.
Below is a sample source code in Python for a linked list with labels that explain the parts as discussed:
class Node:
# The 'Node' class creates individual elements of the linked list.
def __init__(self, data):
self.data = data # Data contained within the node
self.next = None # Reference to the next node, initialized to 'None'
class LinkedList:
# The 'LinkedList' class manages the entire list.
def __init__(self):
self.head = None # The 'head' is the first node in the list.
self.tail = None # The 'tail' is the last node in the list.
def append(self, data):
# The 'append' method adds a new node to the end of the list.
new_node = Node(data)
if not self.head:
# If the list is empty, the new node becomes both the head and the tail.
self.head = new_node
self.tail = new_node
else:
# If the list is not empty, the new node is added after the tail.
self.tail.next = new_node
self.tail = new_node # The new node becomes the new tail of the list.
def remove(self, data):
# The 'remove' method deletes a node from the list.
current = self.head
previous = None
while current:
if current.data == data:
if previous:
previous.next = current.next
else:
self.head = current.next
if current.next is None:
self.tail = previous
return
previous = current
current = current.next
def display(self):
# The 'display' method prints out the linked list elements.
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None") # Indicates the end of the list
# Example usage:
linked_list = LinkedList()
linked_list.append('Node 1')
linked_list.append('Node 2')
linked_list.append('Node 3')
# Display the list: Node 1 -> Node 2 -> Node 3 -> None
linked_list.display()
# Remove 'Node 2' from the list
linked_list.remove('Node 2')
# Display the list after removal: Node 1 -> Node 3 -> None
linked_list.display()
1 -> 2 -> 3 -> None
In this example, we define the Node class as the building block for our linked list, containing the data and a reference to the next node. The LinkedList class manages the list, which begins with the head node and ends with the tail node. The append method adds new nodes to the end of the list, updating the tail each time. The remove method allows for the deletion of nodes based on their data content. The display method is used to show the content of the list, indicating the end of the list with “None”.
Another implementations of a Linked List in Python
Here’s a different implementation of a singly linked list in Python that includes the ability to insert a new node at the beginning of the list and to remove a node by value:
class Node:
"""A single node of a singly linked list"""
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
"""A singly linked list"""
def __init__(self):
self.head = None
def append(self, data):
"""Append a node to the end of the list"""
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def prepend(self, data):
"""Insert a node at the beginning of the list"""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def remove(self, data):
"""Remove a node by value"""
current = self.head
previous = None
while current and current.data != data:
previous = current
current = current.next
if not current:
return None # The data is not in the list.
if not previous:
self.head = current.next # Remove the head node.
else:
previous.next = current.next # Bypass the current node.
def display(self):
"""Display the list"""
elements = []
current = self.head
while current:
elements.append(current.data)
current = current.next
print(" -> ".join(str(e) for e in elements) + " -> None")
# Example usage
linked_list = SinglyLinkedList()
linked_list.append('A')
linked_list.prepend('B')
linked_list.append('C')
linked_list.remove('B')
linked_list.display()
The output will be:
# Output will be: A -> C -> NoneIn this implementation, the Node class creates individual nodes, and the SinglyLinkedList class handles the linked list itself. We have methods to append nodes to the end, prepend nodes to the beginning, remove nodes by value, and display the contents of the list.
This code offers a basic demonstration of a singly linked list’s capabilities, including insertions at both the start and end of the list and deletion of a specific node.
Conclusion
Linked lists are a versatile and efficient way to store and manipulate data in programming. Their dynamic nature makes them ideal for applications where memory utilization and insertion or deletion efficiency are critical. As data structures are the backbone of effective programming, understanding linked lists is a valuable skill for developers.
