writing a singly linked list to a file

[gevCplus]

Hello,

I have the following singly linked list class:

class singlylinkedlist1 {    
public:
    node* head;   
    singlylinkedlist1() {   
        head = NULL;   
    }
    singlylinkedlist1(node* n) {   
        head = n;    
    }
    void func1(){};
    int func2 (){};
       etc...
};

I want to write an object of the above class list to a file (say object list s). I tried to do it with the following code:

ofstream outfile;
outfile.open("data.txt", ios::app);
outfile.write((char*)&s, sizeof(s));
outfile.close();

However, the result is that it does not work for some reason. What could it be?

[jonnin]

you cannot write a linked list to a file directly. You are saving the pointers, which are invalid after the program ends, and not the data pointed to.

there are 2 primary ways to handle this. Method one is to put the linked list into something like a vector and change the pointers to the indices into the vector, then just write the vector out.
method 2 is to iterate the list and write the DATA to the file, and rebuild the list from scratch by reading each record from the file and inserting it into your list object one by one.

in method 2, you can waste space to save effort and time: write each node to the binary file one by one, but when you read it, you must IGNORE the pointers entirely and rebuild as I said, even though you saved them. Basically, saving the pointers on each node wastes the space the pointer variables consume, but it allows a simple write() statement. If you want to avoid wasting the space, you have to write() it field by field, leaving the pointers out.

In method 1, you will want to add a boolean 'deleted' or 'empty' to node so that you can reuse deleted vector locations and skip unused locations when processing it.

if NODE itself is a template, you must assume that NODE may also contain the pointer problem and cannot be safely written out with write() directly. EG if NODE is a next pointer and a vector<int> or string as the data parts, write() has the same problem again: you can't write the pointer, you have to write the data (vectors, strings, and stl containers in general use pointers for the data portions under the hood). If NODE is a simple type like int or double etc, you can use write() on it directly.

basically, write() on something that is full of pointers writes the pointer's value to the file, not the data under the pointer, and this issue crops up a lot with the STL, so you need to understand this concept and how to deal with it. Also, write() dumps a block of bytes to the file. The blocks must be in sequential memory, like an array. You can't dump a linked list or tree: the nodes are not adjacent to each other in memory (classic pointers approach) unless you forced them to be that way (method 1 above!).

[seeplus]

This is called data serialization. It is a big topic and there's loads of info about it available on the Internet.

[dutch]

As seeplus said, you're looking for "serialization". In general it's quite complicated and we tend to use a pre-written library to accomplish it. Using the boost serialization library, the "list_of_lists" code might look something like the following.

// https://www.boost.org/doc/libs/1_75_0/libs/serialization/doc/index.html
// You obviously need to install boost, and the serialization library
// needs to be compiled.
// Then compile this program with -lboost_serialization

#include <iostream>
#include <fstream>
#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>

template <typename T>
struct Node
{
    T     data;
    Node* next;

    template<class Archive>
    void serialize(Archive & ar, unsigned)
    {
        ar & data;
        ar & next;
    }

    Node(const T& d = T(), Node* n = nullptr) : data(d), next(n) { }
};

template <typename T>
class SinglyLinkedList
{
    Node<T>* head = nullptr;
    Node<T>* tail = nullptr;

public:
    SinglyLinkedList() = default;

    SinglyLinkedList(const SinglyLinkedList& s)
    {
        for (auto node = s.head; node; node = node->next)
            append(node->data);
    }

    SinglyLinkedList(SinglyLinkedList&& s)
    {
        head = s.head;
        tail = s.tail;
        s.head = s.tail = nullptr;
    }

    ~SinglyLinkedList()
    {
        for (auto node = head; node; )
        {
            auto xnode = node;
            node = node->next;
            delete xnode;
        }
    }

    void append(const T& data)
    {
        auto node = new Node<T>(data);
        (tail ? tail->next : head) = node;
        tail = node;
    }

    template<class Archive>
    void serialize(Archive & ar, unsigned)
    {
        ar & head;
        ar & tail;
    }

    friend std::ostream& operator<<(std::ostream& out,
                                    const SinglyLinkedList& list)
    {
        for (auto node = list.head; node; node = node->next)
            out << node->data << '\n';
        return out;
    }
};

template<typename T>
void save_list(const SinglyLinkedList<T>& list, const std::string& filename)
{
    std::ofstream out(filename);
    boost::archive::text_oarchive oa(out);
    oa << list;
}

template<typename T>
void load_list(SinglyLinkedList<T>& list, const std::string& filename)
{
    std::ifstream in(filename);
    boost::archive::text_iarchive ia(in);
    ia >> list;
}

#if 1

// Writing the list to "listfile.txt".
int main()
{
    SinglyLinkedList<int> lists[4];
    for (int n: {1, 2, 3, 4, 5})  lists[0].append(n);
    for (int n: {6, 7, 8})        lists[1].append(n);
    for (int n: {9, 10})          lists[2].append(n);
    for (int n: {11, 12, 13, 14}) lists[3].append(n);
    SinglyLinkedList<SinglyLinkedList<int>> list;
    for (int i = 0; i < 4; ++i) list.append(lists[i]);
    std::cout << list;
    save_list(list, "listfile.txt");
}

#else

// Reading the list from "listfile.txt".
int main()
{
    SinglyLinkedList<SinglyLinkedList<int>> list;
    load_list(list, "listfile.txt");
    std::cout << list;
}

#endif 

listfile.txt looks like this:

