Linked lists in C++

Question

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.

Answer 1

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 

Answer 2

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.

Answer 3

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.

Answer 4

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;
}