linked-list链表开始


备注

本节概述了链表是什么,以及开发人员可能想要使用它的原因。

它还应该提到链表中的任何大型主题,并链接到相关主题。由于链接列表的文档是新的,您可能需要创建这些相关主题的初始版本。

使用Sentry节点进行设计

设计链表时,可以使用sentry节点避免所有特殊情况(空列表,第一个节点,最后一个节点等)。让我们看看如何做到这一点:

struct Node
{
    Node* next;
    Node* prev;
    T data;
};

// helper function to link 2 nodes
void Link(Node* n1, Node* n2)
{
    n1->next = n2;
    n2->prev = n1;
}

// this inserts new data before 'here'
Node* Insert(Node* here, const T& data)
{
    Node* item = new Node{0,0,data};  // create new item. use T's copy-constructor
    Link(here->prev, item);           // link in new node. item comes before here,
    Link(item, here);                 // so in-between `here->prev´ and `here´
    size += 1;                        // update size
    return item;
}

// erase one item
Node* Erase(Node* here)
{
    Node* nxt = here->next;           // save next item for return value
    Link(here->prev, here->next);     // unlink item. no special cases needed when using sentry
    delete here;                      // delete item. this will call T's destructor
    size -= 1;                        // update size
    return nxt;
}
 

例如,这似乎对于空列表会失败,但是对于一个哨兵节点,列表永远不会真正为空,它总是包含哨兵节点,如果没有数据节点则连接到自身。哨兵节点也是过去最后一个标记的两倍。

Node* sentry;
void Init()
{
    sentry = (Node*)your_preferred_allocator();
    Link(sentry, sentry);
    size = 0;
}
 

可以在https://pastebin.com/DXunz58Q上找到更全面的教程

安装或设置

获取链接列表设置或安装的详细说明。