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

17 Mar 2025 | 4 分钟阅读

在本程序中，我们将创建一个单链表并在列表的中间插入一个新节点。为了完成此任务，我们将计算列表的大小，然后将其除以 2 以获取需要插入新节点的中间点。

Java Program to insert a new node at the middle of the singly linked list

请参考上图，节点 1 代表原始列表的头部。假设节点 New 是需要插入列表中间的新节点。首先，我们计算大小，在此情况下为 4。因此，为了获得中间点，我们将其除以 2 并将其存储在变量 count 中。节点 current 将指向 head。首先，我们遍历列表直到 current 指向中间位置。定义另一个节点 temp，它指向 current 后面的节点。将 New 节点插入 current 和 temp 之间。

算法

创建一个名为 Node 的类，它有两个属性：data 和 next。Next 是指向链表中下一个节点的指针。
创建另一个名为 InsertMid 的类，该类具有三个属性：head、tail 和 size，用于跟踪列表中存在的节点数量。
addNode() 将向列表添加一个新节点
- 创建一个新节点。
- 它首先检查 head 是否等于 null，这意味着列表为空。
- 如果列表为空，则 head 和 tail 都将指向新添加的节点。
- 如果列表不为空，新节点将添加到列表末尾，使得 tail 的 next 指向新添加的节点。此新节点将成为列表的新 tail。

a. addInMid() 将在新节点的中间插入一个新节点

它首先检查 head 是否等于 null，这意味着列表为空。
如果列表为空，则 head 和 tail 都将指向新添加的节点。
如果列表不为空，则计算列表的大小并将其除以 2 以获得列表的中间点。
定义节点 current，它将遍历列表，直到 current 指向中间节点。
定义另一个节点 temp，它将指向 current 的下一个节点。
新节点将插入在 current 之后和 temp 之前，使得 current 指向新节点，新节点指向 temp。

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

定义一个节点 current，它最初将指向列表的 head。
遍历列表直到 current 指向 null。
通过使 current 在每次迭代中指向它的下一个节点来显示每个节点。

程序

public class InsertMid {

    //Represent a node of the singly linked list
    class Node{
        int data;
        Node next;

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

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

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

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

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

        //Checks if the list is empty
        if(head == null) {
            //If list is empty, both head and tail would point to new node
            head = newNode;
            tail = newNode;
        }
        else {
            Node temp, current;
            //Store the mid position of the list
            int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);
            //Node temp will point to head
            temp = head;
            current = null;

            //Traverse through the list till the middle of the list is reached
            for(int i = 0; i < count; i++) {
                //Node current will point to temp
                current = temp;
                //Node temp will point to node next to it.
                temp = temp.next;
            }

            //current will point to new node
            current.next = newNode;
            //new node will point to temp
            newNode.next = temp;
        }
        size++;
    }

    //display() will display all the nodes present in 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 pointer
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        InsertMid sList = new InsertMid();

        //Adds data to the list
        sList.addNode(1);
        sList.addNode(2);

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

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

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

输出

Original list: 
1 2 
Updated List: 
1 3 2 
Updated List: 
1 3 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 从循环链表开头删除节点的程序

创建和显示循环链表的 Java 程序

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

如何在 Java 中将十进制转换为二进制

Java 对循环链表元素进行排序的程序

Automorphic Number Program in Java

Fascinating Number in Java

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

Java 罗马数字转整数

查找数组中第二小数字的 Java 程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器