Java 在双向链表中插入新节点到中间的程序

17 Mar 2025 | 4 分钟阅读

在此程序中，我们创建一个双向链表并在列表的中间插入一个新节点。如果列表为空，head 和 tail 都将指向新节点。如果列表不为空，我们将计算列表的大小并将其除以 2，以获得需要插入新节点的中点。

Java program to insert a new node at the middle of the Doubly Linked List

考虑上图；需要在列表的中间添加一个新节点。首先，我们计算大小，在本例中为 4。因此，为了获得中点，我们将它除以 2 并将其存储在一个变量 mid 中。Node current 将指向 head。首先，我们遍历列表，直到 current 指向 mid 位置。定义另一个节点 temp，它指向 current 的下一个节点。在 current 和 temp 之间插入新节点

算法

定义一个 Node 类，它表示列表中的一个节点。它将有三个属性：数据、previous 指向前一个节点，以及 next 指向下一个节点。
为创建双向链表定义另一个类，它有两个节点：head 和 tail。最初，head 和 tail 将指向 null。
addNode() 将向列表中添加节点。
- 它首先检查头节点是否为 null，然后将节点作为头节点插入。
- 头节点和尾节点都将指向新添加的节点。
- 头节点的前一个指针将指向 null，尾节点的下一个指针将指向 null。
- 如果头节点不为 null，则新节点将插入到列表的末尾，使得新节点的前一个指针将指向尾节点。
- 新节点将成为新的尾节点。尾节点的下一个指针将指向 null。

a. addInMid() 将在列表的中间添加一个节点

它首先检查 head 是否为 null（空列表），然后它将节点插入为 head。
头节点和尾节点都将指向新添加的节点。
如果列表不为空，那么我们计算大小并将其除以 2 以获得中点。
定义节点 current，它将指向 head，并遍历列表，直到 current 指向 mid 节点。
定义另一个节点 temp，它将指向 current 的下一个节点。
新节点将插入在 current 之后和 temp 之前，使得 current 指向新节点，新节点指向 temp。

a. display() 将显示列表中存在的所有节点。

定义一个新节点“current”，它将指向头节点。
打印 current.data 直到 current 指向 null。
在每次迭代中，current 将指向列表中的下一个节点。

程序

public class InsertMid {

    //Represent a node of the doubly linked list

    class Node{
        int data;
        Node previous;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public int size = 0;
    //Represent the head and tail of the doubly linked list
    Node head, tail = null;

    //addNode() will add a node to the list
    public void addNode(int data) {
        //Create a new node
        Node newNode = new Node(data);

        //If list is empty
        if(head == null) {
            //Both head and tail will point to newNode
            head = tail = newNode;
            //head's previous will point to null
            head.previous = null;
            //tail's next will point to null, as it is the last node of the list
            tail.next = null;
        }
        else {
            //newNode will be added after tail such that tail's next will point to newNode
            tail.next = newNode;
            //newNode's previous will point to tail
            newNode.previous = tail;
            //newNode will become new tail
            tail = newNode;
            //As it is last node, tail's next will point to null
            tail.next = null;
        }
        //Size will count the number of nodes present in the list
        size++;
    }

    //addInMid() will add a node to the middle of the list
    public void addInMid(int data) {
       //Create a new node
        Node newNode = new Node(data);

        //If list is empty
        if(head == null) {
            //Both head and tail will point to newNode
            head = tail = newNode;
            //head's previous will point to null
            head.previous = null;
            //tail's next point to null, as it is the last node of the list
            tail.next = null;
        }
        else {
            //current will point to head
            Node current = head, temp = null;

            //Store the mid position of the list
            int mid = (size % 2 == 0) ? (size/2) : ((size+1)/2);

            //Iterate through list till current points to mid position
            for(int i = 1; i < mid; i++){
                current = current.next;
            }

            //Node temp will point to node next to current
            temp = current.next;
            temp.previous = current;

            //newNode will be added between current and temp
            current.next = newNode;
            newNode.previous = current;
            newNode.next = temp;
            temp.previous = newNode;
        }
        size++;
    }

    //display() will print out the nodes of the list
    public void display() {
        //Node current will point to head
        Node current = head;
        if(head == null) {
            System.out.println("List is empty");
            return;
        }
        while(current != null) {
            //Prints each node by incrementing the pointer.

            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        InsertMid dList = new InsertMid();
        //Add nodes to the list
        dList.addNode(1);
        dList.addNode(2);

        System.out.println("Original list: ");
        dList.display();

        //Adding node '3' in the middle
        dList.addInMid(3);
        System.out.println( "Updated List: ");
        dList.display();

        //Adding node '4' in the middle
        dList.addInMid(4);
        System.out.println("Updated List: ");
        dList.display();

        //Adding node '5' in the middle
        dList.addInMid(5);
        System.out.println("Updated List: ");
        dList.display();
    }
}

输出

Original list: 
1 2 
Updated List: 
1 3 2 
Updated List: 
1 3 4 2 
Updated List: 
1 3 5 4 2

下一个主题Java 程序

Java 在双向链表中插入新节点到中间的程序

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 在双向链表中插入新节点到中间的程序

算法

程序

相关帖子

如何在 Java 中将字符串转换为 double

Java 中将零移到末尾

Java 矩阵减法程序

Java 判断给定矩阵是否为单位矩阵的程序

如何在 Java 中将 char 转换为 int

Java 从单链表中删除重复元素的程序

检查一个字符串是否是另一个字符串旋转的 Java 程序

如何在 Java 中将 int 转换为 double

Java 中的素数程序

Java 中算术级数中的缺失数字

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器