在循环链表中搜索元素的Java程序

1 简介

在此程序中，我们创建一个循环链表并在列表中搜索一个节点。

9- > 5- > 2- > 7- > 3  

考虑上面的例子。假设我们需要搜索节点5。要解决此问题，我们将遍历列表，并将每个节点与5进行比较。如果找到匹配项，则将标志设置为true，并打印出节点5的位置。在此示例中，节点5位于位置2。

2 算法思路

• 定义一个Node类，该类代表列表中的一个节点。它具有两个属性数据，下一个将指向下一个节点。
• 定义另一个用于创建循环链表的类，它具有两个节点：head和tail。
• search（）将在列表中搜索一个节点：
  • 变量i将跟踪搜索到的节点的位置。
  • 变量标志将存储布尔值false。
  • 临时节点将指向头节点。
  • 通过将临时节点增加到current.next并将i增加到i + 1来遍历循环。
  • 将每个节点的数据与搜索到的节点进行比较。如果找到匹配项，则将标志设置为true。
  • 如果flag为true，则打印搜索到的节点的位置。
  • 否则，打印消息“列表中不存在元素”。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class SearchNode {  
    //Represents the node of list.  
    public class Node{  
        int data;  
        Node next;  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    //Declaring head and tail pointer as null.  
    public Node head = null;  
    public Node tail = null;  
  
    //This function will add the new node at the end of the list.  
    public void add(int data){  
        //Create 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;  
            newNode.next = head;  
        }  
        else {  
            //tail will point to new node.  
            tail.next = newNode;  
            //New node will become new tail.  
            tail = newNode;  
            //Since, it is circular linked list tail will point to head.  
            tail.next = head;  
        }  
    }  
  
    //Searches for a node in the list  
    public void search(int element) {  
        Node current = head;  
        int i = 1;  
        boolean flag = false;  
        //Checks whether list is empty  
        if(head == null) {  
            System.out.println("List is empty");  
        }  
        else {  
             do{  
                 //Compares element to be found with each node present in the list  
                if(current.data ==  element) {  
                    flag = true;  
                    break;  
                }  
                current = current.next;  
                i++;  
            }while(current != head);  
             if(flag)  
                 System.out.println("Element is present in the list at the position : " + i);  
            else  
                 System.out.println("Element is not present in the list");  
        }  
    }  
  
    public static void main(String[] args) {  
        SearchNode cl = new SearchNode();  
        //Adds data to the list  
        cl.add(1);  
        cl.add(2);  
        cl.add(3);  
        cl.add(4);  
        //Search for node 2 in the list  
        cl.search(2);  
        //Search for node in the list  
        cl.search(7);  
    }  
}

输出结果为：

Element is present in the list at the position: 2
Element is not present in the list