Linked List

Linked List

A linked list is a set of node where each node has two field data field and address field, where data field contains the information and the address field stores the address of next node.

         Linked list is a linear data structure. It uses non-contigous memory allocation scheme .

Further we say linked list is a collection of node which uses non-contigous memory. The address field of any node in linked list which consist of "NULL" indicates end of linked list.

         Linked list uses dynamic memory allocation which allows your program to obtain more memory space while running, or to release it if it is not required. For dynamic memory allocation we use these functions in C :-

1- Malloc()

The name stands for memory allocation. This function reserves a block of memory of specified size and returns a pointer of type (void) which can be casted into pointer of any type.

Syntax- ptr = (cast_type*)malloc(Byte_size);

2- Calloc()

The name stands for contiguous allocation. This function reserves a block of memory of specified size and initialises it with zero and then returns a pointer of type (void) which can be casted into pointer of any type.

Syntax- ptr = (cast_type*)calloc(n,element_size);

Advantages over arrays

1) Dynamic size

2) Ease of insertion/deletion

Drawbacks:

1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.

Types of Linked List

1- Simple Linked List : Item navigation is forward only.

2- Doubly Linked List : Item can be navigated forward and backward way.

3- Circular Linked List : Last item contains link of the first element as next and and first element has link to last element as prev.

Representation in C

A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL.
Each node in a list consists of at least two parts:
1) data
2) pointer to the next node

// A linked list node

struct Node

{

  int data;

  struct Node *next;

};

                                         C Programs

Creation of Linked List :-

struct node

{

int n;

struct node *address;

};

struct node *start,*temp,*ptr;

int i,len;

printf("Enter the no. of elements ");

scanf("%d",&len);

for(i=1;i<=len;i++)

{

      temp=(struct node*)malloc(sizeof(node));

      printf("Enter the element");

      scanf("%d",&temp->n);

      if(i==1)

          start==temp;

      else

          ptr->address=temp;

      ptr=temp;

}

Traversal Of Linked List:-

void traversal(struct node *start)

{

       struct node *temp;

       temp=start;

       if(temp==NULL)

             printf("List is empty");

       else

             while(temp!=NULL)

            {

                   printf("%d     ",temp->data);

                   temp=temp->next;

            }

}