虚拟头节点链表

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

对于循环双向链表，您可以设置 1 个哨兵节点，当列表为空时，"next"和"prev"都指向自身。当 list 不为空时，sentinel->next 指向第一个元素，sentinel->prev 指向最后一个元素。有了这些知识，您的插入和删除功能将如下所示。

这是非常基本的，您的 LinkedList 和 Node 类的实现方式可能不同。没关系。最主要的是insert（）和remove（）函数实现，它显示了哨兵节点如何消除检查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 2

你为什么要尝试使用虚拟节点？我希望您可以在没有虚拟节点的情况下处理它。例如：

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 3

对于没有虚拟节点的循环双链表，第一个节点的前一个指针指向最后一个节点，最后一个节点下一个指针指向第一个节点。列表本身具有指向第一个节点的头部指针，以及指向最后一个节点和/或计数的尾部指针（可选）。

对于虚拟节点，第一个节点的前一个指针指向虚拟节点

，最后一个节点下一个指针指向虚拟节点。虚拟节点指针可以指向虚拟节点本身，也可以为 null。

HP/Microsoft STL 列表函数使用虚拟节点作为列表头节点，下一个指针用作指向第一个实节点的头指针，前一个指针用作指向最后一个实节点的尾部指针。

Answer 4

#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;
}

我认为这段代码可以帮助您。当你想要实现一些数据结构时，你必须有一个清晰的蓝图。

Answer 5

在构造函数中执行以下操作

ptrHead = new Node();
listSize = 1;

如果你也有尾巴，

ptrHead->next = ptrTail;

上面的代码将创建虚拟节点。确保实现不应受到此虚拟节点的影响。

例如：

int getSize()
{
   return listSize-1;
}