在双向链表中搜索元素的Java程序

1 简介

在此程序中，我们需要在双向链表中搜索给定的节点。

为了解决这个问题，我们将使用节点电流遍历列表。当前指向头部并开始将搜索到的节点数据与当前节点数据进行比较。如果它们相等，则将标志设置为true并打印消息以及搜索到的节点的位置。

例如，在上面的列表中，搜索节点说4可以在位置3找到。

2 算法思路

• 定义一个Node类，该类代表列表中的一个节点。它具有三个属性：数据，前一个将指向上一个节点，下一个将指向下一个节点。
• 定义另一个用于创建双向链接列表的类，它具有两个节点：head和tail。最初，头和尾将指向null。
• addNode（）将节点添加到列表中：
  • 它首先检查head是否为空，然后将节点插入为head。
  • 头部和尾部都将指向一个新添加的节点。
  • 头的前一个指针将指向null，而尾的下一个指针将指向null。
  • 如果head不为null，则新节点将插入列表的末尾，以使新节点的前一个指针指向尾。
  • 新的节点将成为新的尾巴。尾巴的下一个指针将指向null。
• 变量i将跟踪搜索到的节点的位置。
• 变量标志将存储布尔值false。
• temp将指向头节点。
• 通过将temp增加到current.next并将i增加到i + 1来遍历循环。
• 将每个节点的数据与搜索到的节点进行比较。如果找到匹配项，则将标志设置为true。
• 如果该标志为true，则打印搜索到的节点的位置。
• 否则，打印消息“列表中不存在元素”。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class SearchList {  
  
    //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;  
        }  
    }  
  
    //searchNode() will search a given node in the list  
    public void searchNode(int value) {  
        int i = 1;  
        boolean flag = false;  
        //Node current will point to head  
        Node current = head;  
  
        //Checks whether the list is empty  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Compare value to be searched with each node in the list  
            if(current.data == value) {  
                flag = true;  
                break;  
            }  
            current = current.next;  
            i++;  
        }  
        if(flag)  
             System.out.println("Node is present in the list at the position : " + i);  
        else  
             System.out.println("Node is not present in the list");  
    }  
  
    public static void main(String[] args) {  
  
        SearchList dList = new SearchList();  
        //Add nodes to the list  
        dList.addNode(1);  
        dList.addNode(5);  
        dList.addNode(4);  
        dList.addNode(2);  
        dList.addNode(3);  
  
        //Search for node 4 in the list  
        dList.searchNode(4);  
        //Search for node 9 in the list  
        dList.searchNode(9);  
    }  
}  

输出结果为：

Node is present in the list at the position: 3
Node is not present in the list