Day 6: Basic Data Structures – Linked Lists

Linked lists are a fundamental data structure that offers a dynamic way to store a collection of elements. Unlike arrays, linked lists are not contiguous in memory, which allows for efficient insertions and deletions. In this post, we’ll explore the types of linked lists, basic operations, and provide example problems, including finding the middle of a linked list.

Explanation of Linked Lists

A linked list is a collection of nodes where each node contains two components:

  1. Data: The value stored in the node.
  2. Next: A reference (or pointer) to the next node in the sequence.

Types of Linked Lists

  1. Singly Linked List: Each node points to the next node, with the last node pointing to null. This allows for traversal in one direction.
  2. Doubly Linked List: Each node has two pointers: one to the next node and another to the previous node. This allows for traversal in both directions.

Basic Operations

  1. Insertion: Adding a new node to the linked list. This can be done at the beginning, at the end, or at a specific position.Implementation in Java (Singly Linked List)javaCopy codeclass Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } class SinglyLinkedList { Node head; public void insertAtBeginning(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } public void insertAtEnd(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; return; } Node current = head; while (current.next != null) { current = current.next; } current.next = newNode; } }
  2. Deletion: Removing a node from the linked list. This can also be done at the beginning, end, or at a specific position.Implementation in Java (Singly Linked List)javaCopy codepublic void deleteNode(int key) { Node current = head; Node previous = null; // If head node itself holds the key if (current != null && current.data == key) { head = current.next; // Changed head return; } // Search for the key to be deleted while (current != null && current.data != key) { previous = current; current = current.next; } // If key was not present in linked list if (current == null) return; // Unlink the node from linked list previous.next = current.next; }

Example Problem: Finding the Middle of a Linked List

A common problem is to find the middle node of a linked list. This can be efficiently done using two pointers: one moving at normal speed and the other at double speed.

Implementation in Java

javaCopy codepublic Node findMiddle() {
    Node slow = head;
    Node fast = head;

    // Move fast pointer two nodes and slow pointer one node
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // slow is now at the middle
}

// Example usage
public static void main(String[] args) {
    SinglyLinkedList list = new SinglyLinkedList();
    list.insertAtEnd(1);
    list.insertAtEnd(2);
    list.insertAtEnd(3);
    list.insertAtEnd(4);
    list.insertAtEnd(5);
    
    Node middle = list.findMiddle();
    System.out.println("The middle element is: " + middle.data); // Output: 3
}

Conclusion

Linked lists are a versatile data structure that provides efficient ways to manage collections of data. Understanding how to implement and manipulate linked lists is essential for solving many programming problems.

In our next post, we will explore Stacks, another fundamental data structure, and discuss their operations and applications. Stay tuned!

Also see: The Z Blogs

my other Blog: The Z Blog ZB