Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Operations on Singly Linked List

Operations in Singly Linked List

In a singly linked list, each element (known as a node) contains a data value and a reference (or link) to the next node in the sequence. Given this basic structure, let's explore some common operations:

1. Insert

Insertion in a singly linked list can be of three types:

  • At the Beginning - O(1): Add a new node before the current head of the list.
  • At the End - O(n): Traverse the list to the last node and add the new node after it.
  • After a Given Node - O(n): Traverse the list to the desired node and insert the new node after it.

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

After a Given Node - O(n): Traverse the list to the desired node and insert the new node after it.

As reflected in the code example, the time complexity for this operation is O(1) since you don't need to traverse the list. You set the next reference of the provided node to the newly created node which in turn points the previous next.

Reading Progress

0%

Vote for new content