The linked list is a linear data structure that is stored in non-contiguous fashion (unlike array) in the memory. Linked List consists of nodes that contain data and reference/pointer to other nodes. In this linked list tutorial, we will cover the introduction to a linked list, creating a linked list, insertion, and deletion.
A linked list consisting of 3 nodes
A linked list is a dynamic data structure hence we can allocate as many nodes with data value as we want. We only have the pointer(generally called the head) to the first node and we can go to all other nodes using the head pointer only.
Linked list only supports sequential access and we generally use pointers to refer to the next node.
Creating a linked list
class Node{
public:
int data; // use to store an integer value
Node *next; //pointer to the addresss of next node memory address
}
Inserting into a node
If we want to insert a node into a linked list, we will first traverse the entire linked list till we reach the last node. Once we reached the last node, we will create a new node, assign it some value, mark its next address pointer as NULL & assign its address to the next address pointer of the previous node.
Ex: 1->2->7->6->8->NULL
Insert 3: 1->2->7->6->8->3->NULL
void insert(Node *head, int value){
Node *temp_head = head;
while(temp_head->next != NULL)
temp_head = temp_head->next; //visiting next node of linked list
Node *temp_node = new Node; // creating a new node and assign it memory
temp_node->data = value;
temp_node->next = NULL
temp_head->next = temp_node;
}
Time Complexity = O(n)
Deleting a node
When we want to delete a node, we will first search the entire linked list for the element and once the element is found, we assign the memory address of its next node to its previous node next memory address pointer.
Ex: 1->2->3->4->5->null
Delete 3: 1->2->4->5->null
string delete(Node *head, int value){
Node *temp_head = head;
Node *prev = head;
while(temp_head != Null){
if(temp_head==value){ // check if
prev->next = temp_head->next;
free(temp_head); //free the memory assigned to node to be deleted
return "deletion successful";
}
temp_head = temp_head->next;
}
return "element not found";
}
Time Complexity = O(n)
We hope you enjoyed this linked list tutorial. If you want to contributed or found some error, please comment.