从双向链表查找最大值和最小值的Java程序

1 简介

在此程序中，我们将创建一个双向链表，然后遍历该列表以找出最小和最大节点。

我们将维护两个变量min和max。最小值将保留最小值节点，最大值将保留最大值节点。在上面的示例中，1将是最小值节点，而9将是最大值节点。

2 算法思路

• 定义一个Node类，该类代表列表中的一个节点。它具有三个属性：数据，前一个将指向上一个节点，下一个将指向下一个节点。
• 定义另一个用于创建双向链表的类，它具有两个节点：head和tail。最初，头和尾将指向null。
• minimumNode（）将打印出最小值节点：
  • 定义变量min并使用head的数据进行初始化。
  • 电流将指向头部。
  • 通过将每个节点的数据与min进行比较来遍历列表。
  • 如果min>当前数据，则min将保存当前数据。
  • 在列表的末尾，变量min将保存最小值节点。
  • 打印最小值。
• 定义变量max并使用head的数据进行初始化。
• temp将指向头部。
• 通过比较每个节点的数据与最大值来遍历列表。
• 如果max <current data，则max将保存当前数据。
• 在列表的末尾，变量max将保存最大值节点。
• 打印最大值。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class MinMax {  
  
    //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;  
        }  
    }  
  
    //MinimumNode() will find out minimum value node in the list  
    public int minimumNode() {  
        //Node current will point to head  
        Node current = head;  
        int min;  
  
        //Checks if list is empty  
        if(head == null) {  
            System.out.println("List is empty");  
            return 0;  
        }  
        else {  
            //Initially, min will store the value of head's data  
            min = head.data;  
            while(current != null) {  
                //If the value of min is greater than the current's data  
  
                //Then, replace the value of min with current node's data  
  
                if(min > current.data)  
                    min = current.data;  
                current = current.next;  
            }  
        }  
        return min;  
    }  
  
    //MaximumNode() will find out maximum value node in the list  
    public int maximumNode() {  
        //Node current will point to head  
        Node current = head;  
        int max;  
  
        //Checks if list is empty  
        if(head == null) {  
            System.out.println("List is empty");  
            return 0;  
        }  
        else {  
            //Initially, max will store the value of head's data  
            max = head.data;  
            //If value of max is lesser than current's data  
            //Then, replace value of max with current node's data  
            while(current != null) {  
                if(current.data > max)  
                    max = current.data;  
                current = current.next;  
            }  
        }  
        return max;  
    }  
  
    public static void main(String[] args) {  
  
        MinMax dList = new MinMax();  
        //Add nodes to the list  
        dList.addNode(5);  
        dList.addNode(7);  
        dList.addNode(9);  
        dList.addNode(1);  
        dList.addNode(2);  
  
        //Prints the minimum value node in the list  
        System.out.println("Minimum value node in the list: "+ dList.minimumNode());  
        //Prints the maximum value node in the list  
        System.out.println("Maximum value node in the list: "+ dList.maximumNode());  
    }  
}  

输出结果为：

Minimum value node in the list: 1
Maximum value node in the list: 9