# Applications of Linked Lists

2 min readMar 5, 2021

--

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

- Singly linked list, have uni-directional pointers to next immediate node in unidirectional.
- Doubly linked list, have bi-directional pointers to neighboring nodes.
- 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:

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

Time complexity of linked lists:

`Search: O(n)`

Insert: O(1)

Delete: O(n)