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

Insert at Specific Position in Doubly Linked List

📖 Scenario: You are managing a playlist of songs where each song is linked to the previous and next songs. You want to insert a new song at a specific position in the playlist.

🎯 Goal: Build a doubly linked list of songs and insert a new song at a given position.

📋 What You'll Learn

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

Add an integer variable position to specify where to insert the new song

Write a method insertAtPosition to insert a new song at the given position

Print the playlist from head to tail after insertion

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers, and other apps to move forward and backward through items efficiently.

💼 Career

Understanding linked list insertion is fundamental for software engineering roles involving data structures and memory management.

1

Create the initial doubly linked list

Create a class Node with String data, Node prev, and Node next. Then create a doubly linked list with three nodes containing "Song1", "Song2", and "Song3" linked in order. Store the head node in a variable called head.

DSA Java

// Define Node class and create doubly linked list with "Song1", "Song2", "Song3"
// Your code here

Hint

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

2

Add position variable for insertion

Add an integer variable called position and set it to 2 to specify the position where the new song will be inserted.

DSA Java

class Node {
    String data;
    Node prev;
    Node next;

    Node(String data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class Playlist {
    public static void main(String[] args) {
        Node head = new Node("Song1");
        Node second = new Node("Song2");
        Node third = new Node("Song3");

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

        // Add position variable here
        // Your code here
    }
}

Hint

Just add int position = 2; inside the main method.

3

Write method to insert at specific position

Write a static method insertAtPosition that takes Node head, String data, and int position as parameters. Insert a new node with the given data at the given position in the doubly linked list and return the new head. Use this method inside main to insert "NewSong" at position.

DSA Java

    public static Node insertAtPosition(Node head, String data, int position) {
        Node newNode = new Node(data);
        if (position == 1) {
            newNode.next = head;
            if (head != null) {
                head.prev = newNode;
            }
            return newNode;
        }
        Node current = head;
        int count = 1;
        while (current != null && count < position - 1) {
            current = current.next;
            count++;
        }
        if (current == null) {
            return head; // position is beyond list length, no insertion
        }
        newNode.next = current.next;
        if (current.next != null) {
            current.next.prev = newNode;
        }
        current.next = newNode;
        newNode.prev = current;
        return head;
        head = insertAtPosition(head, "NewSong", position);
        // Call printList here

Hint

Traverse to the node before the position, then adjust pointers to insert the new node.

4

Print the doubly linked list after insertion

Write a printList method that takes Node head and prints the list from head to tail in the format: Song1 -> NewSong -> Song2 -> Song3 -> null. Call this method from main after insertion.

DSA Java

Hint

Traverse from head and print each node's data followed by ' -> ', ending with 'null'.

Practice

1. What happens when you insert a new node at position 1 in a doubly linked list?

easy

A. The new node becomes the new head of the list.

B. The new node is added at the end of the list.

C. The new node replaces the last node.

D. The list remains unchanged.

Solution

1. Step 1: Understand position 1 insertion

   Inserting at position 1 means adding the node at the start of the list.

2. Step 2: Effect on the list head

   The new node becomes the head, and its next points to the old head.

3. Final Answer:

   The new node becomes the new head of the list. -> Option A

4. Quick Check:

   Insert at position 1 = new head [OK]

Hint: Position 1 means new head insertion [OK]

Common Mistakes:

• Thinking position 1 means end insertion
• Not updating previous head's previous pointer
• Ignoring head pointer update

2. Which of the following is the correct syntax to insert a new node at position pos in a doubly linked list in Java?

easy

A. newNode.next = current; newNode.prev = current.next; current.next = newNode; current.prev = newNode;

B. newNode.prev = current.next; newNode.next = current; current.prev.next = newNode; current.prev = newNode;

C. newNode.next = current.prev; newNode.prev = current.next; current.next = newNode; current.prev = newNode;

D. newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode;

Solution

1. Step 1: Identify correct pointer updates

   For insertion, newNode's next points to current's next, and prev points to current.

2. Step 2: Update surrounding nodes

   current.next's prev must point to newNode, and current's next must point to newNode.

3. Final Answer:

   newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode; -> Option D

4. Quick Check:

   Correct pointer updates = newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode; [OK]

Hint: Remember to update both next and prev pointers [OK]

Common Mistakes:

• Swapping next and prev pointers
• Not updating current.next.prev
• Incorrect order of pointer assignments

3. Given the doubly linked list: 1 <-> 2 <-> 4 <-> null, what will be the list after inserting node with value 3 at position 3?

medium

A. 1 <-> 2 <-> 3 <-> 4 <-> null

B. 1 <-> 3 <-> 2 <-> 4 <-> null

C. 3 <-> 1 <-> 2 <-> 4 <-> null

D. 1 <-> 2 <-> 4 <-> 3 <-> null

Solution

1. Step 1: Locate position 3 in the list

   Positions: 1=1, 2=2, 3=4 currently. Insert before node with value 4.

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

   New node's next points to node with value 4, prev points to node with value 2. Update pointers accordingly.

3. Final Answer:

   1 <-> 2 <-> 3 <-> 4 <-> null -> Option A

4. Quick Check:

   Insert at position 3 places 3 before 4 [OK]

Hint: Insert before node currently at position [OK]

Common Mistakes:

• Inserting after position instead of at position
• Not updating prev pointer of next node
• Confusing node values and positions

4. Consider this code snippet to insert at position 2 in a doubly linked list:

Node newNode = new Node(5);
Node current = head;
current = current.next;
newNode.next = current.next;
newNode.prev = current;
current.next = newNode;
newNode.next.prev = newNode;

What is the error in this code?

medium

A. It does not handle insertion at head correctly.

B. It may cause NullPointerException if current.next is null.

C. It forgets to update newNode.prev pointer.

D. It inserts the node at the end always.

Solution

1. Step 1: Analyze newNode.next assignment

   newNode.next = current.next; If current.next is null (inserting at end), newNode.next.prev causes error.

2. Step 2: Identify NullPointerException risk

   Accessing newNode.next.prev without checking null causes NullPointerException.

3. Final Answer:

   It may cause NullPointerException if current.next is null. -> Option B

4. Quick Check:

   Check for null before newNode.next.prev update [OK]

Hint: Always check if next node is null before accessing its prev [OK]

Common Mistakes:

• Not checking for null before pointer updates
• Assuming list has more nodes without validation
• Forgetting to update head or tail pointers

5. You have a doubly linked list: 10 <-> 20 <-> 30 <-> 40 <-> null. You want to insert a node with value 25 at position 3. After insertion, you also want to delete the node at position 4. What will be the final list?

hard

A. 10 <-> 25 <-> 20 <-> 40 <-> null

B. 10 <-> 20 <-> 25 <-> 30 <-> null

C. 10 <-> 20 <-> 25 <-> 40 <-> null

D. 10 <-> 20 <-> 30 <-> 25 <-> null

Solution

1. Step 1: Insert 25 at position 3

   Positions before insertion: 1=10, 2=20, 3=30, 4=40. Insert 25 before 30, so list becomes 10 <-> 20 <-> 25 <-> 30 <-> 40.

2. Step 2: Delete node at position 4

   After insertion, position 4 is node with value 30. Remove it by updating pointers: 25's next points to 40, 40's prev points to 25.

3. Final Answer:

   10 <-> 20 <-> 25 <-> 40 <-> null -> Option C

4. Quick Check:

   Insert then delete correct nodes = 10 <-> 20 <-> 25 <-> 40 <-> null [OK]

Hint: Insert first, then delete at updated position [OK]

Common Mistakes:

• Deleting wrong node after insertion
• Not updating pointers after deletion
• Confusing positions before and after insertion