数据结构：链表 gaunthan Posted on Jan 24 2017 ? C++ ? ? Data Structures ? > **链表**(Link List)是一种递归的数据结构，它或者为空(null)，或者是指向一个结点(node)的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。 ## 概述 谈到链表，最容易想到的一个例子是：寻宝。我们知道，藏宝图上面标注了一个地点。到达这个地点后，我们可能获得了宝藏，也可能只是拿到了下一个地点的藏宝图。从逻辑上说，一份份藏宝图通过标注在图上的地点串接了起来。每份藏宝图上有我们需要的地图信息。将藏宝图这一模型给形式化，便是我们的链表ADT。 链表经常用来实现其他数据结构，如背包、栈、队列。因此，一个良好设计的链表实现将使我们大大获益。基于链表实现也被称为**链式存储**实现。 在结构化存储数据集时，**链表是数组的一种重要的替代方式**。这种替代方案已有数十年的历史。事实上，编程语言历史上一块里程碑就是*McCathy*在20世纪50年代发明的*LISP语言*，而链表则是这种语言组织程序和数据的主要结构。 在现代编程语言中，安全指针、自动垃圾回收和抽象数据类型的使用使得我们可以将链表处理的代码封装在若干个类中。 ## 链表结点的定义 按照上面的描述，一个结点（对应到藏宝图），应该含有一个数据域（对应到地图或宝藏）以及一个指示域（对应到标注在图上的下一个地点）。通过指示域可以获取到该信息： - 该结点已经是最后一个结点（相当于当前藏宝图是最后一份了）； - 否则，指示域给出了下一个结点的位置（相当于地图上的标注点，可以通过它获取下一份藏宝图）。 因此，链表结点的结构可以如下定义： ```cpp template<typename T> struct ListNode { T elem; ListNode* next = nullptr; ListNode() = default; ListNode(const T& value, ListNode* nextNode = nullptr) : elem(value), next(nullptr) { } }; ``` 由于链表结点仅被链表ADT操作，因此可以将它定义在链表的内部，提高内聚性。同时为了方便操作，为结点类型定义了构造函数。 赏 Wechat Pay Alipay Application-layer Protocols 模板方法模式
