Thread by @swapnakpanda

Linked List: Frequently used Operations

🔥 Interview Questions with Beginner Friendly Explanations and Pseudo Code 🔥

👇

0️⃣ Basics

✪ What is a Linked List?

• a LINEAR data structure
• its elements may not be in contiguous memory location
• each element has a reference to its next element

✪ What is an element in a Linked List popularly called?
A Node.

++

✪ What is the structure of a Node in Linked List?

A node has 2 parts.

• First one contains the value
• Second one contains the reference (or, pointer) to the next node. For the last node this is NULL as it doesn't point to any other node.

++

✪ What extra is required?

• A reference to start traversal with.
• It's convenient to have the reference of the very first node.
• This reference is referred as Head.

✪ Pseudo Code for Node and, Head ✪

Node {
Value,
next: Node
}
Head = NULL

✪ ✪ ✪ ✪ ✪ ✪ ✪ ✪

1️⃣ Traverse through Nodes

✪ Why do we need to traverse?
Elements in Linked List are not stored contiguously. Then how to reach at an element? For that we need to traverse.

✪ Where to start?
Start from Head
If Head is NULL, Linked List is empty hence no traversal required.

++

✪ How to traverse from one node to another?
Using "next" reference of a node.

✪ Where to end?
When "next" reference of a node is NULL, it means that node doesn't point any other node. So, that's the end node in the linked list. We will stop there.

2️⃣ IsEmpty

If Head is NULL, that means there are no elements in the linked list. Hence it is empty.

✪ Pseudo Code ✪

Return Head is NULL

✪✪✪✪✪✪✪✪✪✪

3️⃣ Size

Traverse through the linked list to find out the size (number of nodes in the list)

✪ Pseudo Code ✪

size = 0
curr = Head

while curr is not NULL
curr = curr->next
size++

Return size

✪✪✪✪✪✪✪✪✪✪

4️⃣.1️⃣ Get Front Node

Head has the reference to the very first node aka the "Front Node".

But when Head is NULL, linked list is empty and hence there is no front node present.

✪ Pseudo Code ✪

If Head is NULL
Throw Error
Return Head

4️⃣.2️⃣ Get End Node

Starting from Head, we have to traverse till the end node.

✪ Pseudo Code ✪

If Head is NULL
Throw Error

current = Head
while current->next is not NULL
current = current->next

Return current
✪ ✪ ✪ ✪ ✪ ✪ ✪ ✪ ✪ ✪

4️⃣.3️⃣ Get Any Node

Let's say the task is to get a node at kth index where 0th index means the very first node.

✪ Pseudo Code ✪

current = Head
i = 0
while i < k and current is not NULL
current = current->next
i++

If i < 0 or current is NULL
Throw Error

Return current

5️⃣.1️⃣ Insert at the Front

Given: "node", which will be inserted at the front

It means after insertion,
• the current Head node should be the 2nd node
• the "node" should be the Head node

✪ Pseudo Code ✪

If node is NULL
Throw Error

node->next = Head
Head = node

✪✪✪

5️⃣.2️⃣ Insert at the Last

Given:
• "node", which will be inserted at the last
• "last", which is current last node

It means after insertion,
• next of "last" node should point to "node"

✪ Pseudo Code ✪
If last is NULL
Throw Error

last->next = node

✪✪✪✪✪✪✪✪✪

5️⃣.3️⃣ Insert at any position

Given:
• "node", which will be inserted at kth position
• "prev", which is the node at (k-1)th position [Use 4️⃣.3️⃣ to get it)

It means after insertion,
• next of "node" should point to next of "prev"
• next of "prev" should point to "node"

++

✪ Pseudo Code ✪
If node is NULL or prev is NULL
Throw Error

node->next = prev->next
prev->next = node

✪✪✪✪✪✪✪✪✪

6️⃣.1️⃣ Delete from Front

After deletion,
• the current Head node should refer to the current 2nd node
• the "next" of 1st node should be NULL

✪ Pseudo Code ✪

If Head is NULL
Throw Error

temp = Head
Head = Head->next
temp->next = NULL

✪✪✪

6️⃣.2️⃣ Delete from Last

Given:
• "prevToLast", which is the previous to current last node

It means after deletion,
• next of "prevToLast" node should be NULL and effectively becomes the last node.

✪ Pseudo Code ✪
If prevToLast is NULL
Throw Error

prevToLast->next = NULL

6️⃣.3️⃣ Delete from any position

Given:
• "prev", which is the node at (k-1)th position [Use 4️⃣.3️⃣ to get it)

It means after deletion,
• next of "prev" should point to next of next of "prev"

++

✪ Pseudo Code ✪
If prev is NULL or prev->next is NULL
Throw Error

temp = prev->next
prev->next = temp->next
temp->next = NULL

✪✪✪✪✪✪✪✪✪

7️⃣ Space & Time Complexity

IsEmpty: O(1),N/A
Size: O(n), N/A
GetFrontNode: O(1), N/A
GetEndNode: O(n), N/A
GetAnyNode: O(n), N/A
InsertAtFront: O(1), N/A
InsertAtEnd: O(1), N/A
InsertAtAny: O(1), N/A
DeleteFromFront: O(1), O(1)
DeleteFromEnd: O(1), O(1)
DeleteFromAny: O(1), O(1)