Applications of Linked Lists

Linked list is list of nodes connected by pointers. Each node stores data and pointer to next node. Linkedlist is a dynamic data structure, so size can be easily increased.

Few frequently used terms in linked list are:

Node
Head
Tail
Sentinel

Python implementation of the node is:

class ListNode(self, val):
    def int(self, val):
        self.val = val 
        self.next = next

The start of the linked list is called head, end of the list is tail, who's next pointer points to None. Sentinel node is a dummy node added at the head or tail of the list to make operations easier on the list.

There are three types of linked lists

1. Singly linked list, have uni-directional pointers to next immediate node in unidirectional.
2. Doubly linked list, have bi-directional pointers to neighboring nodes.
3. Circular linked list, have uni-directional pointers to the next node and tail points to the head of the list.

Applications of Linked Lists are:

1. Linear linked lists are used to implement stacks. It would be FILO [first in last out] procedure to access data.
2. Doubly Linked Lists used in implementation of buffer to provide undo/redo feature to word application or photoshop application
3. Circular linked lists are used to implement round robin technique for process scheduling in operating systems.
4. Program stack trace is also a implementation of linked lists.
5. Browser back and forward button are implementation of the linked list concepts
6. Used in implementation of other data structures like graphs, trees, stacks and queues
7. LRU cache is implemented using linked lists
8. Implementation of polynomial addition

Time complexity of linked lists:

Search: O(n)
Insert: O(1)
Delete: O(n)