Introduction
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
A Linked List is a linear data structure. Unlike arrays, the elements are not stored at contiguous locations. The linked list nodes are linked using pointers. Each node consists of 2 parts:
- Data: The Data which is stored at a particular address.
- Reference: Contains the address of the next node of the linked list.
Applications of Linked List in the field of Computer Science:
1] Dynamic Memory Allocation: As we know, we can dynamically allocate memory in a linked list, so it can be very helpful when we dont know the number of elements we are going to use.
2] Implementing advanced data structures: We can implement data structures like stacks and queues with the help of a linked list.
3] Manipulating polynomials: We can do polynomials manipulation with the help of a linked list by storing the constants in the nodes of the linked list.
4] Arithmetic operations on long integers: As integers have a limit, we cannot perform arithmetic operations on long integers. But, if we use a linked list to represent the long integers, we can easily perform the operations.
5] Graph Adjacency list Representation: Linked List helps in storing the adjacent vertices of a graph in adjacency list representation.
Applications of Linked List in real world
1] In web browsers, you might have seen that we can always access the previous and next URL using the back and forward button. Access to previous and next URL searched is possible because they are linked using a linked list.
2] The songs in the Music Player are linked to the next and the previous song. We can play songs either from the starting or the end of the list.
3] In an Image Viewer, the next and the previous images are linked; hence they can be accessed by the previous and the next button.
Circular linked lists also have good usage. A circular linked list is a linked list in which the last node points to the head instead of pointing to NULL.
Applications of Circular Linked Lists
1] We can use Circular Linked List to implement advanced data structures like Fibonacci Heap.
2] Circular lists are helpful in applications when you want to go around the list several times.
- When many programs are running on a PC, it is typical for the operating system to place them all on a list and then cycle over them, giving each one a chunk of time to execute before having them wait while the CPU is given to another.
- It is more convenient for the operating system to utilize a circular list so that it may cycle back to the beginning when it reaches the end of the list.
3] Circular Linked List can be used to implement a queue. We do not need to maintain the head and rear pointer if we use a circular linked list. We can store a pointer to the last node of the list, and the head can always be obtained as the next of the list.
Lets also see some advantages of linked list over arrays:
Advantages of Linked List
1] Dynamic Data Structure: Linked List being a dynamic data structure, can shrink and grow at the runtime by deallocating or allocating memory, so there is no need for an initial size in the linked list. Whereas in an array, an initial size has to be declared, and the number of elements cannot exceed that size.
2] No Memory Wastage: As the size of a linked list can grow or shrink at runtime, so there is no memory wastage. Only the required memory is allocated. In arrays, we have to first initialize it with a size which we may or may not fully use; hence wastage of memory may occur.
3] Implementation: Some very helpful data structures like queues and stacks can easily be implemented using a Linked List.
4] Insertion and Deletion Operation: In a Linked List, insertion and deletion operations are quite easy, as there is no need to shift every element after insertion or deletion.
- Only the address present in the pointers needs to be updated.
- While, in an array, we have to shift elements. Suppose an array is sorted, and we have to insert an element in it in a sorted way. Let arr[]= [ 1, 3 , 5, 7, .. ] and we have to insert 2. So, all the elements after 1 have to move by one place towards the right.
So, in this article, we have learned about the applications of linked lists. Linked List is a very important topic when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.