双向链表插入前端方法

Question

完成了我的hw，我弄错了。我不明白为什么。

对于我的插入前端，我执行以下操作。

head.next.prev = newNode; 
newNode.next = head;
newNode.prev = null;
head.prev = newnode;
head.next.prev = head; 
size++;

但相反，解决方案如下所示

head.next.prev = newNode(item, head, head.next); // newNode(item,prev,next); So basically head.next.prev is pointing to a newnode here newnode.prev = head and newnode.next = head.next. Ok that make sense. 
head.next = head.next.prev; // huh?
size++;

对我来说，解决方案

没有意义，我的解决方案是完全合乎逻辑的。如果你把head.next.prev =一个新的节点，你应该把head.next.prev =head，否则就会有一个跳跃，对吧？也 head.next = head.next.prev;没有任何意义。这条线基本上是说head.prev指向头部本身。它不应该是head.next.prev = head;？

谁能指出发生了什么？ 我知道解决方案之间的格式不同，但我对逻辑更感兴趣

完整代码如下所示

有很多困惑。所以这是如何声明头部的

 public class DList {
/**
 *  head references the sentinel node.
 *  size is the number of items in the list.  (The sentinel node does not
 *       store an item.)
 *
 *  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
 */
protected DListNode head;
protected int size;
/* DList invariants:
 *  1)  head != null.
 *  2)  For any DListNode x in a DList, x.next != null.
 *  3)  For any DListNode x in a DList, x.prev != null.
 *  4)  For any DListNode x in a DList, if x.next == y, then y.prev == x.
 *  5)  For any DListNode x in a DList, if x.prev == y, then y.next == x.
 *  6)  size is the number of DListNodes, NOT COUNTING the sentinel,
 *      that can be accessed from the sentinel (head) by a sequence of
 *      "next" references.
 */
/**
 *  newNode() calls the DListNode constructor.  Use this class to allocate
 *  new DListNodes rather than calling the DListNode constructor directly.
 *  That way, only this method needs to be overridden if a subclass of DList
 *  wants to use a different kind of node.
 *  @param item the item to store in the node.
 *  @param prev the node previous to this node.
 *  @param next the node following this node.
 */
protected DListNode newNode(Object item, DListNode prev, DListNode next) {
return new DListNode(item, prev, next);
}
/**
 *  DList() constructor for an empty DList.
 */
public DList() {
head = newNode(null, head, head);
head.next = head;
head.prev = head;
size = 0;
}

    public insertfront(Object item){
???????????}

///.java/////

//

  public class DListNode {
  /**
   *  item references the item stored in the current node.
   *  prev references the previous node in the DList.
   *  next references the next node in the DList.
   *
   *  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
   */
  public Object item;
  protected DListNode prev;
  protected DListNode next;
  /**
   *  DListNode() constructor.
   *  @param i the item to store in the node.
   *  @param p the node previous to this node.
   *  @param n the node following this node.
   */
  DListNode(Object i, DListNode p, DListNode n) {
    item = i;
    prev = p;
    next = n;
  }
}

Answer 1

您的插入代码有很多问题。只需用英文阅读：

head.next.prev = newNode; 

将第一个节点的"prev"指向新节点（确定）

newNode.next = head;

将新节点的"下一个"指向头部（什么？

newNode.prev = null;

将新节点的"prev"指向 null（它是第一个节点，所以它应该指向 head）

head.prev = newnode;

将头部的"prev"指向 null（您正在前面插入，所以您不应该触摸它）

head.next.prev = head; 

将第一个节点的上一个指向 head（撤消您在第一步中执行的操作）

所以现在你有一个头仍然指向旧的第一个元素，并且不再指向列表的最后一个元素。以及一个未完全插入的新元素（它的"prev"没有指向任何东西，它的"next"指向错误的元素）。

是的，不是真的正确，我会说。如果您阅读上述正确的解决方案，希望您会发现它更有意义。

Answer 2

链表等结构的问题在于，当你开始修改引用时，你会丢失哪些节点是哪些节点。

因此，让我们命名一些节点。

插入前的链表：

H -> A -> B -> C
H.next = A
H.prev = null
A.next = B
A.prev = H
And so on...

目标链表：

H -> N -> A -> B -> C
H.next = N
H.prev = null (unchanged)
A.next = B (unchanged)
A.prev = N
N.next = A
N.prev = H

基于 DList 不变量和给定的解决方案，有一个头节点不保存保持头部的值。

然后，让我们逐步完成您的代码：

head.next.prev = newNode; // H.next -> A, A.prev = N. This seems fine.
newNode.next = head;      // N.next = H. What? This doesn't match our goal.
newNode.prev = null;      // N.prev = null. Also doesn't match our goal.
head.prev = newnode;      // H.prev = n. Also doesn't match our goal.
head.next.prev = head;    // H.next -> A, looks like you mean this to be N, but its still A.
                          // thus A.prev = H. Also doesn't match our goal.
size++;

最后，让我们看一下给定的解决方案。

head.next.prev = newNode(item, head, head.next);
// First the function, H.next -> A, so...
// N.prev = H. Matches goal.
// N.next = A. Also matches goal.
// Then the assignment:
// head.next -> A, A.prev = N. Matches goal.    
head.next = head.next.prev;
// head.next -> A, A.prev -> N, H.next = N. Matches goal.
size++;

因此，所有 4 个更改的引用都已设置。