A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations (like an array). The elements are linked using pointers. Linked lists are among the simplest and most common data structures.
In basic terms, each element points to the next. A linked list consists of nodes where each node contains data pertaining to that node and a reference (address) of the next node.
Note: This article pertains information about singly linked list.
- Singly linked list
- Circular linked list
- Doubly linked list
- Linked list is a Dynamic Data Structure. Meaning it's size can grow and shrink during runtime.
- Insertion and Deletion operations are easier as compared to arrays.
- They use more memory than arrays because they use pointers.
- Accessing an element has to be done sequentially, i.e, start from the first node.
- Nodes are stored incontigously which increases time required to access individual elements.
- Implementation of stacks and queues can be done using linked list.
- Music Player: Songs are linked to previous and next song.
- Implementation of graphs.
- Implementation of hash maps.
- Performing arithmetic operations on long integers.
The links provided below are for singly linked lists.