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. 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.

``````
class Node{
public:
int data;      // use to store an integer value
}
``````

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

``````

Node *temp_node = new Node;      // creating a new node and assign it memory
temp_node->data = value;
temp_node->next = NULL
}
``````

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){

free(temp_head);          //free the memory assigned to node to be deleted
return "deletion successful";
}
}