TwoWayLinkedList

LinkedList.js

'use strict';

/**
 * Represent node in two way linked list.
 * Totally incomprehensible rand field, that produce circular links for list
 * List is data structure that allows walk around list, specially two way linked list
 * help to walk from tail. With rand field serialize and
 * deserialize have O(n * 2) instead O(n)
 */
class ListNode {
    constructor(data) {
        this.prev = void 0;
        this.next = void 0;
        this.rand = void 0;
        this.data = data;
    }
}

/**
 * Two way linked list
 */
class List {
    constructor() {
        this.head = void 0;
        this.tail = void 0;
        this.length = 0;
    }

    /**
     * Create unique ids for nodes
     * @returns {List}
     * @private
     */
    _addUniqueIds() {
        let el = this.head;
        let uniqueId = 0;
        while(el) {
            el.id = ++uniqueId;
            el = el.next
        }
        return this;
    }

    /**
     * @returns {{}}
     * @private
     */
    _createListMap() {
        let el = this.head;
        let map = {};
        while(el) {
            let obj = {
                data: el.data
            };
            if (el.prev) {
                obj.prevId = el.prev.id;
            }
            if (el.next) {
                obj.nextId = el.next.id;
            }
            if (el.rand) {
                obj.randId = el.rand.id;
            }
            map[el.id] = obj;
            el = el.next;
        }
        return map;
    }

    /**
     * Return serialized list
     */
    serialize() {
        return JSON.stringify(this._addUniqueIds()._createListMap());
    }

    /**
     * Deserialize json to list
     * @param json - serialized list
     * @returns {List}
     */
    deserialize(json) {
        this.head = void 0;
        this.tail = void 0;
        const map = JSON.parse(json);
        const nodes = {};
        const ids = Object.keys(map);
        ids.forEach(uniqueId => {
            const { data } = map[uniqueId];
            nodes[uniqueId] = new ListNode(data);
        });
        ids.forEach(uniqueId => {
            const {prevId, nextId, randId } = map[uniqueId];
            if(prevId) {
                nodes[uniqueId].prev = nodes[prevId];
            }
            if(nextId) {
                nodes[uniqueId].next = nodes[nextId];
            }
            if(randId) {
                nodes[uniqueId].prev = nodes[randId];
            }
        });
        this.head = nodes[Math.min.apply(null, ids)];
        this.tail = nodes[Math.max.apply(null, ids)];
        this.length = ids.length;
        return this;
    }
    
    _getRandomId() {
        return Math.floor(Math.random() * this.length)
    }
    
    shuffle() {
        if(!this.head.id) {
            this._addUniqueIds();
        }
        let el = this.head;
        while(el) {
            const id = el.id;
            let randId = this._getRandomId();
            while(randId === id) {
                randId = this._getRandomId();
            }
            let randNode = this.head;
            while(randId--) {
                randNode = randNode.next;
            }
            el.rand = randNode;
            el = el.next;
        }
        return this;
    }

    /**
     * Create new node and append it to list
     * Update tail node
     * @param data
     * @returns {List}
     */
    add(data) {
        let node = new ListNode(data);
        if(!this.head) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        this.length++;
        return this;
    }

    toArray() {
        let el = this.head;
        const res = [];
        while(el) {
            res.push(el.data);
            el = el.next;
        }
        return res;
    }
}

const a = new List();

a.add("a");
a.add("b");
a.add("c");

console.log(a.deserialize(a.serialize()));

import React from 'react';
import ReactDOM from 'react-dom';

const render = el => ReactDOM.render(el, document.body);

const renderList = list =>
    <div>
        <button
            onClick={() => render(renderSerializedList(list.serialize()))}>
            Show serialized
        </button>
        <ul>
            {list.toArray().map((data, i) => <li key={i}>{data}</li>)}
        </ul>
    </div>;

const renderSerializedList = list =>
    <div>
        <button
            onClick={() => render(renderList((new List()).deserialize(list)))}>
            Show deserialized
        </button>
        <div>
            <p>{list}</p>
        </div>
    </div>;