6

I am trying to teach myself linked-lists with node structs and was hoping someone could help me with this. I would take input from the command line and it would make me a nested list and I could output it.

Example:

Input: "1 2 3 4 5"
Output:"1 2 3 4 5"

There are two things I am having trouble with: 1) When I run the program I keep getting warning: ‘typedef’ was ignored in this declaration [enabled by default] How can I get rid of this?

EDIT: I have changed this to typedef struct Node* NodePtr;

2) My code is not working properly. How can I fix this? I am trying to teach myself linked lists in C++.

typedef struct Node; typedef Node* NodePtr; struct Node{ int x; NodePtr next; }; int main () { int n; NodePtr head, ptr = NULL; head = ptr; while (cin >> n){ ptr = new Node; ptr->x = n; ptr->next = NULL; ptr = ptr->next; } NodePtr bling = head; while(bling != NULL){ cout << bling->x << endl; bling = bling->next; } return 0; }

Ideally what I want to do is to make a linked-list like the following.

1 -> 2 -> 3 -> NULL.
Improve this question
8
  • 3
    I think you meant typedef struct Node {...} *NodePtr; instead of the first two typedefs, unless you really want the NodePtr inside the structure, in which case you'd have to do it a little differently before. Commented Jan 27, 2013 at 4:51
  • By "My code is not working properly" what do you mean? Is there an error? Commented Jan 27, 2013 at 4:52
  • @Quirliom it does not work like it will not print out the data, which makes me think I am connecting the nodes properly Commented Jan 27, 2013 at 4:53
  • @chris I just want NodePtr to be typedef so I would not have to write "struct Node*" everywhere when defining a pointer of this type Commented Jan 27, 2013 at 4:56
  • 2
    @Masterminder, You don't. You only have to type Node * anyway. Commented Jan 27, 2013 at 4:58

4 Answers 4

Reset to default
9

First, regarding the declaration of your structure and the pointer typedef you seem to want, there are a number of ways of doing this. The following will work in C or C++.

// declare NodePtr as a pointer to Node, currently an incomplete type // C and C++ both allow you to declare a pointer to damn-near anything // so long as there is an understanding of what it *will* be, in this // case, a structure called Node. typedef struct Node *NodePtr; // Now declare the structure type itself struct Node { int x; NodePtr next; };

That said, I honestly do not recommend doing this. Most engineers want a clear and syntax-visible definition that screams to them, "THIS IS A POINTER!" You may be different. I, personally would simply prefer this:

struct Node { int x; struct Node *next; // omit the 'struct' for C++-only usage };

So long as you, and equally important, other engineers reading your code, understand your usage of NodePtr as a pointer-to-node, then go with what works best in your situation. Pointer type declaration is near-religious to some, so just keep that in mind. Some prefer seeing those asterisks (I being one), some may not (sounds like you =P).

Note: there is one place that using a typedefed pointer-type can be beneficial in avoiding potential errors: multiple variable declarations. Consider this:

Node* a, b; // declares one Node* (a), and one Node (b)

Having a typedef struct Node *NodePtr; allows this:

NodePtr a, b; // declares two Node*; both (a) and (b)

If you spend enough time writing code in C the former of these will come back to bite you enough times you learn to not make that mistake, but it can still happen once in awhile.

The Load Loop

Regarding the load-loop for piecing together your list, you're not wiring up your list correctly, and frankly there are a million ways to do it, one being the one below. This does not require you to clean out "an extra node". Nor does it require any if (head){} else{} block structure to avoid said-same condition. Consider what we're really trying to do: create nodes and assign their addresses to the right pointers:

NodePtr head = NULL; // always the head of the list. NodePtr* ptr = &head; // will always point to the next pointer to assign. int n; while (cin >> n) { *ptr = new Node; (*ptr)->x = n; ptr = &(*ptr)->next; } // note this always terminates the load with a NULL tail. (*ptr)->next = NULL;

How It Works

