Implementing Dynamic Linked Lists in C

List is a type of dynamic data structure which rectifies certain drawbacks of Stacks and Queues. Lists generally uses the concept of pointers which points to a memory location containing data. The basic structure of a linear linked list is a as follows –

Each item in a list is called NODE. Each NODE has two blocks of data.

• Its main data element or information and
• The address of the next NODE

The external list pointer points to the very first NODE in the list while the address field of the last NODE consists of a null pointer (NULL). For an empty list, LIST = NULL. If p is a pointer to a node, functions say node(p) returns the node pointed by p, info(p) returns the information content of that node and next(p) returns the address of the next node to p.

Concept of Insertion and Removal from a List

Suppose we want to include a new node to an already existing list with 3 nodes as shown below –

The first operation will be to form an empty node and assign its address to a pointer variable p.

i.e. p = getnode();

Now the next operation will be to store information the new node by the operation info(p) = A;

The next operation will be to assign the content of pointer variable list to the add field of the new node by,

next(p) = list;

and at last change list by p as,

list = p;

Now, the removal operation will be just opposite to the insertion operation. So to remove node containing info A, the following steps are done –

p = list;
list = next(p);
x = info(p);
freenode(); /* frees the allocated memory space for the removed node */

Array Representation of Linear Linked Lists

Linked Lists could be easily  represented using arrays as shown below –

define MAX 50
struct node{
              int info, next;              
};
struct node nodes[MAX];

Dynamic Representation of Linear Linked Lists

#include 
struct node{
              int info;
              struct node * next;
};
typedef struct node * NODEPTR;
main(){       
       scanf("%d", &x);
       insert(p,x);
       delete(p, &px);
}

void insert(NODEPTR p, int x){
       NODEPTR q;
       NODEPTR getnode();
       q = getnode();
       q->info = x;
       q->next = p->next;
       p->next = q;
       return;
}
 void delete(NODEPTR p, int * px){
       NODEPTR freenode(NODEPTR p);
       NODEPTR q;
       if(p == NULL || p->next == NULL){
           printf("\n Void Deletion");
           exit(0);
       }
       q = p->next;
       *px = q->info;
       p->next = q->next;
       freenode(q);
}

NODEPTR getnode(void){

NODEPTR p;

p = (NODEPTR) malloc (sizeof(structnode));

return(p);

}