An array is a linear collection of data elements and a linked list is a linear collection of nodes.
But unlike an array, a linked list does not share its nodes in consecutive memory locations.
Another point of difference between an array and a linked list is that a linked list does not allow random access of data.
Nodes in a linked list can be accessed only in a sequential manner.
Nodes in a linked array, insertions and deletions can be done at any point in the list in a constant time.
Another advantage of a linked list over array is that, we can add any number of elements in the list, this is not possible in case of an array.
For example, if we declare an array as int a , then the array can store maximum of 10 data elements, but not even one more than that, there is no such restriction in case of linked list.
Linked list provide an efficient way of storing related data and perform basic operations such as insertion, deletion and updating of information at the cost of extra space required for storing the address.
Applications of linked list:
1. Polynomial representation:
Let us see how a polynomial represented in the memory using linked list, A polynomial is given as $6x^3 + 9x^2 + 7_x +1$ , individual turn in a polynomial consists of 2 points, a coefficient and a power, here 6,9,7 and 1 are the co-coefficients of the terms that have 3,2,1 and 0 as their powers respectively.
Every term of a polynomial can be represented as a note of the linked list, fig shows the linked representation of the terms of above polynomial.
Linked lists can be used to implement stack as label as queues.
Linked list can also be used to implement graphs (Adjacency list representation of graph)
Implementing hash tables:
- Each bucket of the hash table can itself be a linked list. (open chain hashing)
For any polynomial operation, such as addition or multiplication of polynomials, linked list representation is more easier to deal with.
Linked lists are useful for dynamic memory allocation.
The real life application where the circular linked list id used, in our personal computers, where multiple applications are running, linked list is used.
All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. the operating system keeps on iterating over the linked list until all the applications are completed.