Design Linked list⚓︎

Description⚓︎

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 indicate the previous node in the linked list. 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 index-th 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 index-th 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 index-th 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

Constraints:

0 <= index, val <= 1000
Please do not use the built-in LinkedList library.
At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Solution⚓︎

With Dummy Head⚓︎

class MyLinkedList {
public:
    struct LinkedNode {
        int val;
        LinkedNode *next;
        LinkedNode(int val) : val(val), next(nullptr) {}
    };
    MyLinkedList() {
        _dummyHead = new LinkedNode(0);
        _size = 0;
    }

    int get(int index) {
        if (index >= _size || index < 0) return -1;
        LinkedNode *curr = _dummyHead->next;
        while (index-- && curr) curr = curr->next;
        if (curr) return curr->val;
        return -1;
    }

    void addAtHead(int val) {
        LinkedNode *newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    void addAtTail(int val) {
        LinkedNode *newNode = new LinkedNode(val);
        LinkedNode *curr = _dummyHead;
        while (curr->next != nullptr) curr = curr->next;
        curr->next = newNode;
        _size++;
    }

    void addAtIndex(int index, int val) {
        if (index > _size) return;
        if (index < 0) index = 0;
        LinkedNode *newNode = new LinkedNode(val);
        LinkedNode *curr = _dummyHead;
        while (index-- && curr->next) curr = curr->next;
        newNode->next = curr->next;
        curr->next = newNode;
        _size++;
    }

    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) return;
        LinkedNode *curr = _dummyHead;
        while (index-- && curr->next) curr = curr->next;
        LinkedNode *temp = curr->next;
        curr->next = curr->next->next;
        delete temp;
        temp = nullptr;
        _size--;
    }
private:
    int _size;
    LinkedNode *_dummyHead;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

Time complexity: $O (i n d e x)$ for operations involving index, $O (1)$ for the rest;
Space complexity: $O (n)$ .

Note: When we insert with index < 0, test case will just treat as insert at index = 0.

Code with comments:

class MyLinkedList {
public:
    // Node structure representing each element in the list
    struct LinkedNode {
        int val;           // Value of the node
        LinkedNode *next;  // Pointer to the next node in the list
        LinkedNode(int val) : val(val), next(nullptr) {}
    };

    // Constructor
    MyLinkedList() {
        _dummyHead = new LinkedNode(0);  // Create a dummy head to simplify operations
        _size = 0;                       // Initialize the size of the list as 0
    }

    // Get the value of the index-th node in the linked list
    int get(int index) {
        if (index >= _size || index < 0) return -1; // Return -1 for invalid index
        LinkedNode *curr = _dummyHead->next;        // Start from the first real node
        while (index--) curr = curr->next;          // Move to the correct node
        return curr->val;                           // Return the value of the node
    }

    // Add a node of value val before the first element of the linked list
    void addAtHead(int val) {
        LinkedNode *newNode = new LinkedNode(val);  // Create a new node
        newNode->next = _dummyHead->next;           // Point the new node to the first real node
        _dummyHead->next = newNode;                 // Insert the new node after dummy head
        _size++;                                    // Increase the size of the list
    }

    // Append a node of value val to the last element of the linked list
    void addAtTail(int val) {
        LinkedNode *newNode = new LinkedNode(val);  // Create a new node
        LinkedNode *curr = _dummyHead;              // Start from the dummy head
        while (curr->next != nullptr)               // Traverse to the end of the list
            curr = curr->next;
        curr->next = newNode;                       // Append the new node
        _size++;                                    // Increase the size of the list
    }

    // Add a node of value val before the index-th node in the linked list
    void addAtIndex(int index, int val) {
        if (index > _size) return;                  // Do nothing if index is greater than the size
        if (index < 0) index = 0;                   // Treat negative index as 0
        LinkedNode *newNode = new LinkedNode(val);  // Create a new node
        LinkedNode *curr = _dummyHead;              // Start from the dummy head
        while (index--) curr = curr->next;          // Move to the correct position
        newNode->next = curr->next;                 // Insert the new node
        curr->next = newNode;
        _size++;                                    // Increase the size of the list
    }

