Implementing a singly or doubly linked-list in java a leetcode question

In the world of data structures and algorithms, linked lists play a fundamental role. They provide an efficient way to store and manipulate data, especially when the size of the data is unknown or can dynamically change over time. In this article, we will explore how to implement a singly linked list in Java, focusing on a specific LeetCode question. By understanding the concept of linked lists and their implementation, you’ll be better equipped to solve similar coding challenges.

Understanding Singly Linked Lists: A singly linked list is a linear data structure where each element (node) contains a value and a reference to the next node in the list. The last node points to null, indicating the end of the list. Unlike arrays, linked lists do not require contiguous memory allocation, allowing for dynamic memory management.

Implementing the Singly Linked List Class: To solve LeetCode problems involving linked lists, it is essential to have a well-defined implementation of a linked list. Let’s go step by step through the process of creating a basic singly linked list class in Java.

class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
    }
}

class MyLinkedList {
    ListNode head;
    
    MyLinkedList() {
        head = null;
    }
    
    void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
    }
    
    void addAtTail(int val) {
        ListNode newNode = new ListNode(val);
        
        if (head == null) {
            head = newNode;
            return;
        }
        
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        
        current.next = newNode;
    }
    
    void addAtIndex(int index, int val) {
        if (index == 0) {
            addAtHead(val);
            return;
        }
        
        ListNode newNode = new ListNode(val);
        ListNode current = head;
        int count = 0;
        
        while (current != null && count < index - 1) {
            current = current.next;
            count++;
        }
        
        if (current == null) {
            return;
        }
        
        newNode.next = current.next;
        current.next = newNode;
    }
    
    void deleteAtIndex(int index) {
        if (head == null) {
            return;
        }
        
        if (index == 0) {
            head = head.next;
            return;
        }
        
        ListNode current = head;
        int count = 0;
        
        while (current != null && count < index - 1) {
            current = current.next;
            count++;
        }
        
        if (current == null || current.next == null) {
            return;
        }
        
        current.next = current.next.next;
    }
    
    ListNode get(int index) {
        ListNode current = head;
        int count = 0;
        
        while (current != null && count < index) {
            current = current.next;
            count++;
        }
        
        return current;
    }
}

Explaining the Methods:

addAtHead(int val): Adds a new node with the given value at the beginning of the linked list.
addAtTail(int val): Adds a new node with the given value at the end of the linked list.
addAtIndex(int index, int val): Adds a new node with the given value at the specified index in the linked list.
deleteAtIndex(int index): Deletes the node at the specified index from the linked list.

Leave a Comment Cancel reply