我被要求重新实现链表的定义方式。任务是:删除对 LinkedList 类中第一个节点的引用，以便我只跟踪列表中的最后一个元素。我还被要求将最后一个元素的 next() 引用到第一个元素，以便这个链表成为一个循环链表。有没有一种优雅的方法来做到这一点？
这是我到目前为止所拥有的:
import java.util.NoSuchElementException;
public class LinkedList
{
private Node last;
/**
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.next.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.next.data;
last.next = last.next.next;
return element;
}
/**
Adds an element to the front of the linked list.
@param element the element to add
*/
public void addFirst(Object element)
{
if( last == null ){
last = new Node();
last.data = element;
last.next = last;
}
else{
Node newNode = new Node();
newNode.data = element;
last.next = newNode;
newNode.next = last.next;
}
}
/**
Returns an iterator for iterating through this list.
@return an iterator for iterating through this list
*/
public ListIterator listIterator()
{
return new LinkedListIterator();
}
class Node
{
public Object data;
public Node next;
}
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; // Remember for remove
if (position == null)
position = last.next;
else
position = position.next;
return position.data;
}
/**
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;
}
else
{
Node newNode = new Node();
newNode.data = element;
newNode.next = position.next;
position.next = newNode;
position = newNode;
}
previous = position;
}
/**
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;
}
}
}
这是原始代码:
import java.util.NoSuchElementException;
/**
A linked list is a sequence of nodes with efficient
element insertion and removal. This class
contains a subset of the methods of the standard
java.util.LinkedList class.
*/
public class LinkedList
{
private Node first;
/**
Constructs an empty linked list.
*/
public LinkedList()
{
first = null;
}
/**
Returns the first element in the linked list.
@return the first element in the linked list
*/
public Object getFirst()
{
if (first == null)
throw new NoSuchElementException();
return first.data;
}
/**
Removes the first element in the linked list.
@return the removed element
*/
public Object removeFirst()
{
if (first == null)
throw new NoSuchElementException();
Object element = first.data;
first = first.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 = first;
first = newNode;
}
/**
Returns an iterator for iterating through this list.
@return an iterator for iterating through this list
*/
public ListIterator listIterator()
{
return new LinkedListIterator();
}
class Node
{
public Object data;
public Node next;
}
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; // Remember for remove
if (position == null)
position = first;
else
position = position.next;
return position.data;
}
/**
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 first != 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 = first;
}
else
{
Node newNode = new Node();
newNode.data = element;
newNode.next = position.next;
position.next = newNode;
position = newNode;
}
previous = position;
}
/**
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 == first)
{
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;
}
}
}
最佳答案
我认为你需要做的是将 Node 类修改为如下所示:
class Node {
// point to the previous node in the linked list
private Node prev;
private Object data;
}
现在你的链表是向后链接的，在 LinkedList 中你只需要跟踪“尾部”，你就可以沿着尾部的链接来获取链表的任何节点，对吗？
现在要使 LinkedList 成为一个圆，您需要做的就是确保链表的头节点(第一个节点)的“prev”字段始终指向您的尾部。操作方法如下:
- 当列表为空时，不执行任何操作:)
- 当第一个节点添加到列表中时，将 LinkedList 中的“tail”指向该节点，同时将该节点的“prev”指向其自身。这是因为该节点既是尾节点又是头节点，对吗？
- 当添加更多节点时，首先从“tail”开始一直沿着链接找到LinkedList中的头节点，直到找到链接到“tail”的节点。然后添加新节点，并相应地更新头/尾节点的链接。
关于java - 不知道如何实现仅最后一个节点作为引用的循环链表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12293145/