链表和双向链表？

Question

我被分配到一所大学去调整一个单链表来创建一个双链表。我在理解部分代码时遇到了问题。我遇到的问题是与我的问题相关的方法"insert(object o，int index)“：

   else {
      Node nodePointer = listHead;
      int i = 1;
      while (i < index) {
        nodePointer = nodePointer.next;
        i += 1;
        if (nodePointer == null) {
          throw new SequenceListException("Indexed Element out of Range");
        }
      }

我不明白它怎么知道行"nodePointer = nodePointer.next；“中的nodePointer.next是什么。

我看不出它在哪里定义了如何处理.next位。它怎么知道这是什么？

我确实理解它引用的是下一个节点，但不清楚这一行到底在说什么

整个代码发布在下面

class SequenceListException extends Exception {
  SequenceListException() {
    super();
  }
  SequenceListException(String s) {
    super(s);
  }
}

/**
 * <dl>
 * <dt>Purpose: Implementation of Sequence ADT.
 * <dd>
 *
 * <dt>Description:
 * <dd>This class is an implementation of the Sequence using an linked list as
 * the underlying data structure. The capacity is therefore unlimited and
 * overflow does not need to be checked.
 * </dl>
 *
 * @author Danny Alexander
 * @version $Date: 2000/01/08
 */

public class SequenceList {
  /**
   * Member class Node encapsulates the nodes of the linked list in
   * which the stack is stored. Each node contains a data item and a
   * reference to another node - the next in the linked list.
   */
  protected class Node {

    public Node(Object o) {
      this(o, null);
    }

    public Node(Object o, Node n) {
      datum = o;
      next = n;
    }

    //The Node data structure consists of two object references.
    //One for the datum contained in the node and the other for
    //the next node in the list.

    protected Object datum;
    protected Node next;
  }

  //We use object references to the head and tail of the list (the head
  //and tail of the sequence, respectively).
  private Node listHead;
  private Node listTail;

  //Only require a single constructor, which sets both object
  //references to null.
  /**
   * Constructs an empty sequence object.
   */
  public SequenceList() {
    listHead = null;
    listTail = null;
  }

  /**
   * Adds a new item at the start of the sequence.
   */
  public void insertFirst(Object o) {
    //There is a special case when the sequence is empty.
    //Then the both the head and tail pointers needs to be
    //initialised to reference the new node.
    if (listHead == null) {
      listHead = new Node(o, listHead);
      listTail = listHead;
    }

    //In the general case, we simply add a new node at the start
    //of the list via the head pointer.
    else {
      listHead = new Node(o, listHead);
    }
  }

  /**
   * Adds a new item at the end of the sequence.
   */
  public void insertLast(Object o) {
    //There is a special case when the sequence is empty.
    //Then the both the head and tail pointers needs to be
    //initialised to reference the new node.
    if (listHead == null) {
      listHead = new Node(o, listHead);
      listTail = listHead;
    }

    //In the general case, we simply add a new node to the end
    //of the list via the tail pointer.
    else {
      listTail.next = new Node(o, listTail.next);
      listTail = listTail.next;
    }
  }

  /**
   * Adds a new item at a specified position in the sequence.
   */
  public void insert(Object o, int index) throws SequenceListException {

    //Check the index is positive.
    if (index < 0) {
      throw new SequenceListException("Indexed Element out of Range");
    }

    //There is a special case when the sequence is empty.
    //Then the both the head and tail pointers needs to be
    //initialised to reference the new node.
    if (listHead == null) {
      if (index == 0) {
        listHead = new Node(o, listHead);
        listTail = listHead;
      } else {
        throw new SequenceListException("Indexed element is out of range");
      }
    }

    //There is another special case for insertion at the head of
    //the sequence.
    else if (index == 0) {
      listHead = new Node(o, listHead);
    }

    //In the general case, we need to chain down the linked list
    //from the head until we find the location for the new
    //list node. If we reach the end of the list before finding
    //the specified location, we know that the given index was out
    //of range and throw an exception.
    else {
      Node nodePointer = listHead;
      int i = 1;
      while (i < index) {
        nodePointer = nodePointer.next;
        i += 1;
        if (nodePointer == null) {
          throw new SequenceListException("Indexed Element out of Range");
        }
      }

      //Now we've found the node before the position of the
      //new one, so we 'hook in' the new Node.

      nodePointer.next = new Node(o, nodePointer.next);

      //Finally we need to check that the tail pointer is
      //correct. Another special case occurs if the new
      //node was inserted at the end, in which case, we need
      //to update the tail pointer.
      if (nodePointer == listTail) {
        listTail = listTail.next;
      }
    }
  }

  /**
   * Removes the item at the start of the sequence.
   */
  public void deleteFirst() throws SequenceListException {
    //Check there is something in the sequence to delete.
    if (listHead == null) {
      throw new SequenceListException("Sequence Underflow");
    }

    //There is a special case when there is just one item in the
    //sequence. Both pointers then need to be reset to null.
    if (listHead.next == null) {
      listHead = null;
      listTail = null;
    }

    //In the general case, we just unlink the first node of the
    //list.
    else {
      listHead = listHead.next;
    }
  }

  /**
   * Removes the item at the end of the sequence.
   */
  public void deleteLast() throws SequenceListException {
    //Check there is something in the sequence to delete.
    if (listHead == null) {
      throw new SequenceListException("Sequence Underflow");
    }

    //There is a special case when there is just one item in the
    //sequence. Both pointers then need to be reset to null.
    if (listHead.next == null) {
      listHead = null;
      listTail = null;
    }

    //In the general case, we need to chain all the way down the
    //list in order to reset the link of the second to last
    //element to null.
    else {
      Node nodePointer = listHead;
      while (nodePointer.next != listTail) {
        nodePointer = nodePointer.next;
      }

      //Unlink the last node and reset the tail pointer.
      nodePointer.next = null;
      listTail = nodePointer;
    }
  }

  /**
   * Removes the item at the specified position in the sequence.
   */
  public void delete(int index) throws SequenceListException {
    //Check there is something in the sequence to delete.
    if (listHead == null) {
      throw new SequenceListException("Sequence Underflow");
    }

    //Check the index is positive.
    if (index < 0) {
      throw new SequenceListException("Indexed Element out of Range");
    }

    //There is a special case when there is just one item in the
    //sequence. Both pointers then need to be reset to null.
    if (listHead.next == null) {
      if (index == 0) {
        listHead = null;
        listTail = null;
      } else {
        throw new SequenceListException("Indexed element is out of range.");
      }
    }

    //There is also a special case when the first element has to
    //be removed.

    else if (index == 0) {
      deleteFirst();
    }

    //In the general case, we need to chain down the list to find
    //the node in the indexed position.
    else {
      Node nodePointer = listHead;
      int i = 1;
      while (i < index) {
        nodePointer = nodePointer.next;
        i += 1;
        if (nodePointer.next == null) {
          throw new SequenceListException("Indexed Element out of Range");
        }

      }

      //Unlink the node and reset the tail pointer if that
      //node was the last one.
      if (nodePointer.next == listTail) {
        listTail = nodePointer;
      }
      nodePointer.next = nodePointer.next.next;
    }
  }

  /**
   * Returns the item at the start of the sequence.
   */
  public Object first() throws SequenceListException {
    if (listHead != null) {
      return listHead.datum;
    } else {
      throw new SequenceListException("Indexed Element out of Range");
    }
  }

  /**
   * Returns the item at the end of the sequence.
   */
  public Object last() throws SequenceListException {
    if (listTail != null) {
      return listTail.datum;
    } else {
      throw new SequenceListException("Indexed Element out of Range");
    }
  }

  /**
   * Returns the item at the specified position in the sequence.
   */
  public Object element(int index) throws SequenceListException {
    //Check the index is positive.
    if (index < 0) {
      throw new SequenceListException("Indexed Element out of Range");
    }

    //We need to chain down the list until we reach the indexed
    //position

    Node nodePointer = listHead;
    int i = 0;
    while (i < index) {
      if (nodePointer.next == null) {
        throw new SequenceListException("Indexed Element out of Range");
      } else {
        nodePointer = nodePointer.next;
        i += 1;
      }
    }

    return nodePointer.datum;
  }

  /**
   * Tests whether there are any items in the sequence.
   */
  public boolean empty() {
    return (listHead == null);
  }

  /**
   * Returns the number of items in the sequence.
   */
  public int size() {
    //Chain down the list counting the elements

    Node nodePointer = listHead;
    int size = 0;
    while (nodePointer != null) {
      size += 1;
      nodePointer = nodePointer.next;
    }
    return size;
  }

  /**
   * Empties the sequence.
   */
  public void clear() {
    listHead = null;
    listTail = null;
  }


}

Answer 1

您发布的代码列出了几种不同的方法来插入到链表中。

  protected class Node {

    public Node(Object o) {
      this(o, null);
    }

    public Node(Object o, Node n) {
      datum = o;
      next = n; // when creating a Node you have a next attribute associated with each one 
    }

如果这是一个双向链表，那么每个Node对象都会有一个与之关联的prev属性。我相信你是说你很清楚这一点。

刚开始构建链表时，默认情况下会添加两个Nodes：

public SequenceList() {
    listHead = null;
    listTail = null;
  }

    //In the general case, we simply add a new node at the start
    //of the list via the head pointer.
    else {
      listHead = new Node(o, listHead);
    }
  }

这是所需的起点，因此当调用其中一个insert方法时：

  public void insertLast(Object o) {
    //There is a special case when the sequence is empty.
    //Then the both the head and tail pointers needs to be
    //initialised to reference the new node.
    if (listHead == null) {
      listHead = new Node(o, listHead);
      listTail = listHead;
    }
    //In the general case, we simply add a new node to the end
    //of the list via the tail pointer.
    else {
      listTail.next = new Node(o, listTail.next);
      listTail = listTail.next;
    }
  }

在这里，您将向insertLast传递一个Node对象。如果这个Node在这个方法中不是Null，它将通过添加新的Node作为listTail'的下一个成员来创建一个新的尾部。然后将listTail‘s next指定为新的“尾部”。

通过这种方式，您可以跟踪head和tail。每次想要添加一个新的Node时，它就变成了新的tail。

然后，您可以通过传入head和while-loop或递归函数来遍历列表，该函数不断调用Node的next属性来引用列表中的下一项，直到您到达Null或找到您想要的内容。