DSA Linked Lists

Welcome to TheCodingCollege.com, your go-to platform for mastering Data Structures and Algorithms (DSA). In this tutorial, we’ll dive into Linked Lists, a fundamental data structure that forms the building block of many complex algorithms.

What is a Linked List?

A Linked List is a linear data structure where elements, called nodes, are connected using pointers. Each node consists of two parts:

1. Data: Stores the actual value.
2. Pointer/Link: Points to the next node in the sequence.

Unlike arrays, linked lists do not store elements in contiguous memory locations, making them more flexible but slightly complex to manage.

Types of Linked Lists

1. Singly Linked List (SLL): Each node points to the next node, and the last node points to null.
2. Doubly Linked List (DLL): Each node has pointers to both the previous and the next nodes.
3. Circular Linked List: The last node points back to the first node, forming a circular chain.
4. Circular Doubly Linked List: Combines features of circular and doubly linked lists.

Advantages of Linked Lists

1. Dynamic Size: Can grow or shrink during runtime.
2. Efficient Insertion/Deletion: Adding or removing elements is faster compared to arrays, especially for large datasets.
3. No Wasted Memory: Allocates memory as needed.

Disadvantages of Linked Lists

1. Memory Overhead: Additional memory is required for storing pointers.
2. Sequential Access: Accessing an element requires traversing the list, making it slower than arrays for random access.
3. Complexity: Implementation is more complex compared to arrays.

Structure of a Node

In a Singly Linked List, each node contains:

• Data: The actual value.
• Next: A pointer to the next node.

Singly Linked List Implementation

Python Code:

class Node:
    def __init__(self, data):
        self.data = data  # Store data
        self.next = None  # Initialize the next pointer as None

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # Initialize the head of the list as None

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

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

# Example usage
sll = SinglyLinkedList()
sll.insert_at_end(10)
sll.insert_at_end(20)
sll.insert_at_end(30)
sll.display()

Output:

10 -> 20 -> 30 -> None

Java Code:

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    Node head;

    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        SinglyLinkedList sll = new SinglyLinkedList();
        sll.insertAtEnd(10);
        sll.insertAtEnd(20);
        sll.insertAtEnd(30);
        sll.display();
    }
}

Common Operations in Linked Lists

1. Insertion: Add a new node at the beginning, end, or a specific position.
2. Deletion: Remove a node from the beginning, end, or a specific position.
3. Traversal: Iterate through all the nodes in the list.
4. Search: Find whether a value exists in the list.
5. Reverse: Reverse the sequence of nodes.

Insertion at the Beginning (Python Example):

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

Applications of Linked Lists

1. Dynamic Memory Allocation: Useful in systems where memory usage varies.
2. Implementing Stacks and Queues: Often used to build these abstract data types.
3. Graphs: Representing adjacency lists in graph algorithms.
4. Operating Systems: Managing memory blocks, file allocation, etc.

Linked Lists vs Arrays

Conclusion

Linked Lists are a foundational concept in DSA, offering flexibility and efficiency in dynamic memory operations. While slightly more complex than arrays, their advantages make them indispensable in many scenarios. Explore more in-depth DSA tutorials and coding resources on TheCodingCollege.com. Stay tuned for advanced topics like Doubly Linked Lists and Circular Linked Lists!