search

What is a linked list in Python?

In Python, a linked list is a data structure used to store and manage a collection of elements. It consists of nodes where each node contains two parts: the data and a reference (or link) to the next node in the sequence. The last node typically points to None, indicating the end of the linked list.

Unlike arrays or lists, linked lists do not require contiguous memory allocation. Instead, each node can be dynamically allocated in memory and connected through the references. This flexibility allows for efficient insertion and deletion operations at the cost of slower random access.

Here's an example of a basic 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 is_empty(self):
        return self.head is None

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def append(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def delete(self, data):
        if self.is_empty():
            return
        if self.head.data == data:
            self.head = self.head.next
            return

        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

In this implementation, we have two classes: Node and LinkedList. The Node class represents a single node with its data and a reference to the next node. The LinkedList class serves as the container for managing the linked list.

The LinkedList class provides various methods:

  • is_empty(): Returns True if the linked list is empty, False otherwise.
  • prepend(data): Adds a new node with the given data at the beginning of the linked list.
  • append(data): Adds a new node with the given data at the end of the linked list.
  • delete(data): Removes the node containing the given data from the linked list, if present.
  • display(): Prints the contents of the linked list.

Here's an example usage of the linked list implementation:

linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.prepend(0)
linked_list.delete(2)
linked_list.display()

Output:

0 -> 1 -> 3 -> None

Linked lists are versatile data structures and can be used to efficiently implement other data structures like stacks, queues, and graphs. They provide dynamic memory allocation, efficient insertion and deletion operations, and are particularly useful in situations where frequent modifications to the collection of elements are required.

Related Questions You Might Be Interested