双向链表插入前端方法

Question

完成了我的硬件，我弄错了。我不懂为什么。

对于我的插入前面我做了以下。

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){ 
???????????} 

////////////////////下面是DlistNoe.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; 

点的第一个节点的“上一个”新的节点（OK）

newNode.next = head; 

点的新节点的“下一步”头（什么？）

newNode.prev = null; 

点的新节点的“上一个”空（这是第一点，所以它应该指向头）

head.prev = newnode; 

点头上的“上一页”，以空

head.next.prev = head; 

点第一个节点的分组头（你在前面，所以你不应该触及此插入）（撤消在第一个做了什么step）

所以现在你有一个头仍然指向旧的第一个元素，并且不再指向列表的最后一个元素。还有一个没有完全插入的新元素（它的“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个改变的引用已经被设置。