嘗試將鏈接列表轉換爲循環鏈接列表

Question

我一直在做這項任務很長一段時間。我終於讓測試人員打印列表中的內容和方法，但現在我需要連接列表中的元素，形成一個圓圈，並在刪除或添加元素時以這種方式保留它們。我的書不包括關於循環鏈表的任何內容，我試圖將我在這裏看到的幾個樣本的概念應用於循環鏈表，但沒有取得任何成功。

我會非常感謝任何幫助。

以下是我有：

import java.util.NoSuchElementException; 

/** 
A circular linked list. 
*/ 
public class LinkedList 
{ 
    private Node last; 
    // Don't add other instance fields 
    /** 
    Constructs an empty linked list. 
    */ 
    public LinkedList() 
    { 
     last = null; 
    } 

    /** 
    Returns the first element in the linked list. 
    @return the first element in the linked list 
    */ 
    public Object getFirst() 
    { 
     //. . . 
     if (last == null) 
      throw new NoSuchElementException(); 
     return last.data; 
    } 

    /** 
    Removes the first element in the linked list. 
    @return the removed element 
    */ 
    public Object removeFirst() 
    { 
     //. . . 
     if (last == null) 
      throw new NoSuchElementException(); 
     Object element = last.data; 
     last = last.next; 
     return element; 
    } 

    /** 
    Adds an element to the front of the linked list. 
    @param element the element to add 
    */ 
    public void addFirst(Object element) 
    { 
     //. . . 
     Node newNode = new Node(); 
     newNode.data = element; 
     newNode.next = last; 
     last = newNode; 
    } 

    /** 
    Adds an element to the end of the linked list. 
    @param element the element to add 
    */ 
    public void add(Object element) 
    { 
     //. . . 
     if (last == null) 
     { 
      addFirst(element); 
      //position = last;//had to comment out 
     } 
     else 
     { 
      Node newNode = new Node(); 
      newNode.data = element; 
      newNode.next = last.next; 
      last.next = newNode; 
      last = newNode; 
     } 
    } 

    /** 
    Returns an iterator for iterating through this list. 
    @return an iterator for iterating through this list 
    */ 
    public ListIterator listIterator() 
    { 
     return new LinkedListIterator(); 
    } 

    private class Node 
    { 
     public Object data; 
     public Node next; 
    } 

    private class LinkedListIterator implements ListIterator 
    {    
     private Node position; 
     private Node previous; 

     /** 
     Constructs an iterator that points to the front 
     of the linked list. 
     */ 
     public LinkedListIterator() 
     { 
      position = null; 
      previous = null; 
     } 

     /** 
     Moves the iterator past the next element. 
     @return the traversed element 
     */ 
     public Object next() 
     { 
      //. . . 
      if (!hasNext()) 
       throw new NoSuchElementException(); 
      previous = position; //remeber for remove 

      if (position == null) 
       position = last; 
      else 
       position = position.next; 

      return position.data; //correct line 
     } 

     /** 
     Tests if there is an element after the iterator 
     position. 
     @return true if there is an element after the iterator 
     position 
     */ 
     public boolean hasNext() 
     { 
      //. . . 
      if (position == null) 
       return last != null; 
      else 
       return position.next !=null; 
     } 

     /** 
     Adds an element before the iterator position 
     and moves the iterator past the inserted element. 
     @param element the element to add 
     */ 
     public void add(Object element) 
     { 
      //. . . 
      if (position == null) 
      { 
       addFirst(element); 
       position = last; 
      } 
     } 

     /** 
     Removes the last traversed element. This method may 
     only be called after a call to the next() method. 
     */ 
     public void remove() 
     { 
      //. . . 
      if (previous == position) 
       throw new IllegalStateException(); 
      if (position == last) 
      { 
       removeFirst(); 
      } 
      else 
      { 
       previous.next = position.next; 
      } 
      position = previous; 
     } 

     /** 
     Sets the last traversed element to a different 
     value. 
     @param element the element to set 
     */ 
     public void set(Object element) 
     { 
      if (position == null) 
       throw new NoSuchElementException(); 
      position.data = element; 
     } 

    } 
} 

Answer 1

下面的代碼將幫助您創建循環鏈表

class CircularLinkedList 
{ 
    class Node 
    { 
     int data; 
     Node next, prev; 

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

    private Node head; 
    private int count; 

    public Node getHead() 
    { 
     return head; 
    } 

    public int getCount() 
    { 
     return count; 
    } 

    public boolean isEmpty() 
    { 
     return head==null; 
    } 

    // Add new node after the "head" 
    public void add(int data) 
    { 
     Node n = new Node(data); 
     if(isEmpty()) 
     { 
      head = n; 
      n.next = head; 
      n.prev = head; 
     } 
     else 
     { 
      n.next = head.next; 
      n.prev = head; 
      head.next = n; 
      n.next.prev = n; 
     } 
     count++; 
    } 

    // Remove the node pointed by "head" 
    public void remove() 
    { 
     if(isEmpty()) 
      return; 

     if(count==1) 
      head = null; 
     else 
     { 
      Node tmp = head; 
      tmp.prev.next = tmp.next; 
      tmp.next.prev = tmp.prev; 
      head = head.next; 
      tmp.next = tmp.prev = null; 
     } 
     count--; 
    } 

    public void print() 
    { 
     Node tmp = head.next; 
     while(tmp!=head) 
     { 
      System.out.println(tmp.data+" "); 
      tmp = tmp.next; 
     } 
    } 
} 

上面的代碼將會給你一個想法如何創建循環鏈表，節點被添加，打印和刪除。
注意：因爲這是你的任務，所以我沒有提供給你確切的代碼。你可以使用它並以你需要的方式理解和調整它。通過這個，你將對圓形鏈表有很好的想法

如果你有任何問題。問我們。所以總是歡迎你:)