Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Doubly Linked List implementation? #36

Open
Azzarox opened this issue Jan 29, 2023 · 1 comment
Open

Doubly Linked List implementation? #36

Azzarox opened this issue Jan 29, 2023 · 1 comment

Comments

@Azzarox
Copy link

Azzarox commented Jan 29, 2023

Hi, this is not an issue, but more of an asking for help. I tried to implement the Doubly Linked List. However, I can't manage to pass the tests. Also, It's my first time working with typescript, and I'm finding it very frustrating at moments with types, nulls and so on. So I would like to ask if someone has a full implementation of the Doubly Linked List. I saw many implementations throughout GitHub and internet, but I want one that is specific to the course.

@pavles6
Copy link

pavles6 commented Mar 4, 2023

Hey, if you still need it here's my implementation which passes all tests:

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

export default class DoublyLinkedList<T> {
    public length: number;
    private head?: Node<T>;
    private tail?: Node<T>;

    constructor() {
        this.length = 0;
        this.head = undefined;
        this.tail = undefined;
    }

    prepend(item: T): void {
        const node: Node<T> = {
            value: item,
        };

        this.length++;

        if (!this.head) {
            this.head = this.tail = node;
            return;
        }

        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }

    insertAt(item: T, idx: number): void {
        if (idx > this.length) throw new Error("Wow thats not possible");
        else if (idx === this.length) {
            this.append(item);
            return;
        } else if (idx === 0) {
            this.prepend(item);
            return;
        }

        this.length++;

        let curr = this.getAt(idx) as Node<T>;

        curr = curr as Node<T>;

        const node: Node<T> = { value: item, prev: curr.prev, next: curr };

        curr.prev = node;

        if (node.prev) {
            node.prev.next = node;
        }
    }

    append(item: T): void {
        this.length++;

        const node: Node<T> = {
            value: item,
        };

        if (!this.tail) {
            this.head = this.tail = node;
            return;
        }

        node.prev = this.tail;
        this.tail.next = node;
        this.tail = node;
    }

    remove(item: T): T | undefined {
        let curr = this.head;

        for (let i = 0; curr && i < this.length; i++) {
            if (curr.value === item) break;
            curr = curr.next;
        }

        if (!curr) return;

        return this.removeNode(curr);
    }

    get(idx: number): T | undefined {
        return this.getAt(idx)?.value;
    }

    removeAt(idx: number): T | undefined {
        const node = this.getAt(idx);

        if (!node) return undefined;

        return this.removeNode(node);
    }

    private removeNode(node: Node<T>): T {
        this.length--;

        if (this.length === 0) {
            const out = this.head?.value;
            this.head = this.tail = undefined;
            return out as T;
        }

        if (node?.prev) node.prev.next = node.next;

        if (node?.next) node.next.prev = node.prev;

        if (node === this.head) {
            this.head = node.next;
        }

        if (node === this.tail) {
            this.tail = node.prev;
        }

        // cleanup the references (this is kinda redundant, will be done automatically by gc)
        node.prev = node.next = undefined;

        return node.value;
    }

    private getAt(idx: number): Node<T> | undefined {
        let curr = this.head;

        for (let i = 0; i < idx && curr; i++) {
            curr = curr.next;
        }

        return curr;
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants