algoadvance

Leetcode 707. Design Linked List

Problem Statement

Design your implementation of the linked list. You can choose to use a single linked list or a double linked list. A node in a singly linked list should have two attributes: an integer value and a next node pointing to the next node in the list or null if it is the tail of the list. 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:

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

Clarifying Questions

1. Can we assume that index values provided to the get, addAtIndex, and deleteAtIndex functions will be non-negative?
2. Is the linked list intended to be singly or doubly linked for this implementation?
3. What are the size constraints for the linked list? Can it be very large, which might affect performance considerations?

Assumptions:

1. Yes, the index values will be non-negative.
2. It can be either. For simplicity, we will implement a singly linked list.
3. Assume the linked list can be moderately large but within practical limits for typical interview solutions.

Strategy

1. Node Structure: Implement the basic node structure for the linked list having a value and a next pointer.
2. LinkedList Class: Implement the MyLinkedList class with the required methods.
   • Use a dummy head to simplify add and delete operations.
   • Maintain a size variable to keep track of the number of elements for quick length checks.
3. Methods: Implement the methods ensuring boundary checks and proper node manipulation operations.

Code

Here is the implementation in C++:

class MyLinkedList {
private:
    struct Node {
        int value;
        Node* next;
        Node(int val) : value(val), next(nullptr) {}
    };
    
    Node* head;
    int size;

public:
    /** Initialize your data structure here. */
    MyLinkedList() {
        head = new Node(0); // dummy head
        size = 0;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        if (index < 0 || index >= size)
            return -1;
        Node* current = head->next;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        return current->value;
    }
    
    /** 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 addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
        addAtIndex(size, 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 addAtIndex(int index, int val) {
        if (index > size)
            return;
        if (index < 0)
            index = 0;
        Node* prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        Node* newNode = new Node(val);
        newNode->next = prev->next;
        prev->next = newNode;
        size++;
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size)
            return;
        Node* prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        Node* toDelete = prev->next;
        prev->next = toDelete->next;
        delete toDelete;
        size--;
    }
};

Time Complexity

• get(index): O(n) where n is the index since we might need to traverse the whole list.
• addAtHead(val): O(1) since it directly adds the element after the dummy head.
• addAtTail(val): O(n) where n is the length of the list as it needs to traverse to the end.
• addAtIndex(index, val): O(n) where n is the index or the length of the list, as potentially the entire list must be traversed.
• deleteAtIndex(index): O(n) where n is the index because it requires traversal to the node before the index.

This implementation ensures all required operations are efficient and easy to follow.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?