java - Java中如何实现循环链​​表？

Question

我正在开发一个项目，需要在不使用 API 的情况下实现循环相似列表。我完成了大部分代码，但由于某些原因我无法获得我正在寻找的输出。我恳请任何可以帮助我解决问题的人。一个具体问题是我无法将指针从 find 方法中找到的键开始迭代。例如如果数组元素是 10 , 9 ,8 ,5,6 。如果我将 8 作为参数传递给 find 方法，如果找到它，它应该显示为 8,5,6,10, 9 等。否则保留元素不变。

下面是我准备好的代码，请查看它下面的输出，我想这将帮助您找出我具体要寻找的内容。密切关注我的 insert、find、step 方法。预先感谢您!`

//LinkFirstLast Classs
class LinkFirstLast {
public long theData;
public LinkFirstLast next;
public LinkFirstLast last;
public LinkFirstLast previous;

public LinkFirstLast() {
}

public LinkFirstLast(int data) {
    theData =data;  
    }

    public void displayLink(){
    System.out.print(theData+ " ");
    }
    }
    // Circular linklist class//////////////////
    class CircList {

    private LinkFirstLast first, last;
    int nItems;
    //Constructor
    public CircList(){
    last = null;
    }
     //Creates a node and inserts new data
    public void insert(int data) {
    LinkFirstLast newLink = new LinkFirstLast(data);

     if(isEmpty()){
        last = newLink;
         // first = newLink;        
     }      
     else{
            first.previous = newLink;           
        }
     newLink.next = first;  
     first = newLink;    
         //last.next = first;
         // first.previous = last;          
     nItems++;
    }

    public void displayList() {
         LinkFirstLast current = first;
    while(current != null){
            current.displayLink();
            current =current.next;
                    }

    System.out.println("");

    }

    public LinkFirstLast find(int key) {
          LinkFirstLast current = first;
    while(current != null && current.theData != key){

          if(current.theData == key){
             first = current;
         first = current.next;
         last.next = first;
          } 
          else{
         current = current.next;

         }
         }

    /*
           first.previous = newLink;            

           newLink.next = first;    
            first = newLink;



    LinkFirstLast current = first;

    while(current != null && current.theData != key  )      

    {

                       current = current.next;

            }
    */
    return current;

    }

    public LinkFirstLast delete() {
    LinkFirstLast current; 
    current = first;
    while(first.next == null){
        last = null;
    }
    first = first.next;

    return current;
    }

    public int getSize() {

        return nItems;

    }

    public void step() {
    System.out.print("List: ");
    if(first != null && first.next !=null){
    first.next= first.next;

    }

}

  //Checks if linkedlist has no item
    public boolean isEmpty() {

    return (nItems==0);
    }

    public LinkFirstLast delete(int key) {
     LinkFirstLast current = first; 
    LinkFirstLast previous = first;
    while(current.theData != key)
    {
    if(current.next == null)
    return null;
    else
    {
    previous = current;
        current = current.next;

    }
    } 
    if(current == first)
    first = first.next;
    else 
    previous.next = current.next; 
    nItems--;
    return current;
    }
    // -------------------------------------------------------------
    }


    // main
    class Pro {
       public static void main(String[] args)
         {
       LinkFirstLast f, d;
         CircList theList = new CircList();  // make list

      theList.insert(10);      // insert items
      theList.insert(20);
      theList.insert(30);
      theList.insert(40);
      theList.insert(50);
      theList.insert(60);
      theList.insert(70);

      theList.displayList();              

      f = theList.find(30);               
      if( f != null){
         System.out.println("Found link with key " + f.theData);
      }
      else{
         System.out.println("Can't find link with key 30");
      }
      theList.displayList();              // display list

      System.out.println("Inserting link with key 80");
      theList.insert(80);
      theList.displayList();              // display list

      d = theList.delete(60);             // delete item
      if( d != null )
         System.out.println("Deleted link with key " + d.theData);
      else
         System.out.println("Can't delete link with key 60");
      theList.displayList();              // display list


      f = theList.find(99);               // find item
      if( f != null){
         System.out.println("Found link with key " + f.theData);}
      else
         System.out.println("Can't find link with key 99" );
      theList.displayList();              // display list

      d = theList.delete(13);             // delete item
      if( d != null )
         System.out.println("Deleted link with key " + d.theData);
      else
         System.out.println("Can't delete link with key 13");
      theList.displayList();              // display list

      System.out.println("Stepping through list");
      for(int j=0; j<theList.getSize(); j++)
        {
         theList.step();
         theList.displayList();
         }


      System.out.println("Will delete and step one by one");
      while(theList.isEmpty() == false)
         {
         theList.delete();
         theList.step();
         theList.displayList();
         }

      }  // end main()
   }  // end class CircApp

输出为:

List: 70 60 50 40 30 20 10 
Found link with key 30
List: 30 20 10 70 60 50 40 
Inserting link with key 80
List: 80 30 20 10 70 60 50 40 
Deleted link with key 60
List: 50 40 80 30 20 10 70 
Can't find link with key 99
List: 50 40 80 30 20 10 70 
Can't delete link with key 13
List: 50 40 80 30 20 10 70 
Stepping through list
List: 40 80 30 20 10 70 50 
List: 80 30 20 10 70 50 40 
List: 30 20 10 70 50 40 80 
List: 20 10 70 50 40 80 30 
List: 10 70 50 40 80 30 20 
List: 70 50 40 80 30 20 10 
List: 50 40 80 30 20 10 70 
Will delete and step one by one
List: 80 30 20 10 70 40 
List: 20 10 70 40 30 
List: 70 40 30 10 
List: 30 10 40 
List: 40 10 
List: 10 
List: 

Answer 1

您的代码存在几个问题:

1. FirstLastLinkedList 类的定义不好
2. 这些方法没有做它们应该做的事情。

3. 此外，不存在任何地方表明列表在此结束。我已经在我的代码中做到了这一点。

4. 你的输出也不一致；我相信我的程序可以更好地为您提供洞察力。我还添加了我的代码的输出。

我留下代码供您理解。如果您在理解上有任何困难，请在下面评论:-

    /**
 *
 * @author ssuman
 */

class FirstLastLinkedList{
    protected long data;
    protected FirstLastLinkedList next;
    protected FirstLastLinkedList() {
    }    
}

class CircularLinkedList {

    private FirstLastLinkedList head = null,temp = null, move = null, prev = null;
    // `temp` is used to store the last node just before the `head` node;
    protected void findInList(int userData){
        if(head==null){
            System.out.println("Can't find link with key "+ userData+"; List is empty!");
            return;
        }
        move = head;
        do{
            if(move.data == userData){
                System.out.println("Found link with key "+ userData);
                return;
            }
            move = move.next;
        }while(move != head);
        System.out.println("Can't find link with key "+ userData);
    }

    protected void deleteFromList(int userData){
        prev = move = head;
        if(head==null){
            System.out.println("Can't delete link with key "+ userData+"; List is empty!");
            return;
        }
        do{
            if(move.data == userData){
                prev = getPreviousNodeInList(move);
                head = move = move.next;
                prev.next = move;
                System.out.println("Deleted link with key "+ userData);
                displayList();
                return;
            }
            prev = move;
            move = move.next;
        }while(move != head);
        System.out.println("Can't delete link with key "+ userData);
    }

    protected FirstLastLinkedList getPreviousNodeInList(FirstLastLinkedList current){
        move = head;
        if(current == null){
            return null;
        }

        do{ 
            if(head == current){
                return temp;
            }
            if(move == current){
                return prev;
            }
            prev = move;
            move = move.next;
        }while(move != head);
        return null;
    }

    protected void insertInList(int userData){
        if(head==null){
            head = new FirstLastLinkedList();
            System.out.println("Inserting Link with key "+userData);
            head.data = userData;
            head.next = null;   
            move = head;
        }
        else{
            temp = new FirstLastLinkedList();
            System.out.println("Inserting Link with key "+userData);
            temp.data = userData;
            move.next = temp;
            move = temp;
        }
    }

    protected void endList(){
        temp.next = head;
    }

    protected void stepThroughList(){
        if(head == null){
            System.out.println("List is empty...");
            return;
        }
        FirstLastLinkedList temporary;
        System.out.println("Stepping through List :- ");
        temporary = head;
        do{
            move = temporary;
                do{          
                    System.out.print(move.next.data+"  ");  
                    move = move.next;
                }while(move != temporary);
            temporary = temporary.next;
            System.out.println("");
        }while(temporary != head);
    }

    protected void deleteInStepsFromList(){
        System.out.println("Will delete and step one by one :- ");
        prev = move = head;
        if(head==null){
            System.out.println("Can't delete links ; List is empty!");
            return;
        }
        do{
            prev = getPreviousNodeInList(move);
            head = move = move.next;
            prev.next = move;
            displayList();
        }while(move != prev);
    }

    protected void displayList(){
        move = head;
        System.out.print("List :  ");
        do{
            System.out.print(move.data+"  ");
            move = move.next;
        }while(move != head);
        System.out.println();
    }
}

public class TestCircularLinkedList{
    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        cll.insertInList(10);
        cll.insertInList(20);
        cll.insertInList(30);
        cll.insertInList(40);
        cll.insertInList(50);
        cll.insertInList(60);
        cll.insertInList(70);
        System.out.println("The List ended here...");
        cll.endList();
        cll.stepThroughList();
        cll.findInList(10);
        cll.findInList(33);
        cll.displayList();
        cll.deleteFromList(100);
        cll.deleteInStepsFromList();
    }
}

输出:-

Inserting Link with key 10
Inserting Link with key 20
Inserting Link with key 30
Inserting Link with key 40
Inserting Link with key 50
Inserting Link with key 60
Inserting Link with key 70
The List ended here...
Stepping through List :- 
20  30  40  50  60  70  10  
30  40  50  60  70  10  20  
40  50  60  70  10  20  30  
50  60  70  10  20  30  40  
60  70  10  20  30  40  50  
70  10  20  30  40  50  60  
10  20  30  40  50  60  70  
Found link with key 10
Can't find link with key 33
List :  10  20  30  40  50  60  70  
Can't delete link with key 100
Will delete and step one by one :- 
List :  20  30  40  50  60  70  
List :  30  40  50  60  70  
List :  40  50  60  70  
List :  50  60  70  
List :  60  70  
List :  70