Linked List is a linear data structure and it is very common data structure which consists of group of nodes in a sequence which is divided in two parts. Each node consists of its own data and the address of the next node and forms a chain. Linked Lists are used to create trees and graphs.
Following are the important points to be considered:
- Linked List contains an link element called first.
- Each Link carries a data field(s) and a Link Field called next.
- Each Link is linked with its next link using its next link.
- Last Link carries a Link as null to mark the end of the list.
Types of Linked List
-
Simple Linked List
-
Doubly Linked List
-
Circular Linked List
Basic Operations
-
Insertion − add an element at the beginning of the list.
-
Deletion − delete an element at the beginning of the list.
-
Display − displaying complete list.
-
Search − search an element using given key.
-
Delete − delete an element using given key.
Advantages of Linked Lists
- They are a dynamic in nature which allocates the memory when required.
- Insertion and deletion operations can be easily implemented.
- Stacks and queues can be easily executed.
- Linked List reduces the access time.
Disadvantages of Linked Lists
- The memory is wasted as pointers require extra memory for storage.
- No element can be accessed randomly; it has to access each node sequentially.
- Reverse Traversing is difficult in linked list.
Insertion Operation
Insertion is a three step process −
- Create a new Link with provided data.
- Point New Link to old First Link.
- Point First Link to this New Link.
code snippet for insertion is given below:
void insertFirst(int key, int data)
{
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
link->next = head; //point it to old first node
head = link; //point first to new first node
}
Deletion Operation
Deletion is a two step process −
- Get the Link pointed by First Link as Temp Link.
- Point First Link to Temp Link's Next Link.
The code snippet for deletion is given below:
struct node* deleteFirst()
{
struct node *tempLink = head;
head = head->next; //mark next to first link as first
return tempLink; //return the deleted link
}
Navigation Operation
Navigation is a recursive step process and is basis of many operations like search, delete etc. −
- Get the Link pointed by First Link as Current Link.
- Check if Current Link is not null and display it.
- Point Current Link to Next Link of Current Link and move to above step.
The code snippet for Navigation is given below:
void printList()
{
struct node *ptr = head;
printf("\n[ ");
while(ptr != NULL) //start from the beginning
{
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
Go through this video--