    // Delete the index-th node in the linked list, if the index is valid
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) return;    // Do nothing if the index is invalid
        LinkedNode *curr = _dummyHead;              // Start from the dummy head
        while (index--) curr = curr->next;          // Move to the node before the one to be deleted
        LinkedNode *temp = curr->next;              // Temporarily store the node to be deleted
        curr->next = curr->next->next;              // Remove the node from the list
        delete temp;                                // Delete the node
        temp = nullptr;
        _size--;                                    // Decrease the size of the list
    }

private:
    int _size;                  // Size of the linked list
    LinkedNode *_dummyHead;     // Dummy head node to simplify operations
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

Another way of writing:

class MyLinkedList {
public:
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val) : val(val), next(nullptr) {}
    };

    MyLinkedList() {
        dummyHead = new LinkedNode(0);
        _size = 0;
    }

    int get(int index) {
        if (index < 0 || index >= _size) return -1;
        auto curr = dummyHead->next;
        while (index--) curr = curr->next;
        return curr->val;
    }

    void addAtHead(int val) {
        addAtIndex(0, val);
    }

    void addAtTail(int val) {
        addAtIndex(_size, val);
    }

    void addAtIndex(int index, int val) {
        if (index > _size) return;
        if (index < 0) index = 0;

        auto curr = dummyHead;
        while (index--) curr = curr->next;

        auto toAdd = new LinkedNode(val);
        toAdd->next = curr->next;
        curr->next = toAdd;

        _size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= _size) return;

        auto curr = dummyHead;
        while (index--) curr = curr->next;

        curr->next = curr->next->next;
        _size--;
    }
private:
    int _size;
    LinkedNode* dummyHead;
};

Without Dummy Head⚓︎

class MyLinkedList {
public:
    // Node structure for the linked list
    struct Node {
        int val;   // Value of the node
        Node *next; // Pointer to the next node
        Node(int _val) : val(_val), next(nullptr) {} // Constructor to initialize node
    } *head; // Head pointer of the list

    // Constructor initializes the linked list
    MyLinkedList() {
        head = nullptr; // Initially, the list is empty, so head is null
    }

    // Function to get the value of the node at a given index
    int get(int index) {
        if (index < 0) return -1; // Return -1 for invalid index
        auto p = head; // Start from the head of the list
        for (int i = 0; i < index && p; i++) p = p->next; // Traverse the list to reach the desired index
        if (!p) return -1; // If p is null, index is out of bounds
        return p->val; // Return the value of the node at the index
    }

    // Function to add a node at the beginning of the list
    void addAtHead(int val) {
        auto curr = new Node(val); // Create a new node
        curr->next = head; // Link new node to the current head
        head = curr; // Update head to the new node
    }

    // Function to add a node at the end of the list
    void addAtTail(int val) {
        if (!head) { // If the list is empty
            head = new Node(val); // Create a new node and set it as head
        }
        else {
            auto p = head; // Start from the head
            while (p->next) p = p->next; // Traverse to the last node
            p->next = new Node(val); // Add new node at the end
        }
    }

    // Function to add a node at a specific index
    void addAtIndex(int index, int val) {
        if (index <= 0) { // If index is 0 or negative, add at head
            addAtHead(val);
        }
        else {
            int len = 0;
            for (auto p = head; p; p = p->next) len++; // Calculate the length of the list
            if (index == len) { // If index equals the length of the list, add at tail
                addAtTail(val);
            }
            else if (index < len) { // If index is within bounds
                auto p = head;
                for (int i = 0; i < index - 1; i++) p = p->next; // Find the node before the desired index
                auto curr = new Node(val); // Create a new node
                curr->next = p->next; // Insert the new node after p
                p->next = curr;
            }
        }
    }

