CODEWITHSUNDEEP
carraysmemory-managementstructlinked-list
Tamalero
Tamalero

Reputation: 471

Allocating memory for a array of linked lists

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.

Upvotes: 1

Views: 4300

Answers (2)

jasal
jasal

Reputation: 1053

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).

Upvotes: 3

arayq2
arayq2

Reputation: 2554

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.)

Upvotes: 1

Related Questions