Insert at Beginning of Doubly Linked List in DSA Java - Build from Scratch

Insert at Beginning of Doubly Linked List

📖 Scenario: You are managing a playlist of songs. Each song is linked to the previous and next songs, allowing you to move forward or backward easily.Sometimes, you want to add a new favorite song right at the start of the playlist so you can listen to it first.

🎯 Goal: Build a doubly linked list and write code to insert a new song at the beginning of the playlist.

📋 What You'll Learn

Create a Node class with data, prev, and next fields

Create a DoublyLinkedList class with a head field

Write a method insertAtBeginning to add a new node at the start

Print the playlist from head to end showing the order of songs

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding linked lists is important for software development jobs, especially those involving data structures, algorithms, and system design.

1

Create Node and DoublyLinkedList classes

Create a class called Node with a String data field, and Node prev and Node next fields. Then create a class called DoublyLinkedList with a Node head field initialized to null.

DSA Java

// Your code here

Hint

Define the Node class with the required fields and a constructor. Then define the DoublyLinkedList class with a head field.

2

Add insertAtBeginning method

Inside the DoublyLinkedList class, add a method called insertAtBeginning that takes a String data parameter. This method should create a new Node with the given data and insert it at the start of the list, updating head and the links properly.

DSA Java

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

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

class DoublyLinkedList {
    Node head;

    DoublyLinkedList() {
        this.head = null;
    }

    // Add insertAtBeginning method below
    // Your code here
}

Hint

Create a new node. If the list is empty, set head to the new node. Otherwise, link the new node before the current head and update head.

3

Add method to print the list

Inside the DoublyLinkedList class, add a method called printList that prints the data of each node from head to the end, separated by -> , ending with null.

DSA Java

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

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

class DoublyLinkedList {
    Node head;

    DoublyLinkedList() {
        this.head = null;
    }

    void insertAtBeginning(String data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // Add printList method below
    // Your code here
}

Hint

Use a loop to go through each node starting from head. Print the data followed by -> . After the loop, print null.

4

Test insertion and print the list

In the main method, create a DoublyLinkedList object called playlist. Insert these songs at the beginning in this order: "Song3", "Song2", "Song1". Then call playlist.printList() to display the playlist.

DSA Java

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

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

class DoublyLinkedList {
    Node head;

    DoublyLinkedList() {
        this.head = null;
    }

    void insertAtBeginning(String data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.print("null\n");
    }
}

// Your code here

Hint

Create the main method. Make a DoublyLinkedList object called playlist. Insert songs in the order given using insertAtBeginning. Finally, call printList to show the playlist.

Practice

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

easy

A. To add a new node after the tail node

B. To reverse the entire list

C. To delete the first node of the list

D. To add a new node before the current head node

Solution

1. Step 1: Understand the position of insertion

   Inserting at the beginning means placing the new node before the current head node.

2. Step 2: Identify the effect on the list

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

3. Final Answer:

   To add a new node before the current head node -> Option D

4. Quick Check:

   Insert at beginning = add before head [OK]

Hint: Beginning insertion means new node becomes the head [OK]

Common Mistakes:

• Confusing beginning with end insertion
• Thinking insertion deletes nodes
• Mixing up singly and doubly linked list behavior

2. Which of the following is the correct syntax to create a new node in Java for a doubly linked list?

easy

A. Node newNode = Node(data); newNode.prev = null; newNode.next = null;

B. Node newNode = new Node(data); newNode.prev = null; newNode.next = null;

C. Node newNode = new Node(); newNode.data = data; newNode.prev = null; newNode.next = null;

D. Node newNode = new Node(data); newNode.prev = data; newNode.next = data;

Solution

1. Step 1: Understand Java object creation syntax

   In Java, objects are created using the 'new' keyword followed by the constructor.

2. Step 2: Check node initialization

   The node's previous and next pointers should be set to null initially.

3. Final Answer:

   Node newNode = new Node(data); newNode.prev = null; newNode.next = null; -> Option B

4. Quick Check:

   Java new object = new Constructor() [OK]

Hint: Use 'new' keyword and constructor to create objects [OK]

Common Mistakes:

• Omitting 'new' keyword
• Assigning data to prev or next pointers
• Using incorrect constructor syntax

3. What will be the output of the doubly linked list after inserting 10 at the beginning of the list containing nodes 20 <-> 30?

medium

A. 10 <-> 20 <-> 30

B. 20 <-> 30 <-> 10

C. 30 <-> 20 <-> 10

D. 10 <-> 30 <-> 20

Solution

1. Step 1: Identify current list order

   The list currently is 20 <-> 30, with 20 as head and 30 as tail.

2. Step 2: Insert 10 at beginning

   New node 10 becomes head, its next points to 20, and 20's prev points to 10.

3. Final Answer:

   10 <-> 20 <-> 30 -> Option A

4. Quick Check:

   Insert at beginning adds node before head [OK]

Hint: New node at start shifts old head right [OK]

Common Mistakes:

• Appending instead of prepending
• Not updating previous pointer of old head
• Reversing node order incorrectly

4. Given the following code snippet for inserting at the beginning of a doubly linked list, what is the error?

void insertAtBeginning(int data) {
  Node newNode = new Node(data);
  newNode.next = head;
  head.prev = newNode;
  head = newNode;
}

medium

A. No error, code works correctly

B. head should be updated before setting newNode.next

C. head.prev = newNode; causes NullPointerException if list is empty

D. newNode.next should be null

Solution

1. Step 1: Analyze code for empty list case

   If the list is empty, head is null, so head.prev causes NullPointerException.

2. Step 2: Identify fix

   Check if head is not null before setting head.prev = newNode.

3. Final Answer:

   head.prev = newNode; causes NullPointerException if list is empty -> Option C

4. Quick Check:

   Null head means head.prev causes error [OK]

Hint: Check for null head before accessing head.prev [OK]

Common Mistakes:

• Ignoring empty list case
• Assuming head is never null
• Misordering pointer updates

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25. You want to insert a new node with value 1 at the beginning and then reverse the list. What will be the final list after these operations?

hard

A. 25 <-> 15 <-> 5 <-> 1

B. 1 <-> 5 <-> 15 <-> 25

C. 1 <-> 25 <-> 15 <-> 5

D. 5 <-> 15 <-> 25 <-> 1

Solution

1. Step 1: Insert 1 at beginning

   List becomes 1 <-> 5 <-> 15 <-> 25 after insertion.

2. Step 2: Reverse the list

   Reversing swaps head and tail, so list becomes 25 <-> 15 <-> 5 <-> 1.

3. Final Answer:

   25 <-> 15 <-> 5 <-> 1 -> Option A

4. Quick Check:

   Insert at start then reverse flips order [OK]

Hint: Insert first, then reverse flips entire list [OK]

Common Mistakes:

• Reversing before insertion
• Not updating prev pointers when reversing
• Confusing node order after reverse