Dynamically creating nodes for linked list of variable size

Question

For an assignment, I am tasked to created a multi-dimensional linked list based on a file input. Each node contains a seat object with the row, column(as a character), and character data of the file. For example, if the file was

ABC
DEF
GHI

Then the linked list would be (where - and | signify connected pointers)

A-B-C
| | |
D-E-F
| | |
G-H-I

I'm currently trying to create all of the nodes first, based on the number of elements in the file. I've created the head node but I am unsure how to go about allocating the rest of the variable number of nodes. So far I have 2 for loops traversing each character of the file to collect the row, column, and character, like so:

scanner.open(fileName);
   if(scanner)
      {
         for(int i = 0; i < cols; i++)
            {
               for(int j = 0; j < rows; j++)
                  {
                     if(i == 0 && j == 0)
                        {
                           Node<Seat> *headNode = new Node<Seat>(Seat(j, letter, c));
                           headNode->up = NULL;
                           headNode->left = NULL;
                           setFirst(headNode);
                           continue;
                        }
                     scanner >> c;
                     letter = ('A' + i);
                     Node<Seat> *curNode = new Node<Seat>(Seat(j, letter, c));
                     std::cout << "Row, seat, ticket: " << curNode->getPayload().getRow() << curNode->getPayload().getSeat() << curNode->getPayload().getTicketType() << std::endl;
                  }

            }
      }
}

Right now I am creating a single new node and printing it out to verify that it works (and it does), but I am unsure about how to go about creating a new, seperate node for each of the characters in the file. (If I can simply create them, I think I'll be able to figure out how to connect them.)

Wrong approach. You will have multiple head nodes, one for the head of each list (e.g . A, B and C. You then create an add_node() function that will allocate and initialize each node when it is read from the file and add it to the proper list (based on column number). Trying to allocate everything first is like trying to cram a square peg in a round hole -- not really what you want to do. add() example can be found here Singly Linked List (node only, no wrapper), template example C++ Template Singly-Linked List w/Sort — David C. Rankin
– David C. Rankin, Commented Oct 5, 2020 at 23:23
If your nodes are limited to a maximum of four links (as appears from your example) I would suggest not making them variable size, simply allocate four links for every node and leaving some null as appropriate. — SoronelHaetir
– SoronelHaetir, Commented Oct 5, 2020 at 23:25
I would suggest to start with one-dimensional list; then extend it to the second dimension. — Vlad Feinstein
– Vlad Feinstein, Commented Oct 5, 2020 at 23:40
Do the columns need to be lists? This would be simpler if it were only a list of rows. — Thomas Matthews
– Thomas Matthews, Commented Oct 5, 2020 at 23:44
@Siroos I would remind you that this is not your school. We are not going to grade your homework. You are allowed to make changes to (a copy of) your code to create a simpler minimal reproducible example for your questions here. In fact, such changes are encouraged! — JaMiT
– JaMiT, Commented Oct 6, 2020 at 2:47

Jerry Jeremiah · Accepted Answer · 2020-10-06 01:29:08Z

What I would do is keep two sets of pointers:

a "last row" and "this row" pointer to keep track of the start of the rows
a "last column node", "last row node" and "this node" pointer to keep track of the siblings

Then repeat these steps:

read a name from the file
create a node
hook up the siblings
update the pointers so "last..." points to "this..."

Here is a sample:

#include <fstream>
#include <sstream>
#include <iostream>
#include <string>

struct Node {
    std::string name;
    Node *up, *down, *left, *right;
    Node(std::string name) : name(name), up(NULL), down(NULL), left(NULL), right(NULL) {}
};

void dump(Node *this_node) {
    std::cout
        << " name="  << this_node->name
        << " up="    << (this_node->up?this_node->up->name:" ")
        << " down="  << (this_node->down?this_node->down->name:" ")
        << " left="  << (this_node->left?this_node->left->name:" ")
        << " right=" << (this_node->right?this_node->right->name:" ")
        << std::endl;
}

Node *print(Node *head) {
    Node *this_row = head;
    while (this_row) {
        Node *this_node = this_row;
        while (this_node) {
            dump(this_node);
            this_node = this_node->right;
        }
        this_row = this_row->down;
    }
    return head;
}

Node *read() {
    Node *head = NULL;
    std::fstream file("input.txt");
    if (file) {
        std::string line;
        Node *last_row = NULL;
        Node *this_row = NULL;
        while (std::getline(file,line)) {
            std::string name;
            std::stringstream ss(line);
            Node *last_row_node = NULL;
            Node *last_col_node = last_row;
            Node *this_node = NULL;
            while (ss >> name) {
                this_node = new Node(name);
                // if we haven't set these yet then do it now
                if (!head) head = this_node;
                if (!this_row) this_row = this_node;
                // if there was a last column then use it
                if (last_col_node) {
                    last_col_node->down = this_node;
                    this_node->up = last_col_node;
                }
                // if there was a last row then use it
                if (last_row_node) {
                    last_row_node->right = this_node;
                    this_node->left = last_row_node; 
                }
                // move right one column
                last_row_node = this_node;
                if (last_col_node)
                    last_col_node = last_col_node->right;
            }
            // move down one row
            last_row = this_row;
            this_row = NULL;
        }
    }
    return head;
}

int main() {
    Node *head = read();
    print(head);
}

Try it online: https://onlinegdb.com/HyW7SrY8v

Here is the grid it creates:

name=A up=  down=D left=  right=B
name=B up=  down=E left=A right=C
name=C up=  down=F left=B right= 
name=D up=A down=G left=  right=E
name=E up=B down=H left=D right=F
name=F up=C down=I left=E right= 
name=G up=D down=  left=  right=H
name=H up=E down=  left=G right=I
name=I up=F down=  left=H right=

This works great, and I've been trying to tweak it- how could I edit this so it would take characters without whitespace? I forgot to mention my file looks more like ABC, with no whitespace.

Thomas Matthews · Accepted Answer · 2020-10-05 23:48:35Z

0

IMHO, you're going to need four links in every node. Think of a chess board.

struct Node
{
    Node * up;
    Node * down;
    Node * left;
    Node * right;
};

The top row would have a nullptr value for the up field. Likewise for the other edges.

Adding a node would involve adjusting the appropriate links.

answered Oct 5, 2020 at 23:48

Thomas Matthews

58.1k18 gold badges105 silver badges165 bronze badges

2 Comments

Siroos Over a year ago

Forgot to mention that I do have those links, whoops. template<class T> class Node { public: Node *up; Node *down; Node *left; Node *right;

Thomas Matthews Over a year ago

Don't place code in comments. Edit your question with the code.

Collectives™ on Stack Overflow

Dynamically creating nodes for linked list of variable size

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related