# 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.

{% hint style="info" %}
There are also `Doubled Linked Lists`, where each object knows the `previous` and `next` object.
{% endhint %}

{% code title="Node Interface" %}

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

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

{% endcode %}

## 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.

{% hint style="info" %}
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.
{% endhint %}

## 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)*

<img src="https://977358640-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgbsUv4FfxUwe5ihs1aG5%2Fuploads%2FLosU09VPJ9O8O9EOZ6Ud%2Ffile.excalidraw.svg?alt=media&#x26;token=d35991d5-4971-425b-8807-c8ca199eae37" alt="" class="gitbook-drawing">

{% hint style="info" %}
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.
{% endhint %}

## 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)*

<img src="https://977358640-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgbsUv4FfxUwe5ihs1aG5%2Fuploads%2Fask9DiXtb2rg8jKhCmwn%2Ffile.excalidraw.svg?alt=media&#x26;token=2afb6f6c-a1df-454f-9d17-d60a71e00d7c" alt="" class="gitbook-drawing">

{% hint style="info" %}
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.
{% endhint %}

## Implementation

```typescript
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;
    }
}
```