22 serialization::archive 12 0 0 1 1 0
0 0 0 3 1 0
1 1 3
2 2 3
3 3 3
4 4 3
5 5 -1 3 5 1
6 3
7 6 3
8 7 3
9 8 -1 3 9 1
10 3
11 9 3
12 10 -1 3 12 1
13 3
14 11 3
15 12 3
16 13 3
17 14 -1 3 17 -1 1 13

This looks like jonnin's idea of converting the pointers to indices.

[gevCplus]

Thank you guys all. I will search more on the serialization topic

@dutch: That is quite a code. Doing it with jonnin's method 2, can I write something like the following to traverse and write the key and data of the list to my file?

if (head == NULL) {
            cout << "No nodes  in the list ";
        }
        else {
            ofstream outfile;
            outfile.open("data.txt", ios::app);
            node* temp = head;
            while (temp != NULL) {
            outfile << "[" << temp->key << " | " << temp->data << "]" << endl;
                temp = temp->next;
            }
            outfile.close();
        }
    

Just to let you know, I only intend to write to a file and not to be able to read from that.

[dhayden]

If you write the list that way, then how will you read it? You need some sort of sentinel to signal the end of the list. When you have that, you don't need a special case for an empty list.

[jonnin]

yes, you can do that.
To the above post, you should track the # of items in your list (++ when you insert, -- when you delete is sufficient) and you can write that, making the file something like:

5
[0|100]
[1|101]
[2|102]
[3|103]
[4|104]

which is fine. You tossed out your write() which is also fine if a text file does what you need. Its at least better to do text files at first, to get it working, then if you want to revisit binary files you can.

[gevCplus]

@dhayden: I don't want to read the data from the file anyway. Thanks

@jonnin: Thanks jonnin. One more help. I have a problem with a method for adding the data from the nodes. The code I use is the following:

void inodesum(node* head, int* sum1)
    {
        // if head = NULL 
        if (!head) {
            return;
        }

        inodesum(head->next, sum1);
 
        *sum1 = *sum1 + head->data;
    }

    int nodesum1(node* head)
    {
        int sum1 = 0; 
        inodesum(head, &sum1);
        return sum1;
    }

, and with the following implementation code:

node* head = n1;
cin>>key1;
cin >> data1;
n1->data = data1;
n1->key=key1;
cout << "\nThe sum of nodes: " << endl;
cout << s.nodesum1(head);

However, it doesn't work as it only prints the data of the first node, which is the one I give at cin.

Any ideas?

[jonnin]

all I see is you gave it one node. If you tried to load from a file or put more nodes in, you forgot to give us that code part. I would expect this to do what you said, and operate on the one and only node.

[gevCplus]

Hello Jonnin. Yes I gave it one node and this is that it confuses me somehow. I gave one node with the intention to pass it as an argument to the method and the method to recursively go from the head node to the end of the list and sum the data in the nodes. However it seems that there is something I am missing in this logic. How can I pass the first node and the method to go on with summing all the next nodes of the list?

[keskiverto]

You did pass the "first node of a list". Your issue is that your "list" has only that one node (as far as we can see).

[gevCplus]

Ok, I am putting some of my code in summary (I didn't include the node class as I didn't want to fill the post with so much code):

class singlylinkedlist1 {    
public:
    node* head;   
    singlylinkedlist1();
    singlylinkedlist1(node* n);
    node* nodeExists(string k);
    void appendnode(node* n);
    void prependnode(node* n);
    void insertnodeafter(string k, node* n);
    void deletenode(string k);
    void updatenode(string k, int d);
    void printlist();
    void savetofile1();
}

int main(int argc, char* argv)
{
    system("title ..........");
  
    system("color 17");  

    int option;

    static singlylinkedlist1 s;
   
do {
        int choose;
        string key1, k1;
        int data1;
        do {
            cout << "\nSelect an operation:" << endl;
            cout << "0. Return to initial menu" << endl;
            cout << "1. Append node " << endl;
            cout << "2. Prepend node" << endl;
            cout << "3. Insert node" << endl;
            cout << "4. Delete node" << endl;
            cout << "5. Update node" << endl;
            cout << "6. Print" << endl;
            cout << "7. Clscr" << endl;
            cout << "8. sum nodes" << endl;
            cin >> choose;
            node* n1 = new node();
            switch (choose) {
            case 0:
                break;
            case 1:
                cin >> key1;
                cin >> data1;
                n1->key = key1;
                n1->data = data1;
                s.appendnode(n1);
                break;
            case 2:
                cin >> key1;
                cin >> data1;
                n1->key = key1;
                n1->data = data1;
                s.prependnode(n1);
                break;
            case 3:
                cin >> k1;
                cin >> key1;
                cin >> data1;
                n1->key = key1;
                n1->data = data1;
                s.insertnodeafter(k1, n1);
                break;
            case 4:
                cin >> k1;
                s.deletenode(k1);
                break;
            case 5:
                cin >> key1;
                cin >> data1;
                s.updatenode(key1, data1);
                break;
            case 6:
                s.printlist();
                break;
            case 7:
                system("cls");
                break;
            case 8:
                //Here is where I want to apply the node summing
                break;
            default:
                cout << "Wrong number! Enter number 1-8!" << endl;
                break;
            }

    } while (choose != 0);
   return 0;
 }

@keskiverto: I have set a menu so as to build the list by adding, deleting or updating nodes. When I build the list then with the above summation code, how could pass as argument the head node and the method will recursively sum all of the lists nodes, in the menu's case 8?