Real life use of doubly linked list

Question

When does using a doubly linked list seem to be best option in real life scenario? Can someone suggest practical use of it?

Kwakiutl

Answer 1

Adding to templatetypedef's answer.

You consider following applications :

- A music player which has next and prev buttons.
- Represent a deck of cards in a game.
- The browser cache which allows you to hit the BACK-FORWARD pages.
- Applications that have a Most Recently Used list (a linked list of file names)
- Undo-Redo functionality

Any application where you want to traverse both side from specific point.

Golf

Answer 2

In many operating systems, the thread scheduler (the thing that chooses what processes need to run at which times) maintains a doubly-linked list of all the processes running at any time. This makes it easy to move a process from one queue (say, the list of active processes that need a turn to run) into another queue (say, the list of processes that are blocked and waiting for something to release them). The use of a doubly-linked list here allows each of these splices and rewires to run in time O(1) and without any memory allocations, and the doubly-linked-list structure works well for implementing the scheduler using queues (where you only need to pull things out from the front.)

Encore

Answer 3

Doubly linked list is used in constructing MRU/LRU (Most/Least Recently Used) cache. You can find the implementation using HashMap and DoublyLinkedList in the link https://www.geeksforgeeks.org/design-a-data-structure-for-lru-cache/

One of the main applications of LRU cache is that it is employed in cases which uses most/least recently accessed items, like in the case of android phone home screen to save the most recently used apps. Here is a link explaining the application

http://www.primarydigit.com/blog/an-application-of-lru-least-recently-used-data-structure-your-phones-home-screen

Hope this helps!

Hasty

Answer 4

You can think it algorithmically. Like, suppose you want to store some data in which you have to insert some element in between. The best data structure for it would be a linked list as it does the task in O(1). Next, is suppose you want to access some element from the data. An array would be the best for this as it takes O(1) for accessing an element. But it makes insertion in O(n).

Now, in the linked list we can maintain a map of all the nodes and hence this will make the accessing thing in O(1). The insertion thing was already in O(1). Now what's remaining is the deletion part. In an array, the deletion is done in O(n) and in the linked list also deletion is done in O(n)(if you have only the element to be deleted).

However, in the linked list if we had the address of the previous node then we could have just deleted the desired node in O(1). Here, comes the use of the doubly linked list.

The above data structure does the three most important things in a system i.e. insertion, deletion and accessing an element in O(1).

Coquetry