LinkedList

linked-list.js

{
    /*

    Who-when: Krazov 2019

    LinkedList object creator.

    Instead of storing a list in array or other linear container, the data
    is organized in a chain of linked items:

    ```
        LinkedListCell {
            data: any;
            next: LinkedListCell | null;
        }
    ```

    Instantiation:
      * new LinkedList(...items); -- classic constructor call
      * LinkedList.of(...items); -- constructor call without `new` keyword

    Object has two properties:
      * `start` -- the first cell of the list
      * `head` -- pointer for _current_ cell

    Possible mutations:
      * `next()` -- moves head to the next cell (or stays at `null` in case of the end)
      * `setHead(cell)` -- sets head to passed cell (has to be on the list)
      * `resetHead()` -- sets head back to the start
      * `prepend(item)` -- adds new item to the beginning of the list
      * `insertBefore(item, before)` -- adds new item before  first occurence of `before` value
      * `append(item)` -- adds new item to the end of the list
      * `insertAfter(item, after)` -- adds new item after first occurence of `after` value

    Functional methods:
      * `map(fn)` -- returns new LinkedList instance with all elements mapped with `fn` passed
      * `filter(fn)` -- returns new LinkedList instance with all elements filtered with `fn` passed
      * `reduce(fn, ?initial)` -- returns whatever reducer of all elements decides

    Note: All methods are chainable.

    Getters:
      * `[Symbol.iterator]()` -- returns iterator, meaning LinkedList can be iterated over (also: `[...list]`)
      * `current` -- returns value of current cell
      * `currentCell` -- returns current cell container
      * `hasFinished` & `hasNotFinished` -- if head is after last element (or not)
      * `hasOneLastNext` -- if it’s possible to make one last `next()`

    Static methods:
      * `of` -- non-`new` keyword constructor
      * `createCell` -- wraps any value into cell-like container
      * `isCell` -- ducktyping for cell correctness

    Possible TODOs (unlikely at this point):
      * `concat(item | LinkedList)` -- functional method that would return a new list concated with items or other list
      * `prev()` -- going to the previous cell (would require list to become two way list)
      * looped lists -- while possible now, it will fail with iterator, and hence with `map`, `filter`, and `reduce`
      * using local head instead of moving the one of the object itself

    */

    class LinkedList {
        static of(...args) {
            try {
                return new this(...args);
            } catch(error) {
                return new LinkedList(...args);
            }
        }

        static createCell(item) {
            return {
                data: item,
                next: null,
            };
        }

        static isCell(potentialItem) {
            return potentialItem
                && typeof potentialItem == 'object'
                && potentialItem.hasOwnProperty('data')
                && potentialItem.hasOwnProperty('next')
                && (LinkedList.isCell(potentialItem.next) || potentialItem.next === next);
        }

        start = null;
        head = null;

        constructor(...items) {
            const { createCell } = LinkedList;

            items.reduce(
                (previous, current) => {
                    const next = createCell(current);

                    if (previous == null) {
                        this.head = this.start = next;
                    } else {
                        previous.next = next;
                    }

                    return next;
                },
                null
            )
        }

        next() {
            this.head = this.hasNotFinished ? this.head.next : null;

            if (this.head != null && this.head == this.head.next) {
                throw Error('Circularity achieved!')
            }

            return this;
        }

        setHead(cell) {
            if (this.isNotOnList(cell)) {
                const isCell = LinkedList.isCell(cell);
                const thing = isCell ? 'cell' : 'item';
                const thingToDisplay = cell && isCell
                    ? JSON.stringify({ data: cell.data })
                    : cell;

                throw new Error(`No such ${thing} on the list: ${thingToDisplay}`);
            }

            this.head = cell;
            return this;
        }

        resetHead() {
            return this.setHead(this.start);
        }

        prepend(item) {
            const insertion = LinkedList.createCell(item);
            insertion.next = this.start;
            this.start = insertion;
            return this;
        }

        insertBefore(item, before) {
            const savedHead = this.head;
            let previous = null

            this.head = this.start;
            while (this.hasNotFinished) {
                if (this.currentItem === before) {
                    const insertion = LinkedList.createCell(item);
                    insertion.next = this.head;
                    if (previous) {
                        previous.next = insertion;
                    } else {
                        this.start = this.head;
                    }

                    break;
                }
                previous = this.head;
                this.next();
            }

            this.head = savedHead;

            return this;
        }

        append(item) {
            const savedHead = this.head;

            this.head = this.start;
            while (this.hasNotFinished) {
                if (this.hasOneLastNext) {
                    break;
                }
                this.next();
            }

            const insertion = LinkedList.createCell(item);
            if (this.start) {
                this.head.next = insertion;
            } else {
                this.head = this.start = insertion;
            }

            this.head = savedHead;

            return this;
        }

        insertAfter(item, after) {
            const savedHead = this.head;

            this.head = this.start;
            while (this.hasNotFinished) {
                if (this.currentItem === after) {
                    const insertion = LinkedList.createCell(item);
                    insertion.next = this.head.next;
                    this.head.next = insertion;
                    break;
                }
                this.next();
            }

            this.head = savedHead;

            return this;
        }

        removeItem(item) {
            const savedHead = this.head;
            let previous = null;

            this.head = this.start;
            while (this.hasNotFinished) {
                if (this.currentItem === item) {
                    if (previous) {
                        previous.next = this.head.next;
                    } else {
                        this.start = this.head.next;
                    }

                    this.head = this.head.next;
                    break;
                }

                previous = this.head;
                this.next();
            }

            if (this.start != null && savedHead.data !== item) {
                this.head = savedHead;
            }

            return this;
        }

        // immutable methods
        map(fn) {
            return LinkedList.of(...[...this].map((item) => fn(item)));
        }

        filter(fn) {
            return LinkedList.of(...[...this].filter((item) => fn(item)));
        }

        reduce(...args) {
            let fn;
            let initial;
            let array;

            if (args.length == 1) {
                [fn] = args;
                [initial, ...array] = [...this];
            } else {
                [fn, initial] = args;
                array = [...this];
            }

            return array.reduce((accumulated, item) => fn(accumulated, item), initial);
        }

        // debug
        print() {
            console.groupCollapsed('--- print: start');

            [...this].forEach((item, index) => {
                console.log(`#${++index}:`, item);
            });

            console.log(`Structure: ${JSON.stringify(this.start)}`);
            console.log('start', this.start);
            console.log('head', this.head);
            console.log('is head at start:', this.isAtStart);
            console.groupEnd();
        }

        // getters
        *[Symbol.iterator]() {
            const savedHead = this.head;

            this.head = this.start;
            while (this.head != null) {
                yield this.head.data;
                this.head = this.head.next;
            }

            this.head = savedHead;
        }

        isOnList(item) {
            const savedHead = this.head;
            this.head = this.start;

            while (this.hasNotFinished) {
                if (this.head == item) {
                    return true;
                }

                this.head = this.head.next;
            }

            this.head = savedHead;

            return false;
        }

        isNotOnList(item) {
            return !this.isOnList(item);
        }

        get currentItem() {
            return this.hasNotFinished ? this.head.data : null;
        }

        get isAtStart() {
            return this.start === this.head;
        }

        get hasFinished() {
            return this.head == null;
        }

        get hasNotFinished() {
            return !this.hasFinished;
        }

        get hasOneLastNext() {
            return Boolean(this.head) && this.head.next == null;
        }
    }

    function demo1() {
        const list = LinkedList.of(42, 63, 97);

        console.info('# const list = LinkedList.of(42, 63, 97);');
        console.log(list);
        console.info('### list.print();');

        list.print();

        list.insertAfter(666, 42);
        console.info('## list.insertAfter(666, 42);');

        list.print();

        list.insertBefore(1, 666);
        console.info('## list.insertBefore(1, 666);');

        list.print();
    }

    function demo2() {
        const double = (value) => value * 2;
        const lessThan100 = (value) => value < 100;
        const sum = (a, b) => a + b;

        const list1 = LinkedList.of(1, 2, 3);
        const list2 = list1.map(double);

        list2.print();

        list2.prepend(1984);

        console.info('[...list2]');
        console.log([...list2]);

        const list2b = list2.filter(lessThan100);
        console.log('const list2b = list2.filter(lessThan100);');
        console.log([...list2b]);

        const sumOf2 = list2b.reduce(sum, 0);
        console.log('const sumOf2 = list2b.reduce(sum, 0);');
        console.log(sumOf2);
    }

    function demo3() {
        const list3 = LinkedList.of(1, 2, 3);

        const fail = (list, wrongHead) => {
            try {
                list.setHead(wrongHead);
            } catch(error) {
                console.error(error)
            }
        }

        fail(list3);
        fail(list3, null);
        fail(list3, 4);
        fail(list3, {
            data: 57,
            next: null,
        });

        list3.resetHead().setHead(list3.next().head); // brings back fond memories of jQuery

        list3.print();
    }

    function demo4() {
        const list4 = LinkedList.of(1999, 2000, 2001);

        console.log('initial list', [...list4]);
        list4.print();

        list4.removeItem(2000);
        console.log('after removing 2000', [...list4]);
        list4.print();

        list4.removeItem(1999);
        console.log('after removing 1999', [...list4]);
        list4.print();

        list4.removeItem(2001);
        console.log('after removing 2001', [...list4]);
        list4.print();
    }

    // main
    console.clear();
    demo1();
    // demo2();
    // demo3();
    // demo4();
    console.log('The end of demo.');
}

Really, thats amazing!