Linked Lists

About

A linked list is objects that are linked. This means that each object in this list, only knows who is their next object.

The weakness of a Linked List in terms of costs, is the traverse cost to get to an element.

There are also Doubled Linked Lists, where each object knows the previous and next object.

Node Interface

interface LinkedListNode<T> {
    value: T;
    next?: LinkedListNode<T>;
}

interface DoubledLinkedListNode<T> {
    value: T;
    next?: DoubledLinkedListNode<T>;
    previous?: DoubledLinkedListNode<T>;
}

Getting specific value or at specific position

You will have to run through the linked list, since there are no indexes, until you find the desired value.

Takes $O(1)$, for head and tail of the list. (constant time for tail only IF you have it's reference saved)

Otherwise takes $O(N)$, for middle elements.

Inserting at specific position

Desconsidering the asymptotic time to find and get to the position. Inserting a new element is just updating the next property of the existent object, and updating the next from the new object. (In Doubled Linked List, there is also the previous property, and it must update the previous element and the next element, of the inserted position)

Takes $O(1)$, for the head of the list.

It would also take $O(1)$, for the list tail IF you have it's reference saved.

Otherwise for middle elements it will take $O(N)$, since you will have to go through the list until you reach the desired position.

Deleting at specific position

Deleting is the same as inserting, you only update next property from the previous object. (In Doubled Linked List, you also update the previous property from the next object)

Takes $O(1)$, for the head of the list.

It would also take $O(1)$, for the list tail IF you have it's reference saved.

Otherwise for middle elements it will take $O(N)$, since you will have to go through the list until you reach the desired position.

Implementation

type Node<T> = {
    value: T;
    prev?: Node<T>;
    next?: Node<T>;
}

class DoubledLinkedList<T> {
    public length: number = 0;
    private head?: Node<T>;
    private tail?: Node<T>;
    
    prepend(item: T): void {
        let newNode: Node<T> = {
            value: item,
            prev: undefined,
            next: this.head
        }
        if (!this.head) this.tail = newNode;
        else this.head.prev = newNode;
        this.head = newNode;
        this.length++;
    }
    
    insertAt(item: T, idx: number): void {
        if (idx <= 0) this.prepend(item);
        else if (idx >= this.length) this.append(item);
        
        let elRight: Node<T> | undefined = this.getNodeAt(idx);
        let elLeft: Node<T> | undefined = elRight?.prev;
        
        let newNode: Node<T> = {
            value: item,
            prev: elLeft,
            next: elRight
        }
        
        elLeft.next = newNode;
        elRight.prev = newNode;
        this.length++;
    }
    
    append(item: T): void {
        let newNode: Node<T> = {
            value: item,
            prev: this.tail,
            next: undefined
        }
        if (!this.tail) this.head = newNode;
        else this.tail.next = newNode;
        this.tail = newNode;
        this.length++;
    }
    
    remove(item: T): T | undefined {
        let removedNode = this.head;
        for (; removedNode && removedNode.value !== item;)
            removedNode = removedNode.next;
        if (!removedNode) return removedNode;
        
        let elRight: Node<T> | undefined = removedNode?.next;
        let elLeft: Node<T> | undefined = removedNode?.prev;
        
        if (!elRight && !elLeft) {
            this.head = undefined;
            this.tail = undefined;
        }
        else {
            if (elRight) elRight.prev = elLeft;
            if (elLeft) elLeft.next = elRight;
            if (!elRight.prev) this.head = elRight;
            if (!elLeft.next) this.tail = elLeft;
        }
        this.length--;
        return removedNode.value;
    }
    
    removeAt(idx: number): T | undefined {
        let removedNode = this.getNodeAt(idx);
        if (!removedNode) return removedNode;
        
        let elRight: Node<T> | undefined = removedNode?.next;
        let elLeft: Node<T> | undefined = removedNode?.prev;
        
        if (!elRight && !elLeft) {
            this.head = undefined;
            this.tail = undefined;
        }
        else {
            if (elRight) elRight.prev = elLeft;
            if (elLeft) elLeft.next = elRight;
            if (!elRight.prev) this.head = elRight;
            if (!elLeft.next) this.tail = elLeft;
        }
        this.length--;
        return removedNode.value;
    }
    
    private getNodeAt(idx: number): Node<T> | undefined {
        let curr = this.head;
        for (let i = 0; i < idx && curr; i++)
            curr = curr.next;
        return curr;
    }
    
    get(idx: number): T | undefined {
        let curr = this.head;
        for (let i = 0; i < idx && curr; i++)
            curr = curr.next;
        return curr?.value;
    }
}