List->Dynamic List->Concept

We have seen STATIC list, ARRAY, in which, we realised that space is the constraint. At the run-time, it was not possible to add more space to the existing allotted space to the LIST. Now, solution lies here with the advent of Dynamic Linked Lists.

What it does is -- starts with no fixed size and accumulates memory as and when needed (using garbage collection techniques); what you get in turn is no data overflow, no wastage of memory but a little more computation time. Let's understand...

Dynamic LIST:
Linked list, as the name suggests has to have some LINKS. So, where is that link? Every element in the list has a link going to the NEXT element in the list and obviously the last element has a NULL link in that case. Theoretically, it looks like this - 

Here, every box (i.e individual element) in the list is known as a NODE. A NODE in a Singly linked list has the following structure:

struct NODE
{
int nodevalue;
struct NODE *next;
}

So, every linked list has a POINTER to the list, which holds the list. In this case, it is "list". If you loose this pointer, you will loose the list. What I mean is - you have to have a pointer always pointing to the beginning of the list. Now the question is, how do you create a NODE?

In C, you have memory handling functions like malloc() and free(), which do the job of allocating and freeing of memory space for you; defined in alloc.h header file. So simple!

So, to get a fresh NODE, just call malloc() by providing it the size of your NODE and it allocates you that much of memory space. COOL no! Well, its hardly of our concern from where it collects that memory space.

With all that background, I think, we can create a Linked list...

Algorithm:-
Step-1: Get the value for your NEW node to be added to the list
Step-2: Create a NEW, empty node by calling malloc(). If malloc() returns no error then go to step-3 or else say "Memory shortage"
Step-3: Put the value inside the NEW node's nodevalue field. Make its NEXT pointer to point to NULL
Step-4: Add this NEW node at the end of your LIST
Step-5: Go to step-1 till you have more values to be added to the LIST

C implementation:-
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *list, *tail;

main()
{
list = (struct NODE *)malloc(sizeof(NODE));/*list initialized*/
tail = list; /*tail is a pointer to keep track of the list's tail*/
..
..
createlist(48); /* call createlist() as and when you want to add a new node*/
..
createlist(34);
..
..
}

createlist(int value) /*our algorithm starts here*/
{
struct NODE *new;
if(tail==list && tail->nodevalue ==NULL) 
                                        /*check whether the list is empty*/
  {
  tail->nodevalue = value;
  tail->next = NULL;
  }
else /*the case when the list has atleast one non-empty node*/
{
   if(new=(struct NODE*)malloc(sizeof(NODE)))
  {
   new->nodevalue = value;
   new->next = NULL; /*depicts the [1] part in the figure*/
   tail->next = new;
   tail = new; /*depicts the [2] part in the figure*/
  }
 else
  printf("Memory shortage");
}
}

Note:- Remember that the "nodevalue" we have taken here can be anything - an integer or a character or an array, .....or any damn process. Well, programming languages like JAVA does all these memory operations on its own to make the programming simpler!

Related Operations:
Addition and Deletion of a node
Traversing of list
Searching for a particular Key
Sorting of list