Linked list is the linear collection of data structure, where the data is not stored sequentially inside the computer memory but linked with each other by the the help of address. Each element is called a node, contains references to the next node. this way flexibility is provided to a structure.
types of linked list
singly linked list
doubly linked list
circular linked list
Singly linked list
SINGLY linked list is the linear collection of data item called nodes, where each node has been divided into two parts
DATA
NEXT
The data part of the node collects the actual data, and the link part contains the address to the next node which has to be traversed.
Here, the head address is 4800 which determines where the data is being started. On the first node the data is 10 and the address to the next node is given 4900. This process is repeated till the data ends and the address is null on the last node.
Algorithm
1.INSERT ITEM IN THE BEGINING OF SINGLY LINKED LIST
Create a new node with the given value.
Point the next of this new node to the current head of the list.
Update the head to this new node.
2.INSERT ITEM AT THE ENDING OF SINGLY LINKED LIST
Create a new node with the given value.
Traverse the list to find the last node.
Point the next of the last node to the new node.
3.INSERT ITEM AT ANY POSITION OF SINGLY LINKED LIST
Create a new node with the given value.
If the position is 0, update the new node’s next to the current head and update the head to the new node.
Otherwise, traverse the list to find the node just before the desired position.
Update the new node’s next to the next of the node found in step 3.
Update the next of the node found in step 3 to the new node.
4.DELETE FROM THE BEGINING
Check if the list is empty (i.e., the head is NULL).
If it is, there’s nothing to delete.
If the list is not empty, update the head to the next node.
Free the memory allocated for the original head node.
5.DELETE FROM THE END
Check if the list is empty (i.e., the head is NULL).
If it is, there’s nothing to delete.
If the list is not empty, update the head to the next node.
free the memory allocated for the original head node.
6.DELETE FROM ANY POSITION
Check if the list is empty (i.e., the head is NULL).
If it is, there’s nothing to delete.
If the position is 0, delete the node at the beginning.
Otherwise, traverse the list to find the node just before the desired position.
Update the next pointer of the node found in step 3 to the next node of the node to be deleted.
Free the memory allocated for the node to be deleted.
Doubly linked list
Doubly linked list is a linear collection of data items called nodes, where each node has been divided into 3 parts
Previous
Data
Next
Previous section of the node contains address to the previous data node. Data section contains the actual data and next part contains address to the next node.
Following is the example: –
Here, the head address is 100 and the previous section is null. This means this is the starting point of doubly linked list. The next section of the 100 node is 200 which means 200 is the next node.
Algorithm
1.INSERT AN ITEM IN THE BEGINING OF DOUBLY LINKED LIST
Create a new node.
Assign the new node’s data to the given value.
Set the new node’s next to the current head.Set the new node’s prev to NULL.
If the list is not empty, set the current head’s prev to the new node.
Update the head to point to the new node.
2.INSERT AN ITEM IN THE END OF DOUBLY LINKED LIST
Create a new node.
Assign the new node’s data to the given value.
Set the new node’s next to NULL.
If the list is empty, set the head to the new node.
Traverse to the end of the list.Set the last node’s next to the new node.
Set the new node’s prev to the last node.
3.INSERT AN ITEM AT ANY POSITION OF DOUBLY LINKED LIST
Validate the position.
Create a new node.
Assign the new node’s data to the given value.
If inserting at the beginning, update head and return.
Traverse to the node before the desired position.
Set the new node’s next to the current node’s next.
Set the new node’s prev to the current node.
If not inserting at the end, set the next node’s prev to the new node.
Update the current node’s next to the new node.
4.DELETE FROM THE BEGINING
Check if the list is empty.
Store the head in a temporary variable.
Update the head to the next node.
If the list is not empty after the update, set the new head’s prev to NULL.
Free the temporary node.
5.DELETE FROM THE END
Check if the list is empty.
Traverse to the last node.
Update the previous node’s next to NULL.
Free the last node.
6.DELETE FROM ANY POSITION
Validate the position.
Check if the list is empty.
If deleting the first node, update head and return.
Traverse to the node at the given position.
Update the previous node’s next to the current node’s next.
If not deleting the last node, update the next node’s prev to the current node’s prev.
Free the current node.
Circular linked list
It is the variation of singly and doubly linked list where first node point to the last node and last node point to the first. It is used when we want traversing of data numbers of times without relying initializing the start pointer, as well as we can visit all the nodes from any node.
TYPES
CIRCULAR SINGLY LINKED LIST
CIRCULAR DOUBLY LINKED LIST
Circular singly linked list
If a last node of singly linked list hold the address of start node, then its called circular singly linked list.
Following is an example:-
Here, end of the list can’t be seen as there is no null value in address of the node.
Algorithm
1.INSERT AN ITEM IN THE BEGINING
Create a new node.
Assign the new node’s data to the given value.
If the list is empty, set the new node’s next to point to itself.
If the list is not empty, find the last node and set its next to the new node, and update the new node’s next to point to the head.
Update the head to point to the new node.
2.INSERT ITEM AT THE ENDING
Create a new node.
Assign the new node’s data to the given value.
If the list is empty, set the new node’s next to point to itself and update the head.
If the list is not empty, traverse to the last node and update its next to point to the new node, and set the new node’s next to point to the head.
3.INSERT AN ITEM AT ANY POSITION
Validate the position.
Create a new node.
Assign the new node’s data to the given value.
If inserting at the beginning, update the head and return.
Traverse to the node before the desired position.
Update the new node’s next to the current node’s next.
Update the current node’s next to the new node.
4.DELETE FROM THE BEGINING
Check if the list is empty.
If there’s only one node, free it and set the head to NULL.
If the list has more than one node, find the last node.
Set the last node’s next to the second node.Free the head node.
Update the head to point to the second node.
5.DELETE FROM THE END
Check if the list is empty.
If there’s only one node, free it and set the head to NULL.
If the list has more than one node, traverse to the second last node.
Update the second last node’s next to point to the head.
Free the last node.
6.DELETE FROM ANY POSITION
Validate the position.
Check if the list is empty.
If deleting the first node, handle separately.
Traverse to the node just before the position to be deleted.
If the node to be deleted is not within bounds, return an error.
Update the previous node’s next to skip the node to be deleted.
Free the node at the given position.
Circular doubly linked list
If last node of doubly linked list hold the address of first node, and first node hold the Adrian of last node called circular doubly linked list.
Following is an example:-
Here, no null value can be seen in either previous or next part of the node and hence it doesn’t end.
Algorithm
1.INSERT AN ITEM IN THE BEGINING
Create a new node.
Assign the new node’s data to the given value.
If the list is empty, set the new node’s next and prev to point to itself.
If the list is not empty, find the last node and set its next to the new node, and the new node’s next to point to the head.
Update the head’s prev to the new node.
Set the new node’s prev to the last node.
Update the head to point to the new node.
2.INSERT ITEM AT THE ENDING
Create a new node.
Assign the new node’s data to the given value.
If the list is empty, set the new node’s next to point to itself and update the head.
If the list is not empty, traverse to the last node and update its next to point to the new node, and set the new node’s next to point to the head.
3.INSERT AN ITEM AT ANY POSITION
Validate the position.
Create a new node.
Assign the new node’s data to the given value.
If inserting at the beginning, update the head and return.
Traverse to the node before the desired position.
Update the new node’s next to the current node’s next.
Update the current node’s next to the new node.
4.DELETE FROM THE BEGINNING
Check if the list is empty.
If there’s only one node, free it and set the head to NULL.
If the list has more than one node, find the last node.
Set the last node’s next to the second node.
Update the second node’s prev to the last node.
Free the head node.
Update the head to point to the second node.
5.DELETE FROM THE END
Check if the list is empty.
If there’s only one node, free it and set the head to NULL.
If the list has more than one node, traverse to the second last node.
Set the second last node’s next to the head.
Update the head’s prev to the second last node.
Free the last node.
6.DELETE FROM ANY POSITION
Validate the position.
Check if the list is empty.
If deleting the first node, handle separately.
Traverse to the node at the given position.
Update the previous node’s next to the current node’s next.
Update the next node’s prev to the current node’s prev.
Free the current node.
DIFFERENCE BETWEEN ARRAY AND LINKED LIST
ARRAY
LINKED LIST
Array is a collection of homogeneous (similar) datatype.
Linked list is a collection of nodes
Array elements are stored in continuous memory locations
Linked list elements can be stored anywhere in the memory.
Linked list is the linear collection of data structure, where the data is not stored sequentially inside the computer memory but linked with each other by the the help of address. Each element is called a node, contains references to the next node. this way flexibility is provided to a structure.
types of linked list
singly linked list
doubly linked list
circular linked list
Singly linked list
SINGLY linked list is the linear collection of data item called nodes, where each node has been divided into two parts
DATA
NEXT
The data part of the node collects the actual data, and the link part contains the address to the next node which has to be traversed.
Here, the head address is 4800 which determines where the data is being started. On the first node the data is 10 and the address to the next node is given 4900. This process is repeated till the data ends and the address is null on the last node.
Algorithm
1.INSERT ITEM IN THE BEGINING OF SINGLY LINKED LIST
Create a new node with the given value.
Point the next of this new node to the current head of the list.
Update the head to this new node.
2.INSERT ITEM AT THE ENDING OF SINGLY LINKED LIST
Create a new node with the given value.
Traverse the list to find the last node.
Point the next of the last node to the new node.
3.INSERT ITEM AT ANY POSITION OF SINGLY LINKED LIST
Create a new node with the given value.
If the position is 0, update the new node’s next to the current head and update the head to the new node.
Otherwise, traverse the list to find the node just before the desired position.
Update the new node’s next to the next of the node found in step 3.
Update the next of the node found in step 3 to the new node.
4.DELETE FROM THE BEGINING
Check if the list is empty (i.e., the head is NULL).
If it is, there’s nothing to delete.
If the list is not empty, update the head to the next node.
Free the memory allocated for the original head node.
5.DELETE FROM THE END
Check if the list is empty (i.e., the head is NULL).
If it is, there’s nothing to delete.
If the list is not empty, update the head to the next node.
free the memory allocated for the original head node.
6.DELETE FROM ANY POSITION
Check if the list is empty (i.e., the head is NULL).
If it is, there’s nothing to delete.
If the position is 0, delete the node at the beginning.
Otherwise, traverse the list to find the node just before the desired position.
Update the next pointer of the node found in step 3 to the next node of the node to be deleted.
Free the memory allocated for the node to be deleted.
Doubly linked list
Doubly linked list is a linear collection of data items called nodes, where each node has been divided into 3 parts
Previous
Data
Next
Previous section of the node contains address to the previous data node. Data section contains the actual data and next part contains address to the next node.
Following is the example: –
Here, the head address is 100 and the previous section is null. This means this is the starting point of doubly linked list. The next section of the 100 node is 200 which means 200 is the next node.
Algorithm
1.INSERT AN ITEM IN THE BEGINING OF DOUBLY LINKED LIST
Create a new node.
Assign the new node’s data to the given value.
Set the new node’s next to the current head.Set the new node’s prev to NULL.
If the list is not empty, set the current head’s prev to the new node.
Update the head to point to the new node.
2.INSERT AN ITEM IN THE END OF DOUBLY LINKED LIST
Create a new node.
Assign the new node’s data to the given value.
Set the new node’s next to NULL.
If the list is empty, set the head to the new node.
Traverse to the end of the list.Set the last node’s next to the new node.
Set the new node’s prev to the last node.
3.INSERT AN ITEM AT ANY POSITION OF DOUBLY LINKED LIST
Validate the position.
Create a new node.
Assign the new node’s data to the given value.
If inserting at the beginning, update head and return.
Traverse to the node before the desired position.
Set the new node’s next to the current node’s next.
Set the new node’s prev to the current node.
If not inserting at the end, set the next node’s prev to the new node.
Update the current node’s next to the new node.
4.DELETE FROM THE BEGINING
Check if the list is empty.
Store the head in a temporary variable.
Update the head to the next node.
If the list is not empty after the update, set the new head’s prev to NULL.
Free the temporary node.
5.DELETE FROM THE END
Check if the list is empty.
Traverse to the last node.
Update the previous node’s next to NULL.
Free the last node.
6.DELETE FROM ANY POSITION
Validate the position.
Check if the list is empty.
If deleting the first node, update head and return.
Traverse to the node at the given position.
Update the previous node’s next to the current node’s next.
If not deleting the last node, update the next node’s prev to the current node’s prev.
Free the current node.
Circular linked list
It is the variation of singly and doubly linked list where first node point to the last node and last node point to the first. It is used when we want traversing of data numbers of times without relying initializing the start pointer, as well as we can visit all the nodes from any node.
TYPES
CIRCULAR SINGLY LINKED LIST
CIRCULAR DOUBLY LINKED LIST
Circular singly linked list
If a last node of singly linked list hold the address of start node, then its called circular singly linked list.
Following is an example:-
Here, end of the list can’t be seen as there is no null value in address of the node.
Algorithm
1.INSERT AN ITEM IN THE BEGINING
Create a new node.
Assign the new node’s data to the given value.
If the list is empty, set the new node’s next to point to itself.
If the list is not empty, find the last node and set its next to the new node, and update the new node’s next to point to the head.
Update the head to point to the new node.
2.INSERT ITEM AT THE ENDING
Create a new node.
Assign the new node’s data to the given value.
If the list is empty, set the new node’s next to point to itself and update the head.
If the list is not empty, traverse to the last node and update its next to point to the new node, and set the new node’s next to point to the head.
3.INSERT AN ITEM AT ANY POSITION
Validate the position.
Create a new node.
Assign the new node’s data to the given value.
If inserting at the beginning, update the head and return.
Traverse to the node before the desired position.
Update the new node’s next to the current node’s next.
Update the current node’s next to the new node.
4.DELETE FROM THE BEGINING
Check if the list is empty.
If there’s only one node, free it and set the head to NULL.
If the list has more than one node, find the last node.
Set the last node’s next to the second node.Free the head node.
Update the head to point to the second node.
5.DELETE FROM THE END
Check if the list is empty.
If there’s only one node, free it and set the head to NULL.
If the list has more than one node, traverse to the second last node.
Update the second last node’s next to point to the head.
Free the last node.
6.DELETE FROM ANY POSITION
Validate the position.
Check if the list is empty.
If deleting the first node, handle separately.
Traverse to the node just before the position to be deleted.
If the node to be deleted is not within bounds, return an error.
Update the previous node’s next to skip the node to be deleted.
Free the node at the given position.
Circular doubly linked list
If last node of doubly linked list hold the address of first node, and first node hold the Adrian of last node called circular doubly linked list.
Following is an example:-
Here, no null value can be seen in either previous or next part of the node and hence it doesn’t end.
Algorithm
1.INSERT AN ITEM IN THE BEGINING
Create a new node.
Assign the new node’s data to the given value.
If the list is empty, set the new node’s next and prev to point to itself.
If the list is not empty, find the last node and set its next to the new node, and the new node’s next to point to the head.
Update the head’s prev to the new node.
Set the new node’s prev to the last node.
Update the head to point to the new node.
2.INSERT ITEM AT THE ENDING
Create a new node.
Assign the new node’s data to the given value.
If the list is empty, set the new node’s next to point to itself and update the head.
If the list is not empty, traverse to the last node and update its next to point to the new node, and set the new node’s next to point to the head.
3.INSERT AN ITEM AT ANY POSITION
Validate the position.
Create a new node.
Assign the new node’s data to the given value.
If inserting at the beginning, update the head and return.
Traverse to the node before the desired position.
Update the new node’s next to the current node’s next.
Update the current node’s next to the new node.
4.DELETE FROM THE BEGINNING
Check if the list is empty.
If there’s only one node, free it and set the head to NULL.
If the list has more than one node, find the last node.
Set the last node’s next to the second node.
Update the second node’s prev to the last node.
Free the head node.
Update the head to point to the second node.
5.DELETE FROM THE END
Check if the list is empty.
If there’s only one node, free it and set the head to NULL.
If the list has more than one node, traverse to the second last node.
Set the second last node’s next to the head.
Update the head’s prev to the second last node.
Free the last node.
6.DELETE FROM ANY POSITION
Validate the position.
Check if the list is empty.
If deleting the first node, handle separately.
Traverse to the node at the given position.
Update the previous node’s next to the current node’s next.
Update the next node’s prev to the current node’s prev.
Free the current node.
DIFFERENCE BETWEEN ARRAY AND LINKED LIST
ARRAY
LINKED LIST
Array is a collection of homogeneous (similar) datatype.
Linked list is a collection of nodes
Array elements are stored in continuous memory locations
Linked list elements can be stored anywhere in the memory.
