C++ Linked list

Question

I'm trying to make linked list similar too the one here:

That is to have the "head", I called it first, inside another struct. However I found doing that change. Makes it hard to add values to the list_item struct. I have tried some few things to see if it works. It compiles, however when I run the code it will crash. Any help would be helpful here. I know the cause of the crash is when I want to point the new_node to the linked_list.

#include <iostream> using namespace std; struct list_item { int key; int value; list_item *next; }; struct list { struct list_item *first; }; int main() { list *head; list *new_node; head = NULL; head->first = NULL; for(int i = 0; i < 10; i++) { //allocate memory for new_node new_node = (list*)malloc(sizeof(list)); new_node->first = (list_item*)malloc(sizeof(list_item)); //adding the values new_node->first->key = i; new_node->first->value = 10 + i; //point new_node to first; new_node->first->next = head->first; //point first to new_node; head->first = new_node->first; } //print list *travel; travel->first = head->first; int i = 0; while(travel != NULL) { cout << travel->first->value << endl; travel->first = travel->first->next; } return 0; }

Note that C++ has std::list<> as a standard container available to you. For this reason, I'm removing your C++ tag. — ChrisInEdmonton
– ChrisInEdmonton, Commented Nov 28, 2009 at 16:43
If it's going to be tagged C and not C++, use structs instead of classes, and malloc instead of operator new, I'm tempted to edit this to start using printf, stop casting the return value of malloc, and not rely on an implict typedef from a struct definition :P — asveikau
– asveikau, Commented Nov 28, 2009 at 16:49

Lucas · Accepted Answer · 2009-11-28 16:38:15Z

You are creating 10 lists, I think you might try to do something like this:

#include <iostream> using namespace std; struct list_item { int key; int value; list_item *next; }; struct list { struct list_item *first; }; int main() { //Just one head is needed, you can also create this // on the stack just write: //list head; //head.first = NULL; list *head = (list*)malloc(sizeof(list)); list_item *new_node = NULL; head->first = NULL; for(int i = 0; i < 10; i++) { //allocate memory for new_node new_node = (list_item*)malloc(sizeof(list_item)); //adding the values new_node->key = i; new_node->value = 10 + i; //if the list is empty, the element you are inserting //doesn't have a next element new_node->next = head->first; //point first to new_node. This will result in a LIFO //(Last in First out) behaviour. You can see that when you //compile head->first = new_node; } //print the list list_item *travel; travel = head->first; while(travel != NULL) { cout << travel->value << endl; travel = travel->next; } //here it doesn't matter, but in general you should also make //sure to free the elements return 0; }

This is what is going on. At first you only have one head and no elements.

head | | V NULL

Then you add your first element. Make sure that the "new_node->next==NULL":

head | | V node: ------------------> NULL key = 0 value = 10

Then you add another node in front but append your first node to its next node. you move the pointer from the head to the new node

head: first | | V node: ---------> node: -------------> NULL key: 1 key: 0 value: 11 value: 10

etc.

Since you are using c++, you might consider using "new" and "delete". Just replace

new_node = (list_item*)malloc(sizeof(list_item));

with

list *head = new list

hey, I'm going through the code. Trying to understand it. Feel very noobish but I seem not to find the reason why the if-statement inside the loop erases the NULL at the end of the list if ( head->first != NULL) If it's there the travel loop will crash.
@klw: I just realized what you meant. Of course, you are 100% correct. Since head->first is already pointing to NULL the if ... else ... is completely useless.

Donnie · Accepted Answer · 2009-11-28 15:03:40Z

The next line only allocates memory for your list struct. The list contains only a pointer, you must also allocate memory for new_node->first before assigning to any of its members.

//allocate memory for new_node new_node = (list*)malloc(sizeof(list));

I added malloc for it now but it still crashes. Do I still miss something out? I updated the code with the changes

Gabe · Accepted Answer · 2009-11-28 15:36:48Z

I think you want something more like this:

#include <iostream> #include <cstdlib> using namespace std; typedef struct tag_list_item { int key; int value; struct tag_list_item *next; } list_item; typedef struct { list_item *head; } list; int main() { list my_list; list_item *new_node; list_item *previous_node = NULL; my_list.head = NULL; for(int i = 0; i < 10; i++) { //allocate memory for new_node new_node = (list_item*)malloc(sizeof(list_item)); //adding the values new_node->key = i; new_node->value = 10 + i; if(previous_node == NULL) { my_list.head = new_node; } else { previous_node->next = new_node; } previous_node = new_node; } //print list_item *iter = my_list.head; while(iter != NULL) { cout << iter->value << endl; iter = iter->next; } return 0; }

Changes of note:

For malloc, I added:

#include <cstdlib>

I changed your list structures to typedefs, had to declare "next" using the tag since the typedef isn't complete at that point

typedef struct tag_list_item { int key; int value; struct tag_list_item *next; } list_item;

I changed your list name to "my_list" and declared it directly (without the pointer). In this case you can just have the compiler allocate it automatically on the stack.

list my_list;

I keep a pointer for "previous_node" so that you can assign the "next" pointer much more easily. Notice that the first node allocated is pointed to by the "head" pointer in the list structure. I believe that is the traditional name for the pointer to the first element in a list.

if(previous_node == NULL) { my_list.head = new_node; } else { previous_node->next = new_node; } previous_node = new_node;

Billy ONeal · Accepted Answer · 2009-11-28 15:26:02Z

head = NULL; head->first = NULL;

There's the issue. You can't follow a pointer and set it to NULL if you've set the pointer itself to NULL.

That should be

head = malloc(sizeof(list)); head->first = NULL;

That should fix your code.

Hope that helps, Billy3

EDIT: There's also an issue with your FOR loop. When you allocate the list, you should only allocate the list itself once. When you insert an item, you only allocate a list_item. You're assigning a list pointer to a member which accepts only a list_item pointer ;)

See Gabe's post for a demonstration of correct behavior :)

t0mm13b · Accepted Answer · 2009-11-29 00:58:40Z

Look at your struct declaration

 struct list_item { int key; int value; list_item *next; };

That should be

 struct list_item { int key; int value; struct list_item *next; };

Hope this helps, Best regards, Tom

Not in C++. That would be correct in C. The OP's issue is not a compile-time issue, rather a run time Segmentation Fault.

Collectives™ on Stack Overflow

C++ Linked list

5 Answers 5

2 Comments

1 Comment

Comments

Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

1 Comment

Comments

Comments

1 Comment

Linked

Related