Linked List Tutorial and Implementation

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.