java - 试图将链表转换为循环链表

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;
        }
    }
}

上面的代码将让您了解如何创建循环链表，添加、打印和删除节点。
注意：因为这是您的任务，所以我没有向您提供确切的代码。您可以使用它并以您需要的方式理解和调整它。这样你就会对循环链表有一个很好的了解

如果您有任何问题。问我们。所以永远欢迎你:)