Design Linked List - Leetcode Solution

Problem Statement: Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to link the previous node with the current node. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class: MyLinkedList() Initializes the MyLinkedList object. int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1. void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. void addAtTail(int val) Append a node of value val as the last element of the linked list. void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted. void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

Example 1: Input ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] Output [null, null, null, null, 2, null, 3]

Explanation MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 myLinkedList.get(1); // return 2 myLinkedList.deleteAtIndex(1); // now the linked list is 1->3 myLinkedList.get(1); // return 3

Solution: To implement the MyLinkedList class, we need to create a node class first which will represent a node with its value and a reference to the next node. If we want to create a doubly linked list then we also need to add an extra attribute named prev that will point to the previous node. The node class will look like the following:

class Node {
    int val;
    Node next;
    Node prev;
    public Node(int value) {
        this.val = value;
        this.next = null;
        this.prev = null;
    }
}

For a singly linked list, we do not need the prev attribute.

Next, we will create the MyLinkedList class and implement its methods one by one.

Method 1: MyLinkedList() - Initializes the MyLinkedList object.

class MyLinkedList {
    int size;
    Node head;
    public MyLinkedList() {
        this.size = 0;
        this.head = null;
    }
}

Method 2: int get(int index) - Get the value of the indexth node in the linked list. If the index is invalid, return -1.

public int get(int index) {
    if (index < 0 || index >= size) {
        return -1;
    }
    Node temp = head;
    for (int i = 0; i < index; i++) {
        temp = temp.next;
    }
    return temp.val;
}

Method 3: void addAtHead(int val) - Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

public void addAtHead(int val) {
    Node newNode = new Node(val);
    if (head == null) {
        head = newNode;
    } else {
        newNode.next = head;
        head = newNode;
    }
    size++;
}

Method 4: void addAtTail(int val) - Append a node of value val as the last element of the linked list.

public void addAtTail(int val) {
    Node newNode = new Node(val);
    if (head == null) {
        head = newNode;
    } else {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
    size++;
}

Method 5: void addAtIndex(int index, int val) - Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.

public void addAtIndex(int index, int val) {
    if (index < 0 || index > size) {
        return;
    }
    if (index == 0) {
        addAtHead(val);
    } else if (index == size) {
        addAtTail(val);
    } else {
        Node newNode = new Node(val);
        Node temp = head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }
        newNode.next = temp.next;
        temp.next = newNode;
        size++;
    }
}

Method 6: void deleteAtIndex(int index) - Delete the indexth node in the linked list, if the index is valid.

public void deleteAtIndex(int index) {
    if (index < 0 || index >= size) {
        return;
    }
    if (index == 0) {
        head = head.next;
    } else {
        Node temp = head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }
        temp.next = temp.next.next;
    }
    size--;
}

Time Complexity: The time complexity of get, addAtHead, addAtTail, addAtIndex, deleteAtIndex methods is O(n), where n is the size of the linked list. Here, we are traversing the linked list to reach the desired position.

Space Complexity: The space complexity of the MyLinkedList class is O(n), where n is the size of the linked list. We are storing all the nodes of the linked list.

1