A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.

The elements in a linked list are linked using pointers as shown in the below image:

Linkedlist Data Structure

Credit to GeeksforGeeks

Types of linked list

Singly Linked List

The linked list we talked above is singly linked list.

Doubly linked list

A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.


Credit to GeeksforGeeks

Circular linked list

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

Circular Linked List

Credit to GeeksforGeeks

Linked list applications

Delete a node


Credit to programmercarl

If we need to delete node d, what we need to do is to delete the pointer that points to node d

Add a node


Credit to programmercarl

Add and delete both have time complexity O(1).

Note: If we need to delete the last node, we need to start from head node to the fourth node, time complexity is O(n).

Compare with list

Add/Delete(Time Complexity) Search(Time Complexity) When to use
List O(n) O(1) Fixed number of data, frequently search, rarely add/delete
Linked List O(1) O(n) Number of data various, frequently add/delete, rarely search