What is a Linked List?

A linked list is a fundamental data structure used in computer science to represent a sequence of elements. Unlike arrays, linked lists are dynamic in nature, allowing efficient insertion and deletion of elements. In a linked list, elements are not stored at contiguous memory locations, instead, each element (called a node) contains a reference (or link) to the next element in the sequence.

Types of Linked Lists

1. Singly Linked List: Each node contains data and a reference to the next node. Traversal is unidirectional.
2. Doubly Linked List: Each node contains data, a reference to the next node, and a reference to the previous node. Traversal can be bidirectional.
3. Circular Linked List: The last node points back to the first node, forming a circular structure. It can be singly or doubly linked.
4. Doubly Circular Linked List: A circular linked list with bidirectional traversal, where the last node points back to the first node, and the first node points to the last node.

Key Operations on Linked Lists

1. Insertion: Adding a new node to the linked list.
   • At the beginning.
   • At the end.
   • At a specific position.
2. Deletion: Removing a node from the linked list.
   • From the beginning.
   • From the end.
   • From a specific position.
3. Traversal: Accessing each node of the linked list.
   • Print all elements.
   • Search for an element.
4. Reversal: Reversing the order of the nodes in the linked list.

Here are some basic implementations of a singly linked list in C++, Java, and Python.

C++ Program to implement Linked List

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
};

// Function to print the linked list
void printList(Node* n) {
    while (n != NULL) {
        cout << n->data << " -> ";
        n = n->next;
    }
    cout << "NULL" << endl;
}

// Main function
int main() {
    Node* head = new Node();
    Node* second = new Node();
    Node* third = new Node();

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    printList(head);

    return 0;
}

Java Program to implement Linked List

class LinkedList {
    Node head;

    static class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }

    // Function to print the linked list
    public void printList() {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " -> ");
            n = n.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        list.head.next = second;
        second.next = third;

        list.printList();
    }
}

Python Program to implement Linked List

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

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

    def print_list(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("NULL")

# Main function
if __name__ == "__main__":
    llist = LinkedList()
    llist.head = Node(1)
    second = Node(2)
    third = Node(3)

    llist.head.next = second
    second.next = third

    llist.print_list()

Advantages of Linked Lists

1. Dynamic Size: Linked lists can grow and shrink in size dynamically, making them more flexible than arrays.
2. Efficient Insertions/Deletions: Insertions and deletions can be performed efficiently without the need to shift elements, as required in arrays.

Disadvantages of Linked Lists

1. Memory Overhead: Each node requires additional memory for storing the reference to the next node.
2. Sequential Access: Linked lists do not support direct access to elements. To access an element, one must traverse the list from the beginning.

When to Use Linked Lists

Linked lists are preferred over arrays when:

• Frequent insertions and deletions are required.
• The size of the data structure is unknown and can change dynamically.
• Memory overhead is not a primary concern.

Practice Problems on Linked Lists

1. Reverse a Linked List
   • Problem: Given a singly linked list, reverse the list.
   • Example: Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL
2. Detect a Cycle in a Linked List
   • Problem: Given a singly linked list, determine if it has a cycle.
   • Example: Input: 3 -> 2 -> 0 -> -4 (tail connects to node with value 2), Output: True
3. Merge Two Sorted Linked Lists
   • Problem: Merge two sorted linked lists into one sorted linked list.
   • Example: Input: 1 -> 2 -> 4, 1 -> 3 -> 4, Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
4. Remove Nth Node from End of List
   • Problem: Given a linked list, remove the n-th node from the end of the list.
   • Example: Input: 1 -> 2 -> 3 -> 4 -> 5, n = 2, Output: 1 -> 2 -> 3 -> 5
5. Find the Middle of the Linked List
   • Problem: Given a linked list, find the middle of the list.
   • Example: Input: 1 -> 2 -> 3 -> 4 -> 5, Output: 3

Frequently Asked Questions (FAQs)

Q1: What is the difference between a linked list and an array?

• A: Arrays have fixed sizes and allow direct access to elements, while linked lists have dynamic sizes and require sequential access to elements.

Q2: How is memory allocation different in linked lists compared to arrays?

• A: Linked lists allocate memory for each node dynamically, whereas arrays allocate a contiguous block of memory.

Q3: When should I use a doubly linked list over a singly linked list?

• A: Use a doubly linked list when you need to traverse the list in both directions or when you need to delete nodes from the list more efficiently.

Q4: Can linked lists be circular?

• A: Yes, in circular linked lists, the last node points back to the first node, creating a circular structure.

Q5: What are the advantages of using a linked list?

• A: Linked lists allow dynamic resizing and efficient insertions/deletions without the need to shift elements.

Q6: What are the disadvantages of using a linked list?

• A: Linked lists have memory overhead due to storage of references and do not support direct access to elements.

Q7: How do I detect a cycle in a linked list?

• A: You can detect a cycle using Floyd's Cycle-Finding Algorithm, also known as the tortoise and hare algorithm.

Linked lists are a versatile and dynamic data structure, offering efficient insertion and deletion operations. Understanding their structure and implementation is fundamental for tackling various computer science problems and optimizing data manipulation. Whether you're preparing for technical interviews or enhancing your programming skills, mastering linked lists is a valuable asset in your toolkit.