Introduction to Linked List

What is a Linked List?

A linked list is a linear data structure consisting of a sequence of elements called nodes. Each node contains two components: data and a reference (or link) to the next node in the sequence. The last node in the list typically has a reference pointing to null to indicate the end of the list.

Unlike arrays, linked lists do not require contiguous memory allocation. Each node can be located anywhere in memory, and the links between nodes facilitate traversal through the list.

There are different types of linked lists, such as singly linked lists, doubly linked lists, and circular linked lists, each with its own variations in terms of the number of links and the direction of traversal.

Implementation of Linked List

Here's an example of a basic Node class in Python:

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

In this example, the Node class has two attributes: data to store the value of the node, and next to store the reference to the next node. The next attribute is initially set to None to indicate the end of the list.

To construct a linked list, you create instances of the Node class and establish the connections between nodes using the next references. The first node of the list is called the head node, and it serves as the starting point for traversing the list.

Here's an example of creating a linked list with three nodes:

# Create nodes

node1 = Node(10)

node2 = Node(20)

node3 = Node(30)


# Establish connections

node1.next = node2

node2.next = node3

Linked List Operation(Insert, Delete, Display)

Here's a general 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 insert_at_head(self, data):

        new_node = Node(data)

        new_node.next = self.head

        self.head = new_node


    def insert_at_tail(self, data):

        new_node = Node(data)

        if self.is_empty():

            self.head = new_node

        else:

            current = self.head

            while current.next is not None:

                current = current.next

            current.next = new_node


    def delete_at_head(self):

        if self.is_empty():

            raise Exception("Linked list is empty")

        self.head = self.head.next


    def display(self):

        current = self.head

        while current is not None:

            print(current.data, end=" ")

            current = current.next

        print()

In this example, the Node class represents a node in the linked list, containing the data and a reference to the next node. The LinkedList class represents the linked list itself, with methods to perform various operations.

Here are the operations implemented in the example:

is_empty(): Checks if the linked list is empty.

insert_at_head(data): Inserts a new node with the given data at the beginning of the linked list.

insert_at_tail(data): Inserts a new node with the given data at the end of the linked list.

delete_at_head(): Deletes the node at the head (beginning) of the linked list.

display(): Displays the elements of the linked list.


Here's an example usage of the linked list:

my_list = LinkedList()


my_list.insert_at_head(10)

my_list.insert_at_head(20)

my_list.insert_at_tail(30)


my_list.display()  # Output: 20 10 30


my_list.delete_at_head()


my_list.display()  # Output: 10 30