Linked list within a linked list (2D linked list?)

11.4k views Asked by At

I have a txt file that contains a matrix of chars(1 or 2 at each position in matrix)

C P O Hr S A

N Hw N L Z R

W T O O Ta A

I O S S E T

Something like this. What I managed to do is to create a linked list and store every element of this matrix in that list (separately).

struct DataNode{
    char data[3];
    struct DataNode *nextData;
};

void initNode(DataNode *head, char x[3]) {
    for(int i=0; i<3; i++)
        head->data[i]=x[i];
    head->nextData=NULL;
}

void addNode(DataNode *head, char x[3]) {
    DataNode *newNode = new DataNode;
    for(int i=0; i<3; i++)
        newNode->data[i]=x[i];
    newNode->nextData=NULL;

    DataNode *curr = head;
    while(curr) {
        if(curr->nextData==NULL) {
            curr->nextData = newNode;
            return;
        }
        curr = curr->nextData;
    }
}

int main() {
char input[3];
if(in.is_open()) {
        in>>input;
        initNode(head,input);
        for(int i=0; i<3; i++)
            dieSide[i]=input[i];

        while(in>>input) {
            addNode(head,input);
        }
        in.close();
    }
}

So far, this works as it should, and I guess I'm happy with it.

What I need now, it another linked list, where the elements would still be char[3] types, but there has to be first a list containing a row of 6 elements, and then, another list, containing all of those 6 element lists.

I hope I made myself clear about my wishes.

I'm thinking about creating another struct, with next pointers to each of two active lists, but still not sure about that idea.

How would you recommend me to go about doing this?

EDIT

Just a little help, please... I have re-implemented all of the functions to suit the struct you (@Daniel) suggested, and they appear to work. However, I need a way to "reset" the DataNode* I want to use for creating small lists. This way I only get entire matrix printed as many times as there are lines in the file. What I have is>

char input[3];
int counter=0;
struct DataNode *head = new DataNode; //creates a list of all elements
struct DataNode *head_side = new DataNode; //want to use this one to create smaller lists
struct DieSideNode *head_die = new DieSideNode; //creates a list of smaller lists

if(in.is_open()) {
        in>>input;
        initNode(head,input);
        initNode(head_side, input);
        counter++;

    while(in>>input) {
        addNode(head,input);
        addNode(head_side, input);
        counter++;
        if( counter == 6 ) {
            initSide(head_die, head_side);
            head_side=0;
        }else if(counter%6==0) {
            addSide(head_die, head_side);
            head_side=0;
        }
    }
    in.close();
}

This code successfully extracts first six elements, and puts it as a first element of the list, but then it stops working there.

1

There are 1 answers

11
Daniel On

I'll give you a little hint to get started. As you know, a linked-list node contains some data and a pointer to the next element of the list. What you call a "2-d linked list" would actually simply be implemented as a linked-list of linked-lists. Each node in the list points to another linked list. So you will need to define a new type:

struct ListNode {
    DataNode* dataRowHead;
    struct ListNode* nextRow;
};

What you are trying to do would have 6 ListNodes connected as a linked-list. Each ListNode contains a pointer to a DataNode which is the head of a linked-list for the row that corresponds to the ListNode that points to it.

I will leave the implementation up to you.