虚拟头节点链表 [英] Dummy Head Node Linked List

问题描述

我正在尝试为圆形双向链表的字符串值编写一个插入函数.我看到创建一个虚拟节点对此很有帮助，因此我可以消除一些特殊情况，例如列表为空.问题是我在虚拟头节点上找不到很多好的信息.我了解他们的目的，但不了解如何创建/实现它.

I'm trying to write an insert function for string values for a circular doubly linked list. I saw that creating a dummy node is beneficial in doing this so I can eliminate special cases like when the list is empty. The problem is I'm not finding alot of good information on dummy head nodes. I understand their purpose, but I don't understand how I create/implement it.

感谢所有的代码示例专家，试图让我自己弄清楚，尽管有人可以看一下.

appreciate all the code examples guys, tried to figure it out on my own getting a little stuck though if someone can look at it.

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

推荐答案

对于圆形双向链表，您可以设置1个哨兵节点，当列表为空时，下一个"和上一个"都指向自身.当列表不为空时，sentinel-> next指向第一个元素，sentinel-> prev指向最后一个元素.有了这些知识，您的插入和删除功能将看起来像这样.

For a circular doubly linked list, you can setup 1 sentinel node where both "next" and "prev" points to itself when list is empty. When list is not empty, sentinel->next points to first element and sentinel->prev points to last element. With this knowledge, your insert and remove function would look something like this.

这是非常基本的，您的LinkedList和Node类可能以不同的方式实现.那没问题.最主要的是insert()和remove()函数的实现，该实现显示了前哨节点如何消除了检查NULL值的需要.

This is very basic and your LinkedList and Node class maybe implemented differently. That is OK. The main thing is the insert() and remove() function implementation that shows how sentinel node(s) removes the need for checking for NULL values.

希望这会有所帮助.

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

这篇关于虚拟头节点链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！