A Simple Illustration of Link List

[devarishi]

Hi,


I am not getting Link List at all. Can anybody help me understand it? I have got an example program which is as follows:

#include <stdio.h>

struct list_el {
   int val;
   struct list_el * next;
};

typedef struct list_el item;

void main() {
   item * curr, * head;
   int i;

   head = NULL;

   for(i = 1; i <= 10; i++) {

      curr = (item *) malloc( sizeof(item) );

      curr->val = i;

      curr->next  = head;
      head = curr;
   }

   curr = head;

   while(curr) {
      printf("%d\n", curr->val);
      curr = curr->next ;
   }
}

And here's the output:

10
9
8
7
6
5
4
3
2
1

Could you explain me the above program statement-wise? And also explain the notation:

typedef struct list_el item;

Thanks in advance!

[itCbitC]

Here's a good tutorial on linked lists from the FAQ http://faq.cprogramming.com/cgi-bin/...&id=1073086407

[Albinoswordfish]

This is a pretty basic link list example, basically I think of a link list as an object that contains two things 1. A data entry 2.Pointer(s) to another object of the same type. This pointer(s) represents the next element in a list.

If you use an array for example the element A[1] would have a pointer to A[2](intuitively speaking)

the line:

typedef struct list_el item;

basically allows reference to the data type 'struct list_el' to be 'item', therefore you can just use item instead having to write struct list_el, it is not a necessary declaration for the program to work.

#include <stdio.h>

struct list_el {  //This is basically the declaration of the type of element to be used in thel linklist
   int val;  //some data value
   struct list_el * next; //pointer to next element in link list
};

typedef struct list_el item; //typedef declaration previously explained

void main() {
   item * curr, * head; //declaring two pointers of type struct
   int i;

   head = NULL; 

   for(i = 1; i <= 10; i++) {

      curr = (item *) malloc( sizeof(item) ); //intuitively your creating an element in the link list, I'm assuming you know what malloc does

      curr->val = i; //so you set this new element's value to whatever i is

      curr->next  = head; //the pointer to the next element would be set to the previous element created, for the first iteration it would be set to NULL
      head = curr;
   }

   curr = head;
   //right now your curr pointer is pointing to the last element created in your link list which is element that has 10 in this case
   while(curr) { //this while loop just traverses the link list starting at curr prints the value and goes to the next element until curr becomes NULL
      printf("%d\n", curr->val);
      curr = curr->next ;
   }
}

I'm not sure what your understanding on link lists are so I just wrote everything possible so there might be things you already know. I didn't understand link lists very well the first time I saw them so I know why some people get confused but really they're not that complicated

[devarishi]

So, you have done your job quite efficiently and effectively!

This is a pretty basic link list example, basically I think of a link list as an object that contains two things 1. A data entry 2.Pointer(s) to another object of the same type. This pointer(s) represents the next element in a list.

If you use an array for example the element A[1] would have a pointer to A[2](intuitively speaking)

the line:

typedef struct list_el item;

basically allows reference to the data type 'struct list_el' to be 'item', therefore you can just use item instead having to write struct list_el, it is not a necessary declaration for the program to work.

#include <stdio.h>

struct list_el {  //This is basically the declaration of the type of element to be used in thel linklist
   int val;  //some data value
   struct list_el * next; //pointer to next element in link list
};

typedef struct list_el item; //typedef declaration previously explained

void main() {
   item * curr, * head; //declaring two pointers of type struct
   int i;

   head = NULL; 

   for(i = 1; i <= 10; i++) {

      curr = (item *) malloc( sizeof(item) ); //intuitively your creating an element in the link list, I'm assuming you know what malloc does

      curr->val = i; //so you set this new element's value to whatever i is

      curr->next  = head; //the pointer to the next element would be set to the previous element created, for the first iteration it would be set to NULL
      head = curr;
   }

   curr = head;
   //right now your curr pointer is pointing to the last element created in your link list which is element that has 10 in this case
   while(curr) { //this while loop just traverses the link list starting at curr prints the value and goes to the next element until curr becomes NULL
      printf("%d\n", curr->val);
      curr = curr->next ;
   }
}

I'm not sure what your understanding on link lists are so I just wrote everything possible so there might be things you already know. I didn't understand link lists very well the first time I saw them so I know why some people get confused but really they're not that complicated