首页 > 代码库 > 链表总结

链表总结

链表是一种零散的线性数据结构。链表建立、插入、删除、查找、遍历等基本操作。链表的插入删除的时间复杂度为$O(1)$,而查找的时间复杂度为$O(n)$。

按照组织的方式,链表可以分为单链表,双链表,环形链表。

单链表的节点只包括数据域和一个指针域,其中指针域指向其后继节点,因此只能单向访问,不能够访问前置节点。双向链表则包括了两个指针域,分别指向其前驱和后继节点。循环链表则是双向链表的一种延伸,其最后一个节点的后继不是指向了nullptr而是指向了第一个节点。(nullptr是C++11标准中的空指针的保留字。)

一般说链表可以带头指针也可以不带头指针,但是带了头指针则会充分利用nullptr可以直接赋值的特性,使一些操作边界条件处理简化(比如删除节点为第一个节点)。nullptr的这些技巧在二叉树中也会有使用。

下面以双向带头链表为例来说明链表这一数据结构的基本操作:

首先需要定义链表的节点:

 1 template<typename T>
 2 struct node
 3 {
 4     T value;
 5     node * next;
 6     node * prev;
 7     node()
 8     {
 9         next = prev = nullptr;
10     }
11 };

这里自行定义了一个默认的构造函数,用来把新建的节点的指针域全部设置为nullptr。这样可以在后续操作时更加简洁。

(1)链表的建立

链表的建立非常简单,只需要构造出一个表即可。我这里使用了一个带头链表,因此只需返回头节点的指针即可,因为初始化在构造函数中完成了,因此这里直接返回一个new即可。

1 template<typename T>
2 node<T> * CreateList()
3 {
4     return new node<T>;
5 }

(2)链表的插入

对于链表的插入有两种处理方法:头插法和尾插法。顾名思义,头插法将新的节点插入在已知链表的第一个节点之前;而尾插法则是要保存一个末尾指针,插入时先将末尾指针所指向的节点的后继设置为新的节点,然后更新末尾指针为新的节点。在这里假设使用new运算符新建的节点具有构造函数能把所有的指针域设为nullptr,因此没有描述哪些指针需要设置为空。如果使用C语言中的malloc()函数或者没有显式给出构造函数去初始化指针域,将未使用的指针域设置为空这一点还是需要注意的。下面给出头插法和尾插法的代码:

头插法:

 

 1 template<typename T>
 2 node<T> * InsertAtHead(node<T> * list, T value)
 3 {
 4     node<T> * pnode;
 5     pnode = new node<T>;
 6     pnode->value =http://www.mamicode.com/ value;
 7     pnode->next = list->next;
 8     if (list->next != nullptr)
 9         list->next->prev = pnode;
10     pnode->prev = list;
11     list->next = pnode;
12     return pnode;
13 }

尾插法:

 

 

 1 template<typename T>
 2 node<T> * InsertAtTail(node<T> * list, T value, node<T> * tail)
 3 {
 4     node<T> * pnode;
 5     pnode = new node;
 6     pnode->next = nullptr;
 7     pnode->value =http://www.mamicode.com/ value;
 8     tail->next = pnode;
 9     return pnode;
10 }

个人更倾向于为链表的接口单独提供一个类(C不支持类,可以提供一个结构体,用来单独保存尾插法所需的tail指针。),这样使得代码更为简洁明了。(3)链表的查找

链表本质上是一个顺序表,因此查找链表只能从头或者从尾顺序查找。和数组的顺序查找较为类似,只要一个个的遍历整个表中的元素,判断其元素是否符合要求的元素。找不到则返回空指针即可。

下面给出了双向链表的查找:

 1 template<typename T>
 2 node<T> * FindNode(node<T> * list, T value)
 3 {
 4     node<T> * p;
 5     p = list->next;
 6     while (p != nullptr)
 7     {
 8         if (p->value =http://www.mamicode.com/= value)
 9             return p;
10         p = p->next;
11     }
12     return nullptr;
13 }

当然这里使用了模板的方法,要求模板的实例化后的类T具有==运算符。

至于单向链表的查找其实一样,但是如果想要利用查找的结果来进行删除操作,则务必返回前一个节点,这样查找的具体代码又会有所不同。

(4)链表节点的删除

删除节点略有麻烦,因为要涉及到前后指针域的修改。前面提及为了简化边界条件的处理,使用了带头的链表。这样只需判断该节点的后继是否为空(是不是最后一个节点)即可,如果非空则将其的前驱设置为被删除节点的前驱。如果不使用带头表,那么也需要判断一下该节点的前驱是否为空(是不是第一个节点)。当然,如果一开始构造了一个带头又带尾的表,那么两个判断都是不需要的。

代码实现如下:

1 template<typename T>
2 void DeleteNode(node<T> * lnode)
3 {
4     node<T> * pnode = lnode;
5     if (lnode->next != nullptr)
6         lnode->next->prev = lnode->prev;
7     lnode->prev->next = lnode->next;
8     delete pnode;
9 }

(5)链表的销毁

在动态数据结构中,为了避免内存泄漏,在使用结束时应当进行销毁。链表的销毁很简单,只需遍历整个表,逐个删除节点即可。删除的时候需要注意保存当前节点的后继,以免delete运算符释放掉当前节点后无法找到其下一个节点。

 1 template<typename T>
 2 void DestoryList(node<T> * list)
 3 {
 4     node<T> * tmp;
 5     while (list != nullptr)
 6     {
 7         tmp = list;
 8         list = list->next;
 9         delete tmp;
10     }
11 }

切记不能使用节点的析构函数实现递归销毁整个表,这样会导致在删除单个节点时把以该节点为头的子表也全部销毁了。

链表的用途:链表作为基本的数据结构,除了其本身插入删除非常快之外,还可以实现其他的复杂数据结构和算法,比如可以用链表实现栈和队列,可以处理哈希表的冲突,还可以用邻接表来表示图,等等。

参考:算法导论(第三版),数据结构与算法分析C语言描述(影印版),机械工业出版社。

 

链表总结