I have been having trouble trying to figure out how to add an iterator to this, I am really confused how to start here is the code. I imported the Iterator but I have no idea where I would begin to add it in here
我一直在努力弄清楚如何为此添加迭代器,我真的很困惑如何从这里开始是代码。我导入了迭代器,但我不知道在哪里开始添加它
public class DoublyLinkedList<E> implements Iterator <E> {
/**
* Node of a doubly linked list, which stores a reference to its
* element and to both the previous and next node in the list.
*/
private static class Node<E> {
/** The element stored at this node */
private E element; // reference to the element stored at this node
/** A reference to the preceding node in the list */
private Node<E> prev; // reference to the previous node in the list
/** A reference to the subsequent node in the list */
private Node<E> next; // reference to the subsequent node in the list
/**
* Creates a node with the given element and next node.
*
* @param e the element to be stored
* @param p reference to a node that should precede the new node
* @param n reference to a node that should follow the new node
*/
public Node(E e, Node<E> p, Node<E> n) {
element = e;
prev = p;
next = n;
}
// public accessor methods
/**
* Returns the element stored at the node.
* @return the element stored at the node
*/
public E getElement() {
return element;
}
/**
* Returns the node that precedes this one (or null if no such node).
* @return the preceding node
*/
public Node<E> getPrev() {
return prev;
}
/**
* Returns the node that follows this one (or null if no such node).
* @return the following node
*/
public Node<E> getNext() {
return next;
}
// Update methods
/**
* Sets the node's previous reference to point to Node n.
* @param p the node that should precede this one
*/
public void setPrev(Node<E> p) {
prev = p;
}
/**
* Sets the node's next reference to point to Node n.
* @param n the node that should follow this one
*/
public void setNext(Node<E> n) {
next = n;
}
}
// instance variables of the DoublyLinkedList
/** Sentinel node at the beginning of the list */
private Node<E> header; // header sentinel
/** Sentinel node at the end of the list */
private Node<E> trailer; // trailer sentinel
/** Number of elements in the list (not including sentinels) */
private int size = 0; // number of elements in the list
/** Constructs a new empty list. */
public DoublyLinkedList() {
header = new Node<>(null, null, null); // create header
trailer = new Node<>(null, header, null); // trailer is preceded by header
header.setNext(trailer); // header is followed by trailer
}
// public accessor methods
/**
* Returns the number of elements in the linked list.
* @return number of elements in the linked list
*/
public int size() {
return size;
}
/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false otherwise
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Returns (but does not remove) the first element of the list.
* @return element at the front of the list (or null if empty)
*/
public E first() {
if (isEmpty()) return null;
return header.getNext().getElement(); // first element is beyond header
}
/**
* Returns (but does not remove) the last element of the list.
* @return element at the end of the list (or null if empty)
*/
public E last() {
if (isEmpty()) return null;
return trailer.getPrev().getElement(); // last element is before trailer
}
// public update methods
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
public void addFirst(E e) {
addBetween(e, header, header.getNext()); // place just after the header
}
/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
public void addLast(E e) {
addBetween(e, trailer.getPrev(), trailer); // place just before the trailer
}
/**
* Removes and returns the first element of the list.
* @return the removed element (or null if empty)
*/
public E removeFirst() {
if (isEmpty()) return null; // nothing to remove
return remove(header.getNext()); // first element is beyond header
}
/**
* Removes and returns the last element of the list.
* @return the removed element (or null if empty)
*/
public E removeLast() {
if (isEmpty()) return null; // nothing to remove
return remove(trailer.getPrev()); // last element is before trailer
}
// private update methods
/**
* Adds an element to the linked list in between the given nodes.
* The given predecessor and successor should be neighboring each
* other prior to the call.
*
* @param predecessor node just before the location where the new element is inserted
* @param successor node just after the location where the new element is inserted
*/
private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
// create and link a new node
Node<E> newest = new Node<>(e, predecessor, successor);
predecessor.setNext(newest);
successor.setPrev(newest);
size++;
}
/**
* Removes the given node from the list and returns its element.
* @param node the node to be removed (must not be a sentinel)
*/
private E remove(Node<E> node) {
Node<E> predecessor = node.getPrev();
Node<E> successor = node.getNext();
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
return node.getElement();
}
/**
* Produces a string representation of the contents of the list.
* This exists for debugging purposes only.
*/
public String toString() {
StringBuilder sb = new StringBuilder("(");
Node<E> walk = header.getNext();
while (walk != trailer) {
sb.append(walk.getElement());
walk = walk.getNext();
if (walk != trailer)
sb.append(", ");
}
sb.append(")");
return sb.toString();
}
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return false;
}
@Override
public E next() {
// TODO Auto-generated method stub
return null;
}
} //----------- end of DoublyLinkedList class -----------
2 个解决方案
#1
First, your List should not implement the Iterator interface. Iterator is capable to traverse only once. Usually lists implement Iterable interface and have iterator() method which can create a new iterator for this list. There are several similar questions answered already. Check this for example.
首先,您的List不应实现Iterator接口。迭代器只能遍历一次。通常列表实现Iterable接口并具有iterator()方法,该方法可以为此列表创建新的迭代器。已经回答了几个类似的问题。例如,检查这个。
#2
You do not now how to implement next() and hasNext() methods? You can store a "current" node element in a field (initialized by first()), and in hasNext() method compare it with last(). In next() method you should assign current node the getNext() of it an return the node.
您现在不知道如何实现next()和hasNext()方法?您可以在字段中存储“当前”节点元素(由first()初始化),并在hasNext()方法中将其与last()进行比较。在next()方法中,您应该为当前节点分配getNext()并返回该节点。
#1
First, your List should not implement the Iterator interface. Iterator is capable to traverse only once. Usually lists implement Iterable interface and have iterator() method which can create a new iterator for this list. There are several similar questions answered already. Check this for example.
首先,您的List不应实现Iterator接口。迭代器只能遍历一次。通常列表实现Iterable接口并具有iterator()方法,该方法可以为此列表创建新的迭代器。已经回答了几个类似的问题。例如,检查这个。
#2
You do not now how to implement next() and hasNext() methods? You can store a "current" node element in a field (initialized by first()), and in hasNext() method compare it with last(). In next() method you should assign current node the getNext() of it an return the node.
您现在不知道如何实现next()和hasNext()方法?您可以在字段中存储“当前”节点元素(由first()初始化),并在hasNext()方法中将其与last()进行比较。在next()方法中,您应该为当前节点分配getNext()并返回该节点。