    // Function to delete a node at a specific index
    void deleteAtIndex(int index) {
        int len = 0;
        for (auto p = head; p; p = p->next) len++; // Calculate the length of the list
        if (index >= 0 && index < len) { // If index is within bounds
            if (!index) { // If index is 0, delete the head
                head = head->next;
            }
            else {
                auto p = head;
                for (int i = 0; i < index - 1; i++) p = p->next; // Find the node before the one to delete
                p->next = p->next->next; // Delete the node at the index
            }
        }
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

Double Linked List⚓︎

Add at Index, Add at Head, and Add at Tail:

Find the predecessor and the successor of the node to insert. If the node is to be inserted at head, its predecessor is a sentinel head. If the node is to be inserted at the tail, its successor is a sentinel tail. (Use bidirectional search to perform faster.)
Insert the node by changing the links to the next and previous nodes.

toAdd->prev = pred;
toAdd->next = succ;
pred->next = toAdd;
succ->prev = toAdd;

Delete at Index:

Find the predecessor and successor.
Delete the node by changing the links to the next and previous nodes.

pred->next = succ;
succ->prev = pred;

Get:

Compare index and size - index to define the fastest way: starting from the head, or starting from the tail.
Go to the wanted node.

auto curr = head;
if (index + 1 > _size - index) {
    for (int i = 0; i < index + 1; i++)
        curr = curr->next;
} else {
    curr = tail;
    for (int i = 0; i < _size - index; i++)
        curr = curr->prev;
}

Complete code:

class MyLinkedList {
public:
    struct DoubleLinkedNode {
        int val;
        DoubleLinkedNode* prev;
        DoubleLinkedNode* next;
        DoubleLinkedNode(int _val = 0) : val(_val), prev(nullptr), next(nullptr) {}
    };

    MyLinkedList() {
        _size = 0;
        head = new DoubleLinkedNode(0);
        tail = new DoubleLinkedNode(0);
        // sentinel (dummy) nodes as pseudo-head and pseudo-tail
        head->next = tail;
        tail->prev = head;
    }

    // Destructor to free memory of all nodes including sentinel nodes
    ~MyLinkedList() {
        auto curr = head;
        while (curr) {
            auto temp = curr;
            curr = curr->next;
            delete temp;
        }
    }

    int get(int index) {
        if (index < 0 || index >= _size) return -1;

        auto curr = head;
        if (index + 1 > _size - index) {
            for (int i = 0; i < index + 1; i++)
                curr = curr->next;
        } else {
            curr = tail;
            for (int i = 0; i < _size - index; i++)
                curr = curr->prev;
        }

        return curr->val;
    }

    void addAtHead(int val) {
        addAtIndex(0, val);
        // DoubleLinkedNode* pred = head, * succ = head->next;
        // _size++;
        // auto toAdd = new DoubleLinkedNode(val);
        // toAdd->prev = pred;
        // toAdd->next = succ;
        // pred->next = toAdd;
        // succ->prev = toAdd;
    }

    void addAtTail(int val) {
        addAtIndex(_size, val);
        // DoubleLinkedNode* succ = tail, * pred = tail->prev;
        // _size++;
        // auto toAdd = new DoubleLinkedNode(val);
        // toAdd->prev = pred;
        // toAdd->next = succ;
        // pred->next = toAdd;
        // succ->prev = toAdd;
    }

    void addAtIndex(int index, int val) {
        if (index > _size) return;
        if (index < 0) index = 0;

        DoubleLinkedNode* pred, * succ;
        if (index < _size - index) {
            pred = head;
            for (int i = 0; i < index; i++) 
                pred = pred->next;
            succ = pred->next;
        } else {
            succ = tail;
            for (int i = 0; i < _size - index; i++)
                succ = succ->prev;
            pred = succ->prev;
        }

        _size++;
        auto toAdd = new DoubleLinkedNode(val);
        toAdd->prev = pred;
        toAdd->next = succ;
        pred->next = toAdd;
        succ->prev = toAdd;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= _size) return;

        DoubleLinkedNode* pred, * succ;
        if (index < _size - index) {
            pred = head;
            for (int i = 0; i < index; i++)
                pred = pred->next;
            succ = pred->next->next;
        } else {
            succ = tail;
            for (int i = 0; i < _size - index - 1; i++)
                succ = succ->prev;
            pred = succ->prev->prev;
        }

        _size--;

        // Remove the node from the list
        // pred->next = succ;
        // succ->prev = pred;
        auto toDelete = pred->next;
        pred->next = succ;
        succ->prev = pred;
        delete toDelete; // Free the memory of the node to be deleted
    }

private:
    int _size;
    DoubleLinkedNode* head;
    DoubleLinkedNode* tail;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */