707. Design Linked List

LeetCode problem link (opens new window)

Problem description:

Implement the following operations in your linked list class:

• get(index): Get the value of the index-th node in the linked list. If the index is invalid, return -1.
• addAtHead(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.
• addAtTail(val): Append a node of value val to the last element of the linked list.
• addAtIndex(index,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. If index is less than 0, the node will be inserted at the head of the linked list.
• deleteAtIndex(index): Delete the index-th node in the linked list, if the index is valid.

Approach

If you are not familiar with the basics of linked lists, you can read this article: Linked List Basics (opens new window)

If you're not clear on the concept of dummy head nodes in linked lists, you can refer to this article: 0203.Remove Linked List Elements (opens new window)

Removing a node from the linked list:

Adding a node to the linked list:

This problem requires designing five interfaces for linked lists:

• Get the value of the index-th node in the linked list
• Insert a node at the head of the linked list
• Append a node at the tail of the linked list
• Insert a node before the index-th node in the linked list
• Delete the index-th node from the linked list

These five interfaces cover the common operations for linked lists. This problem is a very good exercise for practicing linked list operations.

There are two approaches to operate on linked lists:

1. Directly operate on the original linked list.
2. Set up a dummy head node to simplify operations.

Below is an example using a dummy head node (this makes things more convenient, as you'll see from the code).

class MyLinkedList {
public:
    // Define a structure for the linked list node
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // Initialize the linked list
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // This defines a dummy head node, not the actual head node of the list.
        _size = 0;
    }

    // Get the value of the `index`-th node, return -1 if the index is invalid. Note that the index starts from 0, so the 0th node is the head.
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){
            cur = cur->next;
        }
        return cur->val;
    }

    // Add a node at the front of the linked list; the new node will become the new head of the list
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    // Add a node at the end of the linked list
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    // Add a `val`-valued node before the index-th node in the list
    void addAtIndex(int index, int val) {
        if(index > _size) return;
        if(index < 0) index = 0;        
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    // Delete the `index`-th node in the linked list, if index is valid
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp=nullptr;
        _size--;
    }

    // Print the linked list
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

};

• Time Complexity: Related operations on index are O(index), the rest are O(1).
• Space Complexity: O(n)

Other Language Versions

C++ Double Linked List Approach:

// Implemented using a circular virtual node double linked list
class MyLinkedList {
public:
    // Define the structure of a doubly linked list node
    struct DList {
        int elem;
        DList *next;
        DList *prev;
        DList(int elem) : elem(elem), next(nullptr), prev(nullptr) {};
    };

    // Constructor to initialize the linked list
    MyLinkedList() {
        sentinelNode = new DList(0);
        sentinelNode->next = sentinelNode;
        sentinelNode->prev = sentinelNode;
        size = 0;
    }

    // Get the value of the `index`-th node in the linked list
    int get(int index) {
        if (index > (size - 1) || index < 0) {
            return -1;
        }
    [Translation continues for other code versions...]
    etc...