Linked list is a linear data structure that consists of a sequence of nodes, where each node contains a value and a reference (or pointer) to the next node in the sequence. The last node in the sequence has a reference to null, indicating the end of the list.
The main advantage of a linked list over an array is that it allows for efficient insertion and deletion of elements, as these operations do not require shifting of elements like in an array. However, accessing an element at a particular index in a linked list takes O(n) time, while in an array it takes O(1) time.
There are two major types of linked lists:
- Singly Linked List: In a singly linked list, each node has only one reference to the next node in the sequence.
- Doubly Linked List: In a doubly linked list, each node has two references, one to the next node and one to the previous node in the sequence.
Real-time examples of a linked list include:
- A playlist of songs in a music streaming app.
- A list of messages in a chat app.
- A list of webpages in a browser's history.
PRACTICE PROBLEMS :