鏈表的頭部應該是虛擬節點嗎？

Question

我目前正在編寫一個程序，（目前爲止）利用了大約五個鏈表，並且大約有50個函數修改或以其他方式使用這些鏈表。對於如何實現頭節點我有些困惑。

執行＃1使用虛擬頭節點

如果我創建一個虛擬頭節點，該headNode從來沒有被刪除，即使沒有數據爲鏈表來表示。下面是顯示這個想法的兩種不同的可能鏈表。

Format: (object)--name_of_pointer_to_next_object--> (next object) 
(headNode)--headNode.pNext--> (Nothing/NULL) 
(headNode)--headNode.pNext--> (dataNode1)--dataNode1.pNext--> (dataNode2)--dataNode2.pNext--> (Nothing/NULL) 

這個實現的好處是，對於與鏈表的工作職能，他們不必有特殊代碼的情況下頭節點Nothing或（在C++），NULL。以下是使用此實現將節點附加到鏈接列表末尾的示例。

Public Function AppendNode(theLinkedList as NODE_, theNewNode as NODE_) 
    dim lastNode as NODE_ 

    Set lastNode = theLinkedList 

    Do While Not lastNode.pNext Is Nothing 
     Set lastNode = lastNode.pNext 
    Loop 

    Set lastNode.pNext = theNewNode 
End Function 

執行＃2 headNode可以刪除

如果我允許headNode被刪除，這會帶來問題，並增加了代碼量，我必須寫。下面是同一組數據，除了這一次頭是包含數據的合法節點。

Format: (object)--name_of_pointer_to_next_object--> (next object) 
(Nothing/NULL) 
(dataNode1)--dataNode1.pNext--> (dataNode2)--dataNode1.pNext--> (Nothing/NULL) 

這裏是相同的功能，不同的是這一次它必須提防的可能性，即頭節點是Nothing/NULL。

Public Function AppendNode(theLinkedList as NODE_, theNewNode as NODE_) 
    dim lastNode as NODE_ 

    If theLinkedList Is Nothing Then 
     Set theLinkedList = theNewNode 
    Else 
     Set lastNode = theLinkedList 

     Do While Not lastNode.pNext Is Nothing 
      Set lastNode = lastNode.pNext 
     Loop 

     Set lastNode.pNext = theNewNode 
    End If 
End Function 

很顯然，我傾向於執行＃1。每次我想使用鏈表時，它至少需要4行代碼（考慮到我會這樣做幾百次，你可以將這4行乘以300左右;例如，它可以使我無法寫1,200代碼行），也許最重要的是，它會減少我的程序的狀態量。所有可能的狀態，我的程序將只需要我尋找pNext Is Nothing，並減少國家的數量是非常讚賞在這一點上，因爲這個程序將成爲一個怪物，最終將約爲20K線相當複雜的代碼必須處理很多狀態。

我錯在認爲Implementation＃1是最好的方法嗎？我不能拿出一個理由來說明爲什麼實施＃2會更好。

Answer 1

在鏈表的開始和結尾處有一個特殊的保留節點是很常見的（雖然不是必需的）。它通常被稱爲sentinel node。另外，我建議以「約50個修改或以其他方式使用這些鏈表的函數」並將它們移動到封裝它們的類中。

你不應該有代碼看起來像這樣：

Dim theLinkedList as NODE_ 
Set theLinkedList = New NODE_ 

'bunch of work with the list 
'bunch of work with the list 
'bunch of work with the list 

Dim theNewNode as NODE_ 
Set theNewNode = New NODE_ 
Set theNewNode.Next = someDataObject 

Call AppendNode(theLinkedList, theNewNode) 

取而代之的是代碼應該只是看起來像這樣：

Dim theList As LinkedList 
Set theList = New LinkedList 

'etc 

Call theList.Append(someDataObject) 

看到區別？ LinkedList calss包裝並隱藏細節。它可以處理諸如頭部或尾部是否有哨兵節點等事情，以便項目代碼的其餘部分完全沒有意識到。