1

Hi guys I'm new to linked lists, but I'm pretty sure that I know how they work, theoretically, I think I might having a syntax misunderstanding, or memory management error.

edit: My main purpose is to make a collection of lists which are indexed by the array, each array element is a head(or root) node. I'm having issues allocation dynamically this struct array.

What I'm doing is the following:

typedef struct item_list{
int item_name;
int item_supplier;
int item_price;
struct item_list *next
}node; 

int i;
node ** shop_1 = (node **)malloc(shop_items_elements * sizeof(node)); 

for (i=0;i<=shop_items_elements;i++)
{
    shop_1[i]->next=NULL;
}

I'm getting a segmentation fault while I try to give next at the element i the value of NULL.

Improve this question
3
  • 2
    Your types don't match the malloc argument. Commented May 26, 2014 at 19:28
  • 2
    1) node ** shop_1 = ... --> node * shop_1 = ... 2) for (i=0;i<=shop_items_elements;i++) -->> for (i=0;i < shop_items_elements;i++) 3) shop_1[i]->next=NULL; -->> shop_1[i].next = NULL; Commented May 26, 2014 at 19:29
  • I have a shop_items_elements of 20000 but it stops(segmentation fault) at 7999. As above Kerrek says, there's something with the dimensions allocated... but I don-t know what. Commented May 26, 2014 at 19:44

2 Answers 2

Reset to default
3

The problem is that you are trying to allocate the memory for 20000 items as a contiguous block. Which implies that you actually haven't understood linked lists yet.

I think you are mixing up random access array functionality with pure linked lists which do not allow accessing individual items without traversing the list.

A linked list usually has a head and tail node which are initially NULL when there are no elements in the list:

node* head = NULL;
node* tail = NULL;

When adding a new node you first allocate it by using malloc with the size of a single node struct:

node* the_new_node = (node*)malloc(sizeof(node));

Initialize the struct members, specifically set next to NULL for each new node. Then use this append_node() function to append the node to the linked list:

void append_node(node** head, node** tail, node* the_new_node)
{
  if(*tail == NULL)
  { // list was empty
    *head = *tail = the_new_node;
  }
  else
  {
    (*tail)->next = the_new_node; // link previous tail node with new one
    *tail = the_new_node; // set the tail pointer to the new node
  }

Please note the pointer to pointers which are needed to update the head and tail pointers. Call the function like this for any given n you want to add:

append_node(&head, &tail, n);

Repeat this for every new node.

A much better way of encapsulating a linked list is putting the head and tail pointers into another struct

typedef struct linked_list
{
  node* head;
  node* tail;
} list;

and using an instance of that as first argument to append_node() (which I'll leave to you as an exercise ;)

When using such a linked list it is not possible to conveniently access the Nth node in less than O(n) since you have to follow all next pointers starting from the head node until you arrive at the Nth node.

EDIT: If you want to have the possibility to index the shop items and build a linked list from each of the elements I would suggest the following solution:

node** shop_1 = (node**)malloc(shop_items_elements * sizeof(node*));
int i;
for(i = 0; i < shop_items_elements; ++i)
{
  node* n = (node*)malloc(sizeof(node));
  n->next = NULL;
  shop_1[i] = n;
}

You first allocate an array of pointers to node pointers which have to be allocated individually of course. Take a look at this diagram for reference:

enter image description here

The actual node instances may be larger than a pointer's size (unlike drawn in the diagram) which is the reason why you allocate N * sizeof(node*) in a block instead of N * sizeof(node).

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I liked your explanation, a lot, but the reason behind the array is that I want a collection of lists, each array's element is a head node or root node for a list. Let me update my post because I think it is misleading because of lack of information.
1

Your code needs to look like this

int i;
node * shop_1 = (node *)malloc(shop_items_elements * sizeof(node)); 

for (i=0;i<shop_items_elements;++i)
{
    shop_1[i].next=NULL;
}

Your malloc statement has allocated an array of nodes, not an array of pointers to nodes. (If that is what you wanted instead, then you would have had to initialize each pointer with a further malloc call before trying to assign a value to a field within the node pointed to.)

Improve this answer

6 Comments

i<shop_items_elements
Still not a linked list though. Just an array.
True. There were three confusions here, the linked list business to start with, what the malloc statement was doing, and the purpose of the loop.
You are right weston, but it is what I wanted, the allocation for the struct intended for a linked list, that array contains all the heads or roots for the lists. I tried this and I got segmentation fault at making NULL the element number 7034 (out of 20000)
@Tamalero: Did you check the return value from malloc()? What's here should do the job you seek to have done. 'Tis odd that it is at element 7034 of 20000. On a 32-bit system, the size of a node is 16 bytes; on a 64-bit system, it will be 24 bytes. That gives a total array size of about 320 KiB or 480 KiB. Neither of those is normally big enough to give problems on a modern desktop or laptop machine (or even a most mobile systems). It is unlikely that you've run out of memory. That makes a crash all the more puzzling. Have you got valgrind available? If so, use it.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.