The term “list” refers to a linear collection of data items. One way to store such data is by means at “array” . The array implementation of list hap certain draw backs there are
- Memory storage space is wasted, very often the list is much stories than the array size declared.
- List cannot grow in its size beyond the size at the declared array i.e required during paragraph execution.
- Operations like insertion and declaration as a specified location in a list requires a lot of movement of data, Therefore leading to inefficient and time containing algorithm
- Another way of storing a list in memory is by means of linked list. Each element in the list contain a field, called a link fields, Which contains the address of the next elements in the list need not occupy adjacent space in memory. Thus will make it easier to insert and delete element in the list.
Advantages of linked list over arrays:
- Linked list is a dynamic structure where as array is a static structure. That is the size of the array is fixed, it cannot be increased or decreased during execution of a program.
- In portion and deletion of nodes require no data movement
- Joining two arrays is very tedious process because these is lot of data movement, where of joining two linked list is very easy.
Types of linked list :
These are 3 types.
- Singly linked list
- Doubly linked list
- Circular linked list
Singly linked list:
- A singly linked list or one way list is a linear collection of data elements, called nodes
- Here each node is dividing into two fields.
- The first filed containing the information of the element, and the second field contains the address in the next node in the list.
- The first filed is called “Data field ” and the second field is called “Link field”
- The left part represents information part of the node the right part represents the link field of the node.
- The pointer to the last node contains a special value called “NULL” pointer.
- Linked list also contains a pointer variable, called HEAD, which points to the first node of the list
Inserting at an element in list:
- Inserting at the beginning of the list :
- Suppose a node N is to be inserted into the list at beginning as Shan in the fig. The simplest strategy for an item at the beginning at the list ip to:
- Allocate space for a new node.
- Copy the item to be inserted into it.
- Make the new nodes next pointer point to the current head of the list
- Make the HEAD of the list point to the newly allocated node.
- cur -> Link = Head
- Hand = Cur;
Insertion After a give node :
To insert a node in the linked list we need to specify the element to be inserted and the element in the list after which the element has to be inserted.
- Search for the element after which the insertion is to be done.
- Create a memory space for element to be inserted.
- Assign the data value its data field.
- Assign is a pointer to pointer of the element searched at step 2
- Assign pointer of the element searched at step 2to this new element started.
- cur - > Link = ptr -> Link;
- ptr - > Link =cur;
Deletion Operation :
Deleting Beginning Node:
- Store the first “link field” in the “HEAD” pointer
- Disappear the memory space held by the deleted element
Head=Head - > Link
Deleting a specified node:
- Search for the element with key value same as the element to be deleted.
- Its pointer to next element be saved and late assigned to next element of predecessor of the element searched at step.
- Dispose the memory space held by the deleted element.
ptr à link= ptr1 àlink;
Linked List Program
Implementation of singly linked list
# include <studio.h>
struct Node *link;
printf(“Enter Data for the Node -1): “);
cur=(struct Node*)malloc (size of (structNode));
ptr link =cur;
printf(“Enter Data For The Node -1):”);
cur=(structNode *) malloc (size of (structNode));
printf(“Enter Data for the New Node:”);
printf(“Do you want to insert first(y\n:”);
if((ch==’y’) || (ch==’n’))
cur link =Head;
printf(“After which element you want to Insert:”);
if(ptr Data ==ele)
cur Link =ptr à Link;
ptr Link= cur;
ptr =ptr Link;
void Deletion ()
printf(“Do you want to Delete First (Y/n):”);
printf(“ which element you want to delete:”);
if(ptr Link àData==ele)
printf(“List is Empty \n”);
printf(“Enter your choice:”);
case1: insertion ();
case2: deletion ();