Linked Lists

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

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

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

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

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

def insert_at_beginning(linked_list, value):
    new_node = Node(value)
    new_node.next = linked_list.head
    linked_list.head = new_node