LINKED LIST

A linked list is a linear data structure consisting of a sequence of elements called nodes. Each node contains two parts: data and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not have contiguous memory allocation; instead, they use dynamic memory allocation.

Types of Linked Lists:

Singly Linked List: Each node has a single pointer that points to the next node in the sequence.
Doubly Linked List: Each node has two pointers - one that points to the next node and another that points to the previous node.
Circular Linked List: In a circular linked list, the last node's pointer points back to the first node, forming a circular structure.

Operations on Linked Lists:

Traversal: Iterating through the linked list to access or modify each node.
Insertion: Adding a new node to the linked list at a specified position (beginning, end, or middle).
Deletion: Removing a node from the linked list.
Search: Finding a specific element in the linked list.
Concatenation: Combining two linked lists into one.
Reversal: Reversing the order of nodes in the linked list.

Advantages of Linked Lists:

Dynamic Size: Linked lists can grow or shrink in size dynamically as elements are added or removed.
Memory Efficiency: Linked lists use memory efficiently as memory is allocated dynamically.
Insertion and Deletion: Insertion and deletion operations are efficient, especially in the middle of the list.

Disadvantages of Linked Lists:

Random Access: Random access to elements is inefficient since elements are not stored in contiguous memory locations.
Extra Space: Linked lists require extra memory to store pointers/references for each node.
Traversal Overhead: Traversing a linked list requires traversing each node sequentially, which can be slower than arrays for certain operations.

Implementation in Python:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

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

Example Usage:

llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.display()  # Output: 1 2 3

Linked lists are commonly used in various applications such as implementing stacks, queues, and hash tables, and for representing sparse matrices and graphs. They provide flexibility and efficient memory usage, making them suitable for many dynamic data storage needs.

DatastructureARRAYS

DatastructureSTACK