How to add an item to a serialized linked list in Javascript

Question

If I serialize a linked list to JSON and store it in a text file

const list = new SinglyLinkedList();
list.push('Hello');
list.push('World');
list.push('!');
list.print();

fs.writeFile('./test.txt', JSON.stringify(list), err => {
    if (err) {
        console.log(err);
        return;
    }
})

I can read the file and de-serialize the data to get back the linked list but what if I want to add a new element in the linked list. Serialization only saves the obj state.

Is there any way by which I can add a new item to this list and serialize it again ?

What does your object serialise into? Can you instantiate it from its serialised form? — VLAZ, Sep 21 '21 at 10:01
It's not clear to me what the problem is. If you still have the object in memory, can't you add the item to it and re-serialize it? If you don't still have the object in memory, can't you de-serialize it and then add the item and re-serialize it? — David, Sep 21 '21 at 10:04
@VLAZ JSON. I don't think so. I can deserialize it and have the obj back in memory. — RHGPT, Sep 21 '21 at 10:07
@RHGPT so, you cannot actually get a `SinglyLinkedList` from this JSON, and you are searching for a way to do that, correct? — VLAZ, Sep 21 '21 at 10:09
@David I have a class that instantiate a SInglyLinkedList obj that has some methods like push, pop and traverse. If I serialize the obj to JSON and store it in a text file, it will captures the state of the obj and store it. After de-serializing the obj back to memory. I can get the list back but it will not have any methods so do I have to manually instantiate a new linked list and then recreate the old one by traversing it ? — RHGPT, Sep 21 '21 at 10:14
@VLAZ yeah I wanna know how can I store the data str to a file and the recreate it back again efficiently. — RHGPT, Sep 21 '21 at 10:15
As you already deduced, the parsed JSON will just be an object, not a class instance. You can either traverse this and reinstantiate your LinkedList, add a methods to your Class that emit/accept JSON, or write a custom [reviver](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/JSON/parse#using_the_reviver_parameter) to pass to JSON.parse() — pilchard, Sep 21 '21 at 10:18
@RHGPT well, you'd need to write out the logic for that somewhere. Might be a static method in `SinglyLinkedList` or a separate function/method elsewhere but there isn't a generic way to transform any object to a specific class. Well, you could *try* deserialisng into a generic object, then change the prototype, but I'd advise against it. It's not a good generic solution when you have custom classes around - it might not work for every case. — VLAZ, Sep 21 '21 at 10:19
@pilchard How does something like sqllite or anything that store the data in a persistant data str on disk add a new item to the data. Do they recreate the obj as a class instance, but that will not be very efficient I think. — RHGPT, Sep 21 '21 at 10:24
@RHGPT RBMSes don't keep an instance of the data in memory all the time and save *that". Usually they just save *some data* and then retrieve it. No need to make it into some object. Certainly not on the fly all the time. And different systems function differently. Some do a periodic syncronisation with persistent storage, others a manual one. In either case, they can *restore* the object from that serialised form. it depends on the language/technology stack how efficient that is. Some are better but even slower solutions aren't THAT bad. — VLAZ, Sep 21 '21 at 10:28
@VLAZ Yeah I can have a static method on a class for this case. But how does a program store data in a persistent data structure on a disk. They can probably traverse the data efficiently but how do they add new items to the persistent data structure stored on the disk. I was experimenting about that. I didn't found any simple answers around. — RHGPT, Sep 21 '21 at 10:28
@VLAZ I think that answer the questions about program that persist the data on the disk. But If I want to index some data and store that on the disk in a persistent binary tree for faster lookup. To insert a new item in the tree, I need to have a static method on a class that can insert a new item into the tree and then serialize it back again to store it. Is that correct and efficient. — RHGPT, Sep 21 '21 at 10:40
@RHGPT depends. It might be efficient *enough*. Or might not be. If you need it faster, you could perhaps write the data as CSV (easy to append to) and also maintain an index of the data. So, you don't have to traverse the whole CSV to find something, for example. That will probably need to be re-synced but it does reduce the time to find stuff in the CSV. Or you can split up the data in other ways. Depends on what exactly you need to do with it and what is fast *enough* for the use case. — VLAZ, Sep 21 '21 at 10:43

score 1 · Accepted Answer · answered Sep 21 '21 at 20:31

JSON.parse can only produce a few data types: boolean, number, string, null, array and plain object. It cannot produce an instance of a custom class.

To ease that process, here are some ideas:

It is not necessary to serialise the next references of a linked list, since its order uniquely defines these links implicitly.
Serialise a linked list as if it was an array.
Make your linked list instances iterable. This way it is easy to turn an instance to an array (and serialise that).
Implement the toJSON method, which gets called by JSON.stringify
Allow the linked list constructor to take any number of arguments, which get added to the new list immediately. This is much like the Array constructor allows.
Implement a static fromJSON method that takes a JSON string and returns a linked list instance for it.

Here is that implemented:

class SinglyLinkedList {
    static Node = class {
        constructor(value, next=null) {
            this.value = value;
            this.next = next;
        }
    }
    constructor(...values) {
        this.head = this.tail = null;
        for (let value of values) this.push(value);
    }
    push(value) {
        let node = new SinglyLinkedList.Node(value);
        if (this.tail) {
            this.tail = this.tail.next = node;
        } else {
            this.head = this.tail = node;
        }
    }
    * [Symbol.iterator]() {
        for (let node = this.head; node; node = node.next) {
            yield node.value;
        }
    }
    toJSON() {
        return [...this];
    }
    static fromJSON(json) {
        return new this(...JSON.parse(json));
    }
}

// Demo
// 1. Constructor can accept values to be added to the list
const list = new SinglyLinkedList('Hello', 'World', '!');

// 2. A linked list can be iterated, so no specific print method is needed
console.log(...list);

// 3. JSON.stringify will call toJSON method
let serialized = JSON.stringify(list);
console.log(serialized);

// 4. fromJSON can be used to create a linked list instance from Array-like JSON
let restored = SinglyLinkedList.fromJSON(serialized);

// Again, iteration can be used for printing
console.log(...restored);

No. I think I got it. But the answer I was really looking for is "How does a program store data in a data structures on the disk". — RHGPT, Sep 23 '21 at 07:48
Oh, I see. Well, serialization is not specific to disk storage, it is just about producing a string. Once you have the string, you can decide to write it to a file, ...etc. Producing the string representation (here: JSON) should take care to not include redundant data (like for instance the `next` property in the case of a linked list). To *manipulate* such serialized data, the most sensible thing to do is to deserialize it, do the manipulation on the structured data, and then serialize it again. That is best practice. — trincot, Sep 23 '21 at 07:51
If it's not a general question can you tell me "What does it means that a db stores data in a b-tree ?" — RHGPT, Sep 23 '21 at 07:57
A b-tree is a structure that a DB uses for *indexing* tables. It allows to quickly find a record by its (indexed) key without having to scan the whole table. See for instance [how B-tree indexing works in mysql](https://stackoverflow.com/questions/2362667/how-b-tree-indexing-works-in-mysql), and [How Database stores data internally in B-Tree/B+Tree](https://stackoverflow.com/questions/4059920/how-database-stores-data-internally-in-b-tree-btree), and [How to lay out B-Tree data on disk?](https://stackoverflow.com/questions/40740752/how-to-lay-out-b-tree-data-on-disk). — trincot, Sep 23 '21 at 08:48

How to add an item to a serialized linked list in Javascript

1 Answers1