需要頭節點

Question

我們說一個頭鏈表是由一個稱爲頭節點的特殊節點組成的，它標記了列表的開始，但我不明白這個頭節點的真正重要性。 請幫我嗎？

Answer 1

哨兵節點阻止你處理某些邊緣情況。

最大的是空檢查：你總是知道在列表頂部會有一個節點可以插入節點，所以你不必處理檢查head是否爲空。 （也可以幫助有類似的原因，尾節點）

考慮兩種情況：

有了頭和尾節點：

addNewDataAtHead(data): 
    newNode = new Node(data); 
    newNode.next = head.next; 
    newNode.prev = head; 
    head.next.prev = newNode; 
    head.next = newNode; 

沒有：

addNewDataAtHead(data): 
    newNode = new Node(data); 
    if (head == null): 
     head = newNode; 
    newNode.next = head; 
    head.prev = newNode; 
    head = newNode; 

的第一個的意圖更清晰，因爲它就像插入其他地方一樣。第二種情況要求您檢查特殊情況。

Answer 2

存在某種鏈接列表，您可以極大地簡化附加，插入和刪除代碼，代價是隻需少量存儲，並且在遍歷列表時只需極少的額外工作即可。

那是因爲一個空列表如下：

 +-------+ +-------+ 
head -> | dummy | -> | dummy | -> null 
null <- | head | <- | tail | <- tail 
     +-------+ +-------+ 

而是擔心是否要追加（或插入）的空單，還是你的缺失將創建一個空列表，它的簡單得多。

初始化變得稍微複雜一些，原來在左邊，按照全部右邊修改下面的代碼。這通常不會導致問題，因爲列表創建發生了一次但插入和刪除發生了很多。

def init():       def init(): 
    head = null        head = new node 
    tail = null        tail = new node 
              head->next = tail 
              head->prev = null 
              tail->prev = head 
              tail->next = null 

比較經典的追加（插入變得更爲複雜，因爲你可能需要head之前插入，在中間，或tail後）與簡化的一個：

def append (node):      def append (node): 
    node->next = null      node->next = tail 
    if head == null:      node->prev = tail->prev 
     head = node       tail->prev = node 
     tail = node 
     node->prev = null 
    else: 
     tail->next = node 
     node->prev = tail 
     tail = node 

缺失也是大大簡化了，因爲使用經典鏈接列表，有很多檢查以確保您不會取消引用空指針：

def delete (node):      def delete (node): 
    if node == head and node == tail:  if node != head and node != tail: 
     head = null        node->prev->next = node->next 
     tail = null        node->next->prev = node->prev 
    elsif node == head:       free node 
     head = head->next 
     head->prev = null 
    elsif node == tail: 
     tail = tail->prev 
     tail->next = null 
    else: 
     node->prev->next = node->next 
     node->next->prev = node->prev 
    free node 

The co德遍歷列表需要排除當然，虛擬節點，但這是一個微不足道的變化：

def traverse (head):     def traverse (head): 
    node = head        node = head->next 
    while node != null:      while node != tail: 
     do something with node     do something with node 
     node = node->next      node = node->next 

---

我自己，我不是這樣的代碼的大風扇，因爲它可能表明人們都懶得了解數據結構和算法是如何工作的。我寧願擁有更復雜的代碼，因爲它表明人們可以思考問題。無論如何，這只是你一次只寫的東西。