Understanding Linked Lists

A linked list is a linear data structure, consisting of a collection of nodes, each pointing to the next node by means of a pointer. It is widely used in computer science due to its efficiency in certain operations, such as insertion and deletion.

Basic Structure

A node in a linked list typically contains:

• Data: The information stored in the node.
• Next: A pointer to the next node in the list.

Types of Linked Lists

• Singly Linked List: Each node has a single link pointing to the next node.
• Doubly Linked List: Each node has two links, one pointing to the next node and the other to the previous node.
• Circular Linked List: The last node in the list points to the first node, making the list circular.

Operations on Linked Lists

• Insertion: Adding a new node to the list.
• Deletion: Removing a node from the list.
• Traversal: Visiting each node in the list.
• Search: Finding a node in the list.
• Merge: Combining two lists.

Example Code

Here is a simple example 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 insert(self, data):
        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 display(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        return ' -> '.join(map(str, elements))

# Usage
linked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)

print(linked_list.display())  # Output: 1 -> 2 -> 3

For more information on linked lists and their implementations, check out our Data Structures tutorial series.

Image

Linked List