虛擬頭節點鏈接列表

Question

我想爲圓形雙向鏈表寫入字符串值的插入函數。我看到創建一個虛擬節點對於這樣做是有益的，因此我可以消除特殊情況，例如列表爲空時。問題是我在虛擬頭節點上找不到很多好的信息。我瞭解他們的目的，但我不明白我如何創建/實施它。

欣賞所有的代碼示例傢伙，試圖找出我自己得到一點卡住，雖然如果有人可以看看它。

#include <iostream> 
#include <string> 
using namespace std; 
typedef string ListItemType; 

struct node { 
node * next; 
node * prev; 
ListItemType value; 

}; 
node * head; 
node * dummyHead = new node; 
void insert(const ListItemType input, node * & within); 

void main(){ 
    insert("bob",dummyHead); 
} 

void insert(const ListItemType input, node * &ListHead){ 
    node *newPtr = new node; 
    node *curr; 
    newPtr->value = input; 

curr = ListHead->next; //point to first node; 
while (curr != ListHead && input < curr->value){ 
    curr = curr->next; 
} 
     //insert the new node pointed to by the newPTr before 
     // the node pointed to by curr 
    newPtr->next = curr; 
    newPtr->prev = curr->prev; 
    curr->prev = newPtr; 
    newPtr->prev->next = newPtr; 
} 

Answer 1

你爲什麼試圖使用虛擬節點？ 我希望你可以在沒有虛擬節點的情況下處理它。 例如：

void AddNode(Node node) 
{ 
    if(ptrHead == NULL) 
    { 
     ptrHead = node; 
    }else 
    { 
     Node* itr = ptrHead; 
     for(int i=1; i<listSize; i++) 
     { 
      itr = itr->next; 
     } 
     itr->next = node; 
    } 
    listSize++; 
} 

上面一個是處理而不虛節點鏈表的示例。

Answer 2

執行構造

ptrHead = new Node(); 
listSize = 1; 

內以下，如果你有尾巴也

ptrHead->next = ptrTail; 

上面的代碼將創建虛擬節點。 確保您的實現不應受此虛擬節點影響。

如：

int getSize() 
{ 
    return listSize-1; 
} 

Answer 3

對於圓形雙鏈表沒有一個虛擬節點，第一個節點以前的指針指向最後一個節點，最後一個節點旁邊指針指向第一個節點。該列表本身具有指向第一個節點的頭指針和可選的指向最後節點和/或計數的尾指針。

對於虛擬節點，第一個節點先前指針指向虛擬節點，最後一個節點下一個指針指向虛擬節點。虛擬節點指針可以指向虛擬節點本身或者爲空。

HP/Microsoft STL列表函數使用虛擬節點作爲列表頭節點，下一個指針用作指向第一個真實節點的頭指針，而前一個指針用作指向最後一個實際節點的尾指針。

Answer 4

對於一個循環雙向鏈表，當列表爲空時，您可以設置1個sentinel節點，其中「next」和「prev」指向自身。當列表不爲空時，sentinel-> next指向第一個元素，sentinel-> prev指向最後一個元素。有了這些知識，你的插入和移除功能就會像這樣。

這是非常基本的，你的LinkedList和Node類可能以不同的方式實現。那沒問題。主要的是insert（）和remove（）函數實現，它顯示了sentinel節點如何刪除檢查NULL值的需求。

希望這會有所幫助。

class DoublyLinkedList 
{ 
    Node *sentinel; 
    int size = 0; 

    public DoublyLinkedList() { 
     sentinel = new Node(null); 
    } 

    // Insert to the end of the list 
    public void insert(Node *node) { 
     // being the last node, point next to sentinel 
     node->next = sentinel; 

     // previous would be whatever sentinel->prev is pointing previously 
     node->prev = sentinel->prev; 

     // setup previous node->next to point to newly inserted node 
     node->prev->next = node; 

     // sentinel previous points to new current last node 
     sentinel->prev = node; 

     size++; 
    } 

    public Node* remove(int index) { 
     if(index<0 || index>=size) throw new NoSuchElementException(); 

     Node *retval = sentinel->next; 
     while(index!=0) { 
      retval=retval->next; 
      index--; 
     } 

     retval->prev->next = retval->next; 
     retval->next->prev = retval->prev; 
     size--; 
     return retval; 
    } 
} 

class Node 
{ 
    friend class DoublyLinkedList; 
    string *value; 
    Node *next; 
    Node *prev; 

    public Node(string *value) { 
     this->value = value; 
     next = this; 
     prev = this; 
    } 

    public string* value() { return value; } 
} 

Answer 5

#include <iostream> 
#include <string> 
using namespace std; 
typedef string ElementType; 

struct Node 
{ 
    Node(){} 
    Node(ElementType element, Node* prev = NULL, Node* next = NULL):element(element){} 
    ElementType element; 
    Node* prev; 
    Node* next; 
}; 

class LinkList 
{ 
public: 
    LinkList() 
    { 
     head = tail = dummyHead = new Node("Dummy Head", NULL, NULL); 
     dummyHead->next = dummyHead; 
     dummyHead->prev = dummyHead; 

     numberOfElement = 0; 
    } 

    void insert(ElementType element) 
    { 
     Node* temp = new Node(element, NULL, NULL); 

     if (0 == numberOfElement) 
     { 
      head = tail = temp; 
      head->prev = dummyHead; 
      dummyHead->next = head; 

      tail->next = dummyHead; 
      dummyHead->prev = tail; 
     } 
     else 
     { 
      tail->next = temp; 
      temp->prev = dummyHead->next; 
      temp->next = dummyHead; 
      dummyHead->next = temp; 
      tail = temp; 
     } 

     numberOfElement += 1; 
    } 

    int length() const { return numberOfElement; } 
    bool empty() const { return head == dummyHead; } 

    friend ostream& operator<< (ostream& out, const LinkList& List); 
private: 
    Node* head; 
    Node* tail; 
    Node* dummyHead; 

    int numberOfElement; 
}; 


ostream& operator<< (ostream& out, const LinkList& List) 
{ 
    Node* current = List.head; 
    while (current != List.dummyHead) 
    { 
     out<<current->element<<" "; 
     current = current->next; 
    } 
    out<<endl; 
    return out; 
} 
int main() 
{ 
    string arr[] = {"one", "two", "three", "four", "five"}; 
    LinkList list; 
    int len = sizeof(arr)/sizeof(arr[0]); 
    for (int i = 0; i < len; ++i) 
    { 
     list.insert(arr[i]); 
    } 

    cout<<list<<endl; 
} 

我覺得這個代碼可以幫助你。當你想要實現一些數據結構時，你必須有一個清晰的藍圖。