A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.
Types of Linked List
Singly Linked List
A singly linked list is a linear data structure in which the elements are not stored in contiguous memory locations and each element is connected only to its next element using a pointer.
Related Post
Doubly Linked List
Inserting a new node in a doubly linked list is very similar to inserting new node in linked list. There is a little extra work required to maintain the link of the previous node. A node can be inserted in a Doubly Linked List in four ways:
- At the front of the DLL.
- In between two nodes
- After a given node.
- Before a given node.
- At the end of the DLL.
Circular Linked List
The circular linked list is a linked list where all nodes are connected to form a circle. In a circular linked list, the first node and the last node are connected to each other which forms a circle. There is no NULL at the end.
Circular Doubly Linked List
A circular doubly linked list is defined as a circular linked list in which each node has two links connecting it to the previous node and the next node.
Header Linked List
A header node is a special node that is found at the beginning of the list. A list that contains this type of node, is called the header-linked list. This type of list is useful when information other than that found in each node is needed.
Basic Operations
Traverse
We keep moving the temp node to the next one and display its contents.
When temp is NULL, we know that we have reached the end of the linked list so we get out of the while loop.
Ex:
1 2 3 4 5 6 | struct node *temp = head; printf("\n\nList elements are - \n"); while(temp != NULL) { printf("%d --->",temp->data); temp = temp->next; } |
Output:
1 2 | List elements are - 1 --->2 --->3 ---> |
Insert Elements
| Position | Step |
|---|---|
| Insert at the Beggining |
|
| Insert at the End |
|
| Insert at the Middle |
|
Ex:
1 2 3 4 5 6 7 | //Insert at the Beggining struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = head; head = newNode; |
1 2 3 4 5 6 7 8 9 10 | //Insert at the End struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = NULL; struct node *temp = head; while(temp->next != NULL) temp = temp->next; temp->next = newNode; |
1 2 3 4 5 6 7 8 9 10 11 12 13 | //Insert at the Middle struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; struct node *temp = head; for(int i=2; i < position; i++) { if(temp->next != NULL) { temp = temp->next; } } newNode->next = temp->next; temp->next = newNode; |
Delete
| Position | Step |
|---|---|
| Delete from beginning |
|
| Delete from end |
|
| Delete from middle |
|
Ex:
1 2 | //Delete from beginning head = head->next; |
1 2 3 4 5 6 | //Delete from end struct node* temp = head; while(temp->next->next!=NULL){ temp = temp->next; } temp->next = NULL; |
1 2 3 4 5 6 7 8 | //Delete from middle for(int i=2; i< position; i++) { if(temp->next!=NULL) { temp = temp->next; } } temp->next = temp->next->next; |
Search an Element
We are finding item on a linked list.
- Make
headas thecurrentnode. - Run a loop until the
currentnode isNULLbecause the last element points toNULL. - In each iteration, check if the key of the node is equal to
item. If it the key matches the item, returntrueotherwise returnfalse.
Ex:
1 2 3 4 5 6 7 8 9 10 | // Search a node bool searchNode(struct Node** head_ref, int key) { struct Node* current = *head_ref; while (current != NULL) { if (current->data == key) return true; current = current->next; } return false; } |
