What is a Linked List?

A linked list is a linear data structure that consists of a sequence of connected nodes, where each node contains a value and the address of the next node.

• Pointers are used to connect the consecutive nodes.
• The first node is referred to as the head.
• The size of a linked list is not fixed.
• The last node points to null.

Why is it needed?

• Unlike arrays, linked lists do not require contiguous memory allocation. Linked lists can allocate memory blocks from anywhere in the memory which helps in more efficient utilization of memory.
• In linked list, insertion and deletion of elements is relatively easier as these operations could be performed through traversing the linked list using the pointer from head node and no shifting is required.
• Linked lists can grow or shrink dynamically during runtime because they don’t have fixed size like arrays.

Hence, linked lists are a beneficial linear data structure in situations where dynamic sizing, efficient insertion and deletion and flexible memory allocation are important factors.

Common uses of linked list

Linked lists can be used in a variety of applications. Here are some common uses of linked lists:

1. Implementing stacks and queues: Linked lists are commonly used to implement stacks and queues, as they provide efficient insertion and deletion operations at the head or tail of the list, respectively.

2. Implementing hash tables: Linked lists are used to handle collisions in hash tables. Each bucket in the hash table can contain a linked list of elements that map to the same index in the table.

3. Memory allocation: Operating systems and programming languages often use linked lists to manage memory allocation, such as tracking free memory blocks and maintaining lists of allocated memory.

4. Graph and trees algorithms: Linked lists can be used to represent graphs as well as trees and perform graph algorithms, such as breadth-first search and depth-first search.

5. Mathematical operations: Linked lists are also used for manipulation of polynomials, performing arithmetic operations on long integers and representing sparse matrices.