How do you insert a node at the beginning of a doubly linked list?

This takes O(1) time. Java example: static Node insertAtBeginning(Node head, int value) { Node node = new Node(value); node.next = head; if (head != null) { head.prev = node; } return node; // new head }

How do you insert a node at the end of a doubly linked list?

Without a tail reference this takes O(n); keeping a tail field makes it O(1).

How do you insert a node after a given node?

Because you already have the node, this is O(1). Java example: static void insertAfter(Node given, int value) { Node node = new Node(value); node.prev = given; node.next = given.next; if (given.next != null) { given.next.prev = node; } given.next = node; }

How do you insert a node before a given node?

This is the operation a singly linked list cannot do in O(1).

Write a Java method to insert a value at a given position.

Java example: // position is 0-based; positions past the end append the node static Node insertAt(Node head, int position, int value) { if (position == 0 || head == null) { Node node = new Node(value); node.next = head; if (head != null) head.prev = node; return node; } Node current = head; for (int i = 0; i < position - 1 && current.next != null; i++) { current = current.next; } Node node = new Node(value); node.prev = current; node.next = current.next; if (current.next != null) { current.next.prev = node; } current.next = node; return head; }

Why does the order of link updates matter during insertion?

If you overwrite given.next before saving it into node.next, you lose the reference to the rest of the list. Always set the new node's links first, then update the neighbours.

Write a Java method to insert a value into a sorted doubly linked list.

Java example: static Node sortedInsert(Node head, int value) { Node node = new Node(value); if (head == null || value <= head.data) { node.next = head; if (head != null) head.prev = node; return node; } Node current = head; while (current.next != null && current.next.data < value) { current = current.next; } node.next = current.next; node.prev = current; if (current.next != null) { current.next.prev = node; } current.next = node; return head; }

What edge cases should insertion handle?

Inserting into an empty list: the new node becomes both head and tail. Inserting before the head: the head reference changes. Inserting after the tail: the tail reference changes, and there is no next node to update. A position larger than the list length.

How many links change when inserting in the middle of a doubly linked list?

Four: the new node's prev and next, the previous node's next, and the following node's prev. In a singly linked list only two links change.

How does java.util.LinkedList insert at a position?

add(index, element) first walks to the node at that index, starting from whichever end is closer, then links the new node before it. The walk is O(n), and the link update is O(1). Using a ListIterator avoids the walk when you insert many elements in one pass.

Insertion in Doubly Linked List

Q: Why does the order of link updates matter during insertion?

If you overwrite given.next before saving it into node.next, you lose the reference to the rest of the list. Always set the new node's links first, then update the neighbours.

Q: Write a Java method to insert a value into a sorted doubly linked list.

Java example: static Node sortedInsert(Node head, int value) { Node node = new Node(value); if (head == null || value <= head.data) { node.next = head; if (head != null) head.prev = node; return node; } Node current = head; while (current.next != null && current.next.data < value) { current = current.next; } node.next = current.next; node.prev = current; if (current.next != null) { current.next.prev = node; } current.next = node; return head; }

Q: What edge cases should insertion handle?

Inserting into an empty list: the new node becomes both head and tail. Inserting before the head: the head reference changes. Inserting after the tail: the tail reference changes, and there is no next node to update. A position larger than the list length.

Q: How many links change when inserting in the middle of a doubly linked list?

Four: the new node's prev and next, the previous node's next, and the following node's prev. In a singly linked list only two links change.

Q: How does java.util.LinkedList insert at a position?

add(index, element) first walks to the node at that index, starting from whichever end is closer, then links the new node before it. The walk is O(n), and the link update is O(1). Using a ListIterator avoids the walk when you insert many elements in one pass.

In this tutorial, we will see all about the insert operation in a doubly linked list. In the insert operation, we will add a new node to the doubly linked list at any position.

In a Doubly Linked List, we can insert a node at the following positions:

At the beginning of the list.
At the end of the list.
At the specific position of the list.

1. Insert a node at the beginning of the list.

In the below given example we will see how to insert a new node in the beginning or front the doubly linked list.

InsertAtBeginningInDLL.java

// Java Program to insert a node at the beginning of a doubly linked list
public class InsertAtBeginningInDLL {
  static Node head;

  // Method to insert a node in doubly linked list
  static void insertNode(int data) {
    Node newNode = new Node(data);
    Node last = head;
    if (head == null) {
      head = newNode;
      return;
    }
    while (last.next != null) {
      last = last.next;
    }
    last.next = newNode;
    newNode.prev = last;
  }

  // Method to insert a node at the beginning of the list
  static Node insertAtBeginning(Node head, int data) {

    Node new_node = new Node(data);
    new_node.next = head;

    // Set previous of head as new node
    if (head != null) {
      head.prev = new_node;
    }

    return new_node;
  }

  // Method to print the doubly linked list
  public static void printList(Node head) {
    Node node = head;
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Create a doubly linked list
    insertNode(10);
    insertNode(20);
    insertNode(30);
    insertNode(40);
    insertNode(50);

    System.out.println("Original doubly linked list:");
    printList(head);

    // Insert a new node at the front of the list
    head = insertAtBeginning(head, 90);

    // Print the updated list
    System.out.print("List, After inserting a node at the beginning:\n");
    printList(head);
  }
}

Output

Original doubly linked list:
10 20 30 40 50
List, After inserting a node at the beginning:
90 10 20 30 40 50

2. Insert a node at the end of the doubly linked list.

In the below given example we will see how to insert a new node at the end of the doubly linked list.

InsertAtEndInDLL.java

// Java Program to insert a node at the end of doubly linked list
public class InsertAtEndInDLL {
  static Node head;

  // Method to insert a node in doubly linked list
  static void insertNode(int data) {
    Node newNode = new Node(data);
    Node last = head;
    if (head == null) {
      head = newNode;
      return;
    }
    while (last.next != null) {
      last = last.next;
    }
    last.next = newNode;
    newNode.prev = last;
  }

  // Method to insert a new node at the end of the DLL
  static Node insertNodeAtEnd(Node head, int newData) {

    Node newNode = new Node(newData);
    if (head == null) {
      head = newNode;
    } else {
      Node node = head;
      while (node.next != null) {
        node = node.next;
      }

      // Set the next of last node to the new node
      node.next = newNode;

      // Set the prev of new node to the last node
      newNode.prev = node;
    }

    return head;
  }

  // Method to print the doubly linked list
  public static void printList(Node head) {
    Node node = head;
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Create a doubly linked list
    insertNode(10);
    insertNode(20);
    insertNode(30);
    insertNode(40);
    insertNode(50);

    System.out.println("Original doubly linked list:");
    printList(head);

    // Insert a new node with data 60 at the end
    head = insertNodeAtEnd(head, 60);

    System.out.println("After inserting, doubly linked list:");
    printList(head);
  }
}

Output

Original doubly linked list:
10 20 30 40 50
After inserting, doubly linked list:
10 20 30 40 50 60

3. Insert a node at a specific position of the list

In the below given example we will see how to insert a new node in the specific position in the doubly linked list.

InsertAtSpecPositionInDLL.java

// Java Program to insert a node at the specific position in DLL
public class InsertAtSpecPositionInDLL {
  static Node head;

  // Method to insert a node in a doubly linked list
  static void insertNode(int data) {
    Node newNode = new Node(data);
    Node last = head;
    if (head == null) {
      head = newNode;
      return;
    }
    while (last.next != null) {
      last = last.next;
    }
    last.next = newNode;
    newNode.prev = last;
  }

  // Method to insert a node at the specific position in a doubly linked list
  static Node insertNodeAtPosition(Node head, int position, int data) {
    Node new_node = new Node(data);

    // Insertion at the beginning
    if (position == 1) {
      new_node.next = head;

      if (head != null) {
        head.prev = new_node;
      }

      head = new_node;
      return head;
    }

    Node curr = head;

    for (int i = 1; i < position - 1 && curr != null; ++i) {
      curr = curr.next;
    }

    // If the position is out of bounds
    if (curr == null) {
      System.out.println("Error: Given position is out of bounds.");
      return head;
    }

    new_node.prev = curr;
    new_node.next = curr.next;
    curr.next = new_node;

    if (new_node.next != null) {
      new_node.next.prev = new_node;
    }

    return head;
  }

  // Method to print the doubly linked list
  public static void printList(Node head) {
    Node node = head;
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Create a doubly linked list
    insertNode(10);
    insertNode(20);
    insertNode(30);
    insertNode(40);
    insertNode(50);

    System.out.println("Original doubly linked list:");
    printList(head);

    // Insert new node with data 25 at position 3
    int data = 25;
    int position = 3;
    head = insertNodeAtPosition(head, position, data);

    System.out.println("After inserting, doubly linked list:");
    printList(head);
  }
}

Output

Original doubly linked list:
10 20 30 40 50
After inserting, doubly linked list:
10 20 25 30 40 50

Help Us Improve

Insertion in Doubly Linked List

1. Insert a node at the beginning of the list.

2. Insert a node at the end of the doubly linked list.

3. Insert a node at a specific position of the list

Frequently Asked Questions (FAQ)