雙向鏈表插入前端方法

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個改變的引用已經被設置。