Home Data Structures Linked List Tutorial and Implementation

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.
Linked list only supports sequential access and we generally use pointers to refer to the next node.

Singly-linked-list.svg

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.

Creating a linked list node


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 linked list:

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 from a linked list:

When we want to delete a node, we will first search 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)

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here