将迭代器实现到双向链接列表

时间:2022-09-05 18:55:24

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()并返回该节点。