如何创建一个空的双向链表？

| 如果我有以下节点类

class Node {
 public:
Node() { next = NULL; prev = NULL; }
~Node() {}
 public :
Node *next;
Node *prev;
T data;
 };

我如何在函数中创建一个空的链表 LinkedList :: LinkedList（）我的链表类具有以下功能

 void append(T item);
T get(int idx);
void insert(int idx, T item);
void map(T (*pf)(T item));
T remove(int index);
int size();
void unshift(T item);

已邀请:

3 个回复

博沮富教全

双链列表通常会引用列表中的第一个和（有时）最后一个元素。

Node *first, *last;

在构造函数中，只需将它们设置为NULL。然后使用isEmpty方法检查这种情况，您已经完成了。

LinkedList::LinkedList()
{
    first = NULL;
    last = NULL;
}

bool LinkedList::isEmpty()
{
    return (first == NULL) && (last == NULL);
}

抬澈帅沮

我的解决方案（从标准日开始）一直是一个带有指针的NodeBase类，并从中派生为添加数据。这允许我的“ 7”对象包含 NodeBase，而不是必须管理指针分开。 NodeBase总是有一个构造函数将其链接到无处-通常，通过设置两个指针为此，例如：

struct NodeBase
{
    NodeBase* next;
    NodeBase* prec;
    NodeBase()
        : next(this)
        , prec(this)
    {
    }
    ~NodeBase()
    {
        next->prec = prec;
        prec->next = next;
    }
};

这样做意味着没有明确的列表结尾指示符（实际列表是圆形的），因此您必须跟踪自己的位置在迭代时开始，但是它进行了许多其他操作，因此容易得多。

担每棱绰

正如其他答案所表明的，有多种方法可以做到这一点。这是一个特别的信息供您参考：尽管它不是可移植的C，所以也许更适合于组装：

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

struct List {
    Node *a;
    Node *b;
    Node *c;
    List : a(tail()), b(0), c(head())
    Node *head() { return (Node *)&a; }
    Node *tail() { return (Node *)&b; }
};

因此，一个结构包含一个虚拟头节点（当然，其“ 12”指针始终为0）和一个虚拟尾节点（其“ 13”的指针始终为0），并且为了在每个列表中节省大量的“ 14”字节存储，它们相互重叠（这就是使其不可携带）。重叠不是必需的，您可以在List中放置两个Node，而不是三个Node*。这是一个有用的结构，因为它在列表中为您提供了一个“开始前”节点和一个“结束后”节点，这意味着您可以在上执行remove，insert_after和insert_before的所有操作完全不引用列表头的节点。在这方面，这就像James的通告列表，但与他不同的是，您还可以通过查找空指针来检查结尾（也无需引用头部）。在“我不需要播放的技巧”下进行归档。

要回复问题请先登录或注册

如何创建一个空的双向链表？

3 个回复

发起人

c++

linked_list

问题状态

如何创建一个空的双向链表？

与内容相关的链接

3 个回复

发起人

c++

linked_list

问题状态