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:
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: