Applications of Linked Lists

Aditya Bhamidipati
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

  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)

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

--

--

Aditya Bhamidipati
Aditya Bhamidipati

Written by Aditya Bhamidipati

Curious Human, Software Developer and a Dog Lover

No responses yet

Write a response