Linked Lists Using Dynamic Variables

Suppose we have a linked list that consists of a set of nodes, each of which has two fields: a data field and a pointer to the next node in the list. In addition, an external pointer points to the first node in the list. We use pointer variables to implement list pointers. Thus, we define the type of a pointer and a node by

struct node {

int data;

struct node *link;

};

typedef struct node *NODEPTR;

A node of this type is identical to the nodes of the array implementation except that the link field is a pointer (containing the address of the next node in the list) rather than an integer (containing the index within an array where the next node in the list is kept).

Let us employ the dynamic allocation features to implement linked lists. Instead of declaring an array to represent an aggregate collection of nodes, nodes are allocated and freed as necessary. The need for a declared collection of nodes is eliminated in dynamic allocation. The structures for head node and data node in C are given below.

Struct node /*declare structure type */

{

int data ;

struct node *link ; /*declare a pointer to structure of node type*/

/* node is a self-referential structure */

};

Struct list /*declare structure type */

{

int count ;

struct node *head ;

} list1; /*declare a structure variable */

In above statements, pointer variable head will contain the address of first element of the list, list1. And pointer variable link will contain address of next node in the list, list1.