Intro to Linked List

a simple single linked list in leetcode

class ListNode {
    public:
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(NULL) {}
};

a more pratical one

private:
    template <typename E>
    class Node {
    public:
        E val;
        Node* next;
        Node* prev;
        
        Node(Node* prev, E element, Node* next){
            this->val = element;
            this->next = next;
            this->prev = prev;
        }
};

Why we need linked list?

• To overcome the limitation of array, which requires contiguous memory allocation.
• elements in linked list can be anywhere in the memory, and linked together via pointers.

However, the limitation of linked list is you cannot access element via index directly, you have to traverse the linked list from head to the desired index.

Convert array to linked list

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* arrayToLinkedList(std::vector<int> arr) {
    if (arr.empty()) return nullptr;
    
    ListNode* head = new ListNode(arr[0]);
    ListNode* cur = head;

    for (int i = 1; i < arr.size(); i++){
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return head;
}

I think its important to realise that when you create a new node. You get a pointer to that node. You can make this pointer point to another node, but you cannot change the address of the node itself. This is why when you do cur = cur->next, you are changing the pointer cur to point to the next node, but you are not changing the address of the node that cur was originally pointing to.

Some techniques to improve a double linked list

• use a dummy head and dummy tail to simplify the code, so you dont need to check
• have reference to head and tail to make addFirst and addLast O(1)

Double Linked list Implementation (Passed all leetcode tests)

class MyLinkedList {
private:
    struct Node {
        int value;
        Node* next;
        Node* prev;
        Node(int val) : value(val), next(nullptr), prev(nullptr) {} // need to memorise the pattern
    };

    Node* head;
    Node* tail;
    int size;

public:
    MyLinkedList() {
        // dummy head and dummy tail
        head = new Node(int());
        tail = new Node(int());
        head->next = tail;
        tail->prev = head;
        size = 0;     
    }
    ~MyLinkedList() {
        while(size > 0){
            removeFirst();
        }
        delete tail;
        delete head;
    }

    int get(int index) {
        Node* p = head;
        if (index < 0 || index >= size){
            return -1;
        }
        for (int i = 0; i < index + 1; i++){
            p = p->next;
        }
        return p->value;
    }
    
    void addAtHead(int val) {
        Node* p = new Node(val);
        // could be wrong
        head->next->prev = p;
        p->next = head->next;
        head->next = p;
        p->prev = head;  
        ++size;
    }
    
    void addAtTail(int val) {
        Node* p = new Node(val);
        Node* temp = tail->prev;

        temp->next = p;
        p->prev = temp;
        p->next = tail;
        tail->prev = p;
        ++size;
    }
    
    void addAtIndex(int index, int val) {
        //position
        Node* temp = new Node(val);
        if (index < 0 || index > size) return;

        // choose to start from tail or head based on the idx
        if (index <= size/2){
            Node* p = head;
            for (int i = 0; i < index; i++){
                p = p->next;
            }
            p->next->prev = temp;
            temp->next = p->next;
            p->next = temp;
            temp->prev = p;
        } else {
            Node* p = tail;
            for (int i = size; i > index; i--){
                p = p->prev;
            }
            p->prev->next = temp;
            temp->prev = p->prev;
            temp->next = p;
            p->prev = temp;
        }
        ++size;
    }
    
    void deleteAtIndex(int index) {
        //element
        if (index < 0 || index >= size) return;

        if (index <= size/2){
            Node* p = head;
            for (int i = 0; i <= index; i++){
                p = p->next;
            }
            // p is pointing at the node we want to delete
            p->prev->next = p->next;
            p->next->prev = p->prev;
        } else {
            Node* p = tail;
            for (int i = size - 1; i >= index; i--){
                p = p->prev;
            }
            p->prev->next = p->next;
            p->next->prev = p->prev;
        }
        --size;
    }
private:
    void removeFirst(){
        Node* p = head;
        p = p->next;
        head->next = p->next;
        p->next->prev = head;

        delete p;
        --size;
    }
};

/**
 * 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);
 */

Single Linked List Implementation