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.