Application of Doubly Linked Lists
- Redo and undo functionality.
- Use of the Back and forward button in a browser.
- The most recently used section is represented by the Doubly Linked list.
- Other Data structures like Stack, Hash Table, and Binary Tree can also be applied by Doubly Linked List.
- Used to implement game objects and their interactions in a game engine.
- Used in networking.
- Used in Graph algorithms.
- Operating systems use doubly linked lists to manage the process scheduling. Each process waiting to be executed is represented as a node in the doubly linked list, and the operating system can easily traverse the list in both directions to manage the process queue.
Example:
Design a data structure that supports following operations efficiently.
- getMin : Gets minimum
- extractMin : Removes minimum
- getMax : Gets maximum
- extractMax : Removes maximum
- insert : Inserts an item. It may be assumed that the inserted item is always greater than maximum so far. For example, a valid insertion order is 10, 12, 13, 20, 50.
Explanation: Doubly linked list is the best solution here. We maintain head and tail pointers, since inserted item is always greatest, we insert at tail. Deleting an item from head or tail can be done in O(1) time. So all operations take O(1) time.
Applications of linked list data structure
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: