A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations meaning they are not stored in locations like an array. The elements in a linked list are connected via pointers. In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. In a doubly linked list, there is also a reference to the previous pointer of the list.
Formally a link list is like:-
In a linear list implementation, there are always head and tail nodes, and inserting to them is a
O(1) operation.
In Linked List implementation, it has the following characteristics:
1)Insertion - O(1)
2)Deletion - O(n)
3)Searching - O(n)
Therefore Insertion operation with O(1) stands out. Link List is being trivial data structure but has two key points:-
1) Insertion operation is O(1)
2) The list is dynamically resized.
In a singly link list there is a node and pointer to the next node.
Link List Structure:
struct node
{
int info;
struct node *next;
};
Types of Linked Lists:
- Simple Linked List – In this type of linked list, one can move or traverse the linked list in only one direction
- Doubly Linked List – In this type of linked list, one can move or traverse the linked list in both directions (Forward and Backward)
- Circular Linked List – In this type of linked list, the last node of the linked list contains the link of the first/head node of the linked list in its next pointer and the first/head node contains the link of the last node of the linked list in its prev pointer
Linked List Applications
- Dynamic memory allocation
- Implemented in stack and queue
- In undo functionality of softwares
- Hash tables, Graphs
Linked List Complexity
Time Complexity
| Worst case | Average Case | |
|---|---|---|
| Search | O(n) | O(n) |
| Insert | O(1) | O(1) |
| Deletion | O(1) | O(1) |
Space Complexity: O(n)
MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview
2 year PGDM (E-Business) from Welingkar, Mumbai
4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology
Google and Hubspot Certification
Brain Bench Certification in C++, VC++, Data Structure and Project Management
10 years of Experience in Software Development out of that 6 years 8 months in Wipro
Selected in Six World Class UK Universities:-
King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds
