CODEWITHSUNDEEP
clist
MrSykkox
MrSykkox

Reputation: 528

Linked list initialization

I trying to create a linked list in C, but I get one more element in the list than I expect.

#define SIZE_OF_LIST 10 

int main()
{
  struct node* head = NULL;
  struct node* item = NULL;

  int i;

  head = (struct node*)malloc(sizeof(struct node));
  item = (struct node*)malloc(sizeof(struct node) * 10);

  head->data = 999;
  head->link = item;

  // Create a list of 10 elements
  for (i = 0; i < SIZE_OF_LIST; i++)
    {
      (item+i)->data = i;
      printf("(item+%d)->data = %d\n",i,i);
      if (i<SIZE_OF_LIST-1)
      {
          (item+i)->link = (item+i+1);
           printf("(item+%d->link = (item+%d+1);\n", i, i);
      }
      else 
      {
          (item+i)->link = NULL;
          printf("(item+%d->link = NULL;\n", i);
      }
    }

  printf("Items : %d\n", getListLength(head));
  PrintListData(head);
  return 0;
}

So I created 2 functions. One to determine the length of the list, by running through nodes until it find the end node (link=NULL). And i created a function which prints out the data of the list.

void PrintListData(struct node* list)
{
  int i = 0;
  int list_length = getListLength(list);

  for (i = 0; i < list_length; i++)
  {
      printf("List[%d] = %d\n", i, (list+i)->data);
  }
}

So I expect the list to hold head+10 items in the list, but my output is:

Items : 12
List[0] = 999
List[1] = 0
List[2] = 0
List[3] = 1
List[4] = 2
List[5] = 3
List[6] = 4
List[7] = 5
List[8] = 6
List[9] = 7
List[10] = 8
List[11] = 9

So it seems like there is an extra element at position 1 of the list? What am I doing wrong?

Upvotes: 1

Views: 3924

Answers (2)

Manoj Awasthi
Manoj Awasthi

Reputation: 3520

The above answer points to the problem correctly. Going with the semantics of Linked list, I'd rather implement your function as this: 

int getListLength(struct node *head) {
  struct node *current = head;
  int len = 0;
  if (current) {
    while(current->link != NULL) {
      len ++;
      current = current->link;
    }
  }
  return len;
}

void PrintListData(struct node* head) {
  int index = 0;
  struct node *current = head;
  if (current) {
    while(current != NULL) {
      printf("List[%d] = %d\n", index, current->data);
      index ++;
      current = current->link;
    }
  }
}

Upvotes: 1

R Sahu
R Sahu

Reputation: 206567

Your implementation of PrintListData is wrong. It should be:

void PrintListData(struct node* list)
{
   int index = 0;
   for ( ; list != NULL; list = list->link, ++index )
   {
      printf("List[%d] = %d\n", index, list->data);
   }
}

Looking at how you have implemented PrintListData, I am going to guess that you have a similar error in getListLength

The implementation of getListLength should be something like:

int getListLength(struct node* list)
{
   int len = 0;
   for ( ; list != NULL; list = list->link, ++len );
   return len;
}

Upvotes: 2

Related Questions