Java 对双向链表元素进行排序的程序

17 Mar 2025 | 4 分钟阅读

在此程序中，我们将创建一个双向链表并按升序对链表节点进行排序。

原始列表

Java program to sort the elements of the doubly linked list

已排序列表

为了实现这一点，我们维护两个指针：current 和 index。最初，current 指向 head 节点，index 指向 current 后面的节点。通过比较 current 的数据和 index 的数据，遍历链表直到 current 指向 null。如果 current 的数据大于 index 的数据，则交换它们之间的数据。在上面的示例中，current 最初指向 7，index 指向 1。因为 7 大于 1，交换数据。继续此过程，直到整个链表按升序排序。

算法

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

a. sortList() 将按升序对列表节点进行排序。

定义一个节点 current，它将指向 head。
定义另一个节点 index，它将指向 current 后面的节点。
比较 current 和 index 节点的数据。如果 current 的数据大于 index 的数据，则交换它们之间的数据。
Current 将指向 current.next，index 将指向 index.next。
继续此过程，直到整个列表排序完成。

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

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

程序

public class SortList {

    //Represent a node of the doubly linked list

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

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

    //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;
        }
    }

    //sortList() will sort the given list in ascending order
    public void sortList() {
        Node current = null, index = null;
        int temp;
        //Check whether list is empty
        if(head == null) {
            return;
        }
        else {
            //Current will point to head
            for(current = head; current.next != null; current = current.next) {
                //Index will point to node next to current
                for(index = current.next; index != null; index = index.next) {
                    //If current's data is greater than index's data, swap the data of current and index
                    if(current.data > index.data) {
                        temp = current.data;
                        current.data = index.data;
                        index.data = temp;
                    }
                }
            }
        }
    }

    //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) {

        SortList dList = new SortList();
        //Add nodes to the list
        dList.addNode(7);
        dList.addNode(1);
        dList.addNode(4);
        dList.addNode(5);
        dList.addNode(2);

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

        //Sorting list
        dList.sortList();

        //Displaying sorted list
        System.out.println("Sorted list: ");
        dList.display();
    }
}

输出

Original list: 
7 1 4 5 2 
Sorted list: 
1 2 4 5 7

下一个主题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 创建 N 个节点的循环链表并计算节点数的程序

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

Spy Number in Java

Java 判断两个字符串是否为回文的程序

ISBN Number Java

Java 分离字符串中各个字符的程序

判断两个矩阵是否相等的 Java 程序

nth Prime Number Java

在保留空格位置的情况下反转给定字符串的 Java 程序

Java 从三叉树创建双向链表的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器