Linked lists are a fundamental data structure commonly used in computer science. They are an ordered collection of data elements, each containing a link to its successor. Linked lists are used to efficiently store and manipulate data in a variety of applications, such as web browsers, databases, operating systems, and graphics applications.
In this article, we will discuss linked lists in the context of the course Data Structures and Algorithms with Python. We’ll start by looking at the basics of linked lists, and then move on to discuss how to implement linked lists using classes. We’ll also cover singly linked lists, doubly linked lists, traversing linked lists, inserting and deleting elements from linked lists, and skip lists.
Overview of Linked Lists
Linked lists are a type of data structure that allows data elements to be stored and manipulated in an ordered collection. Each element in a linked list is known as a node, and each node contains two pieces of information: a data element and a link to the successor node. The first element in a linked list is known as the head, and the last element is known as the tail.
Linked lists are a dynamic data structure, meaning that their size can change at runtime. They are also very efficient, as the time required to access, insert, or delete an element is independent of the size of the list. This makes linked lists well suited for applications where frequent insertions and deletions are needed.
Implementing Linked Lists Using Classes
In Python, linked lists can be implemented using classes. The following code shows an example of how a linked list can be implemented using a class.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
The Node class is responsible for storing the data element and the link to the successor node. The LinkedList class is responsible for managing the list of nodes. It stores a reference to the head node, which is the first element in the linked list.
Singly Linked Lists
A singly linked list is a type of linked list where each node contains a link to its successor, but not to its predecessor. This makes it a one-way data structure, as elements can only be traversed in one direction.
A singly linked list can be implemented using the following code:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
The SinglyLinkedList class is similar to the LinkedList class, but it stores a reference to the head node instead of the head node itself. This makes it easier to add and remove elements from the list.
Doubly Linked Lists
A doubly linked list is a type of linked list where each node contains a link to both its successor and its predecessor. This makes it a two-way data structure, as elements can be traversed in both directions.
A doubly linked list can be implemented using the following code:
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
The DoublyLinkedList class is similar to the SinglyLinkedList class, but it stores a reference to the head and tail nodes instead of the head and tail nodes themselves. This makes it easier to add and remove elements from the list.
Traversing Linked Lists
Traversing a linked list involves iterating through all of its elements. This can be done in either a forward or backward direction, depending on the type of linked list being used.
In a singly linked list, elements can be traversed in a forward direction using a while loop. The following code shows an example of how this can be done:
# Traverse a singly linked list
current_node = linked_list.head
while current_node is not None:
# Do something with the current node
current_node = current_node.next
In a doubly linked list, elements can be traversed in either a forward or backward direction using a while loop. The following code shows an example of how this can be done:
# Traverse a doubly linked list forward
current_node = linked_list.head
while current_node is not None:
# Do something with the current node
current_node = current_node.next
# Traverse a doubly linked list backward
current_node = linked_list.tail
while current_node is not None:
# Do something with the current node
current_node = current_node.prev
Inserting and Deleting Elements from Linked Lists
Inserting and deleting elements from linked lists can be done in constant time, regardless of the size of the list. This makes linked lists well suited for applications where frequent insertions and deletions are needed.
In a singly linked list, elements can be inserted and deleted from the head or tail of the list. The following code shows an example of how this can be done:
# Insert a new element at the head
new_node = Node(data)
new_node.next = linked_list.head
linked_list.head = new_node
# Delete the element at the head
linked_list.head = linked_list.head.next
In a doubly linked list, elements can be inserted and deleted from any position in the list. The following code shows an example of how this can be done:
# Insert a new element at a given position
new_node = Node(data)
new_node.next = current_node
new_node.prev = current_node.prev
current_node.prev.next = new_node
current_node.prev = new_node
# Delete an element at a given position
current_node.prev.next = current_node.next
current_node.next.prev = current_node.prev
Skip Lists
A skip list is a type of linked list that allows for efficient searching and traversal. It is a randomized data structure, meaning that its elements are stored in a random order. This makes it well suited for applications where frequent searches are needed.
In a skip list, each node contains multiple links to other nodes. This allows for faster search times, as the search can be done in multiple directions at the same time. The following code shows an example of how a skip list can be implemented using a class:
class SkipListNode:
def __init__(self, data):
self.data = data
self.next = [None] * MAX_LEVEL
class SkipList:
def __init__(self):
self.head = None
Conclusion
In this article, we discussed linked lists in the context of the course Data Structures and Algorithms with Python. We looked at the basics of linked lists, and then discussed how to implement them using classes. We also covered singly linked lists, doubly linked lists, traversing linked lists, inserting and deleting elements from linked lists, and skip lists.
Linked lists are a powerful data structure that can be used to efficiently store and manipulate data. They are a dynamic data structure, meaning that their size can change at runtime, and they are also very efficient, as the time required to access, insert, or delete an element is independent of the size of the list.
Exercises
Write a function that takes a linked list and returns the length of the list.
def get_length(linked_list):
current_node = linked_list.head
length = 0
while current_node is not None:
length += 1
current_node = current_node.next
return length
Write a function that takes a linked list and returns the middle element of the list.
def get_middle(linked_list):
slow_node = linked_list.head
fast_node = linked_list.head
while fast_node is not None and fast_node.next is not None:
slow_node = slow_node.next
fast_node = fast_node.next.next
return slow_node
Write a function that takes a linked list and a value, and deletes all nodes with the given value from the list.
def delete_value(linked_list, value):
current_node = linked_list.head
prev_node = None
while current_node is not None:
if current_node.data == value:
# Delete the node
if prev_node is not None:
prev_node.next = current_node.next
else:
linked_list.head = current_node.next
else:
prev_node = current_node
current_node = current_node.next
Write a function that takes a linked list and a value, and inserts a new node with the given value at the end of the list.
def insert_at_end(linked_list, value):
new_node = Node(value)
if linked_list.head is None:
linked_list.head = new_node
return
current_node = linked_list.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = new_node
Write a function that takes a linked list and a value, and inserts a new node with the given value at the beginning of the list.
def insert_at_beginning(linked_list, value):
new_node = Node(value)
new_node.next = linked_list.head
linked_list.head = new_node