Insert at Specific Position in Doubly Linked List in DSA Python - Build from Scratch

Insert at Specific Position in Doubly Linked List

📖 Scenario: You are managing a playlist of songs. Each song is connected to the previous and next song, allowing you to move forward or backward easily. You want to add a new song at a specific position in this playlist.

🎯 Goal: Build a doubly linked list representing the playlist and insert a new song at a given position.

📋 What You'll Learn

Create a doubly linked list with three songs: 'Song1', 'Song2', 'Song3'.

Create a variable position to specify where to insert the new song.

Write code to insert 'NewSong' at the position in the doubly linked list.

Print the playlist from head to tail showing all songs in order.

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, web browsers, and other applications where you need to move forward and backward through items.

💼 Career

Understanding linked lists and insertion operations is fundamental for software development roles involving data structures and memory management.

1

Create the initial doubly linked list

Create a class called Node with attributes data, prev, and next. Then create three nodes with data 'Song1', 'Song2', and 'Song3'. Link them to form a doubly linked list where head points to the first node.

DSA Python

# Define Node class and create three linked nodes
# Your code here

Hint

Start by defining the Node class with data, prev, and next. Then create three nodes and link them forward and backward.

2

Set the insertion position

Create a variable called position and set it to 2 to indicate where the new song will be inserted.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

head = Node('Song1')
second = Node('Song2')
third = Node('Song3')

head.next = second
second.prev = head
second.next = third
third.prev = second

# Set the position to insert the new song
# Your code here

Hint

Just create a variable position and assign it the value 2.

3

Insert the new song at the given position

Create a new node called new_node with data 'NewSong'. Insert new_node at the position in the doubly linked list. Update the prev and next pointers of the surrounding nodes accordingly.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

head = Node('Song1')
second = Node('Song2')
third = Node('Song3')

head.next = second
second.prev = head
second.next = third
third.prev = second

position = 2

# Insert 'NewSong' at position 2
# Your code here

Hint

Traverse the list to the node before the insertion point. Then adjust the next and prev pointers to insert the new node.

4

Print the playlist from head to tail

Use a current variable to traverse the doubly linked list from head to the end. Print the data of each node separated by -> and end with null.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

head = Node('Song1')
second = Node('Song2')
third = Node('Song3')

head.next = second
second.prev = head
second.next = third
third.prev = second

position = 2

new_node = Node('NewSong')

current = head
count = 1
while count < position - 1 and current.next is not None:
    current = current.next
    count += 1

new_node.next = current.next
if current.next is not None:
    current.next.prev = new_node
current.next = new_node
new_node.prev = current

# Print the playlist from head to tail
# Your code here

Hint

Start from head and move to each next node, adding the song names to a string. End with null and print the string.

Practice

1. What is the main purpose of inserting a node at a specific position in a doubly linked list?

easy

A. To add a new node exactly where you want in the list

B. To delete a node from the list

C. To reverse the entire list

D. To find the length of the list

Solution

1. Step 1: Understand insertion in doubly linked list

   Insertion at a specific position means adding a new node exactly at that place, shifting others if needed.

2. Step 2: Differentiate from other operations

   Deleting removes nodes, reversing changes order, and length counts nodes, none insert at a position.

3. Final Answer:

   To add a new node exactly where you want in the list -> Option A

4. Quick Check:

   Insert at position = Add node at exact place [OK]

Hint: Insertion means adding, not deleting or reversing [OK]

Common Mistakes:

• Confusing insertion with deletion
• Thinking insertion changes list order
• Mixing insertion with counting nodes

2. Which of the following is the correct way to update the previous pointer of the new node when inserting at position 3 in a doubly linked list?

easy

A. new_node.prev = null

B. new_node.prev = head

C. new_node.prev = head.next.next

D. new_node.prev = head.next

Solution

1. Step 1: Identify the node before position 3

   Position 3 means the new node comes after the second node, so prev points to node at position 2 (head.next).

2. Step 2: Assign previous pointer correctly

   new_node.prev must point to the node at position 2, which is head.next.

3. Final Answer:

   new_node.prev = head.next -> Option D

4. Quick Check:

   Prev pointer = node before insertion [OK]

Hint: Prev points to node before insertion position [OK]

Common Mistakes:

• Setting prev to null instead of correct node
• Confusing prev with next pointer
• Using head instead of node before position

3. What will be the output list after inserting a node with value 10 at position 2 in the doubly linked list 5 <-> 15 <-> 20?

medium

A. 5 <-> 15 <-> 10 <-> 20 <-> null

B. 5 <-> 10 <-> 15 <-> 20 <-> null

C. 10 <-> 5 <-> 15 <-> 20 <-> null

D. 5 <-> 15 <-> 20 <-> 10 <-> null

Solution

1. Step 1: Understand position 2 insertion

   Position 2 means the new node goes after the first node (5) and before the second node (15).

2. Step 2: Insert node with value 10 at position 2

   List becomes 5 <-> 10 <-> 15 <-> 20, with null at the end.

3. Final Answer:

   5 <-> 10 <-> 15 <-> 20 <-> null -> Option B

4. Quick Check:

   Insert at 2 shifts old 2nd node right [OK]

Hint: Insert pushes existing nodes right from position [OK]

Common Mistakes:

• Inserting after instead of at position
• Placing new node at wrong position
• Confusing list order after insertion

4. Given this code snippet for insertion at position 3, what is the error?

temp = head
for _ in range(2):
    temp = temp.next
new_node.next = temp.next
new_node.prev = temp
if temp.next:
    temp.next.prev = new_node
temp.next = new_node

medium

A. Loop runs one time too many causing temp to be wrong

B. new_node.prev should be temp.prev

C. new_node.next should be temp

D. Missing check if head is null before loop

Solution

1. Step 1: Analyze loop and temp assignment

   The loop with range(2) moves temp from head (position 1) to position 2, then to position 3.

2. Step 2: Identify the position error

   For insertion at position 3 (new node becomes position 3), temp must be at position 2 to insert after it; range(2) overshoots to position 3, so loop runs one time too many.

3. Final Answer:

   Loop runs one time too many causing temp to be wrong -> Option A

4. Quick Check:

   Loop range should be (position - 2) [OK]

Hint: Loop iterations = position - 2 for temp at (position - 1) [OK]

Common Mistakes:

• Loop runs one time too many
• Confusing prev and next pointers
• Incorrect loop count for position

5. You have a doubly linked list: 1 <-> 3 <-> 5 <-> 7 <-> null. You want to insert a node with value 4 at position 3. After insertion, what will be the correct sequence of the list?

medium

A. 4 <-> 1 <-> 3 <-> 5 <-> 7 <-> null

B. 1 <-> 4 <-> 3 <-> 5 <-> 7 <-> null

C. 1 <-> 3 <-> 4 <-> 5 <-> 7 <-> null

D. 1 <-> 3 <-> 5 <-> 7 <-> 4 <-> null

Solution

1. Step 1: Identify position 3 in the list

   Position 3 means the new node goes after the second node (3) and before the third node (5).

2. Step 2: Insert node with value 4 at position 3

   The list becomes 1 <-> 3 <-> 4 <-> 5 <-> 7 <-> null, maintaining order and links.

3. Final Answer:

   1 <-> 3 <-> 4 <-> 5 <-> 7 <-> null -> Option C

4. Quick Check:

   Insert at position 3 places node between 3 and 5 [OK]

Hint: Insert at position shifts old node at that position right [OK]

Common Mistakes:

• Inserting before position 1 instead of 3
• Appending at end instead of position
• Mixing node values order after insertion