  1. Initialize the head pointer to NULL
  2. Initializer a Node pointer-pointer (yes a pointer to a pointer) to point to the head pointer. This pointer-to-pointer will always hold the address of the target pointer that is to receive the address of the next dynamic-allocated node. Initially, that will be the head pointer. In the above code, this pointer-to-pointer is the variable: ptr.
  3. Begin the while-loop. For each value read, allocate a new node, saving it in the pointer that is pointed-to by ptr (thus the *ptr). On the first iteration this holds the address of the head pointer, so the head variable will get our new node allocation. On all subsequent iterations, it contains the address of the next pointer of the last node inserted. Incidentally, saving the address of this new target pointer is the last thing that is done in the loop before we move to the next allocation cycle.
  4. Once the loop is complete, the last node inserted needs to have its next pointer set to NULL to ensure a properly terminated linked list. This is mandatory. We conveniently have a pointer to that pointer (the same one we've been using all this time), and thus we set the pointer it "points to" to NULL. Our list is terminated and our load is complete. Brain Food: What pointer will it be pointing to if the load loop never loaded any nodes? Answer: &head, which is exactly what we want (a NULL head pointer) if our list is empty.

Design

I hope this will help better explain how it works through three full iterations of the loop.

Initial configuration

 head ===> NULL; ptr --^

After one iteration:

head ===> node(1) next ptr ------^

After two iterations

head ===> node(1) next ===> node(2) next ptr ----------------^

After three iterations

head ===> node(1) next ===> node(2) next ===> node(3) next ptr --------------------------^

If we stopped at three iterations, the final termination assignment (*ptr = NULL;), gives:

head ===> node(1) next ===> node(2) next ===> node(3) next ===> NULL; ptr --------------------------^

Notice that head never changes once the first iteration is finished (it always points to the first node). Also notice that ptr always holds the address of the next pointer that is to be populated, which after the initial iteration (where it started as the address of our head pointer), will always be the address of the next pointer in the last node added.

I hope that gives you some ideas. It is worth noting that pairing these two pointers (the head pointer and the ptr pointer) into their own structure and having the appropriate management functions defines the textbook Queue; where one end is only for insertions (ptr) one is for extractions (head) and the container does not allow random access. There isn't much need for such a thing these days with the standard library container adapters like std::queue<>, but it does provide an interesting adventure into a good use of pointer-to-pointer concepts.

Complete Working Sample

This sample just loads our queue with 20 elements, prints them, then cleans out the queue and exits. Adapt to your usage as needed (hint: like change the source of the incoming data perhaps)

#include <iostream> using namespace std; // declare NodePtr as a pointer to Node, currently an incomplete type // C and C++ both allow you to declare a pointer to damn-near anything // so long as there is an understanding of what it *will* be, in this // case, a structure called Node. typedef struct Node *NodePtr; // Now declare the structure type itself struct Node { int x; NodePtr next; }; int main() { // load our list with 20 elements NodePtr head = NULL; NodePtr* ptr = &head; for (int n=1;n<=20;++n) { *ptr = new Node; (*ptr)->x = n; ptr = &(*ptr)->next; } // terminate the list. *ptr = NULL; // walk the list, printing each element NodePtr p = head; while (p) { cout << p->x << ' '; p = p->next; } cout << endl; // free the list while (head) { NodePtr victim = head; head = head->next; delete victim; } return 0; }

Output

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

Would this be correct as well to type def it so I could avoid the ? typedef struct Node NodePtr; struct Node{ int x; NodePtr next; };
@Masterminder I'll update the head of this answer to reflect the structure definition I think you're having problems with. Most everyone else already has which was why I avoided it, but if you want it here as well I'll certainly provide it.
Thank you I am trying to run your code with my structure definiton and am getting a segmentation fault
@Masterminder then it is highly likely your structure is not declared correctly. see the updated post above, including both how to declare your structure and structure pointer, as well as the complete working sample at the end.
instead of ... NodePtr* ptr = &head; ... can i just do this? int n; NodePtr head, ptr; ptr = head; while (cin >> n){ ptr = new Node; ptr->x = n; ptr->next = NULL; ptr = ptr->next; }
|
3

You do not actually set the 'head' variable beyond NULL(head = ptr). You you actually lose your list from the get go. Try this:

int n; NodePtr head, ptr; ptr = new Node; head = ptr; while (cin >> n){ ptr->x = n; ptr->next = new Node; ptr = ptr->next; }

You may then want to delete the last ptr->next and set it to 0 to save memory and avoid printing out an extra value.

Improve this answer

4 Comments

Thanks for the answer. So suppose I have 1 2 3 4 5 will this code create 1 2 3 4 5 plus an extra node and then I will have to set to NULL?
It's untested, but in theory yes.
How can I make it so I do not have to create the extra node? Because is that not unnecessary allocation of memory? So something like ... 1-> 2-> 3-> NULL
@Masterminder by (a) not allocating until you need to, and (b) assigning directly to the pointer that you want to own the new allocation. it is quite doable.
1

First, your typedef : typedef struct Node; is not correct. You declare a struct with the sintaxe:

struct st_Name{ int field1; double field2; };

Typedef is like a name attribution function. You should (for easier reading/working) change the name of your struct, wich is possible, after declaring it, with:

typedef struct Node_st Node;

Or, all in one statement:

typedef struct node_st{ int x; struct node_st *next; }Node;

In the segment above, notice that I also changed the NodePtr to struct node_st *Next for a reason: If you do all in one segment, since c++ code is read linearly top->down(kinda), if you try to make NodePtr a pointer to Node before the struct declaration you'll get an error, and if you do it later and use NodePtr inside the struct you'll also have an error. The compiler don't know yet that the struct exists so it will say that you're trying to name something that does not exist.

Then, your pointers manipulation is wrong. 

... while (cin >> n){ ptr = new Node; ptr->x = n; ptr->next = NULL; // You're making the next slot inexistent/NULL ptr = ptr->next; // You're just setting ptr to NULL } ...

What I think that you want is to keep adding to the end a keep the head in the first number. You can do this simply with an if/else statement for the first case:

 while (cin >> n){ if(head == NULL){ ptr = new Node; ptr->x = n; ptr->next = NULL; head = ptr; }else{ ptr->next = new Node; ptr = ptr->next; ptr->x = n; ptr->next = NULL; } }

This way, your insertion happens in the end so your print loop should work.

Hope this helps.

Improve this answer

2 Comments

so like how would a node pointer look like? I want to avoid writing "node* "
If, after the all in one declaration, you do typedef Node* NodePtr. a pointer declaration would look like NodePtr aPointer;
1

You aren't connecting the list. Every new item will have it's ->next NULL.

You say ptr = ptr->next (which is NULL) but then the next iteration overwrites ptr with the newly allocated node. You need to rearrange your code to string the nodes together...

One way of doing that is ptr->next = head makes your new node point to the old head. Then head = ptr to move the head to the new node. e.g.:

To insert in the beginning (e.g. for a LIFO, last-in-first-out):

while (cin >> n){ ptr = new Node; ptr->x = n; ptr->next = head; head = ptr; }

To insert at the end (for a FIFO):

while (cin >> n){ if(!head) { head = new Node; ptr = head; } else { ptr->next = new Node; ptr = ptr->next; } ptr->next = NULL; ptr->x = n; }
Improve this answer

8 Comments

what if I want to insert at the end of the list? SO like 1 2 3 4 5 ... 1 -> 2 -> 3 -> 4 -> 5 -> NULL
@Masterminder. Then you need a pointer to the head which is set when you allocate the very first node. After that you keep a pointer to the last node similar to Quirliom's answer... I could write this code for you but you'd enjoy it more figuring it our yourself. :-)
:D Well I know I would have to keep a pointer to the very beginning and just keep adding but what I am unsure of is that to write code so I do not have to make an unnecessary allocation, like I do not want to this 1 2 3 4 5 plus an extra node, what I want to do is 1-> 2-> 3-> 4-> 5 -> NULL
@Masterminder. You can do that with an if statement, check if the head is NULL as a special case. If it is, allocate new node and assign it to the head. If it's not allocate new node in ptr->next.
@Masterminder: yes, assigning one pointer to another means they contain the same address which means point to the same thing.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.