【数据结构】双向链表

双链表 文章简介

本文主要涉及双向链表的设计以及一些常用接口的代码设计
编程语言：C++
reference：
学堂在线-数据结构
本文所有代码下载

链表是一类在逻辑上有顺序，但是在物理结构上没有顺序的数据结构，结点之间通过指针相互索引和访问，所需时间为O(n)

链表的优点：动态操作耗时低，只需要修改指针的指向就可以实现数据的增加删除，并且只需要常数的时间就能够实现

链表的缺点：静态操作耗时高，因为在物理结构属于无序的状态，所以不能使用寻秩访问这种时间复杂度为O(1)的方式进行数据的访问

文章目录

• 双链表
• • 文章简介
  • 1. 双链表的设计
  • • 1.1 从一个结点开始
    • 1.2 结点之间的相互连接
    • 1.3 链表的哨兵结点
    • 1.4 结点的能力
    • 1.2 双链表的构成
  • 2. 双链表常用的操作
  • • 2.1 双链表的大小与判空
    • 2.2 双链表结点查找
    • 2.3 双链表结点插入
    • 2.4 双链表遍历
    • 2.5 双链表结点删除
    • 2.6 双链表排序
    • 2.7 双链表去重
    • • 2.7.1 无序链表去重
      • 2.7.2 有序链表去重
    • 2.8 双链表清空

1. 双链表的设计

先从一个结点开始，结点是双链表的基本组成单位，一个双链表就是由一个一个的结点构成的

1.1 从一个结点开始

一个结点可以用struct进行表示，如下：

结点中数据数据解释如下：

Data：任意数据类型（var），用于表示当前结点存放的数据

pred（前驱：precursor ）：结构指针，指向当前结点的前一个结点

succ（后继：succeed）：结构指针，指向当前结点的后一个结点

1.2 结点之间的相互连接

一个一个的结点相互连接，就构成了一个双链表

此时：

• B的pred就是A，同样，A的succ就是B

• B的succ就是C，同样，C的pred就是B

但是，这样的链表结构还不是一个合格的设计，在链表的操作上容易出现边界问题，那么此时，就需要加入两个哨兵结点将双链表进行一个比较好的封装，以便后续的操作

1.3 链表的哨兵结点

在添加了两个哨兵结点之后，也就是header和trailer结点，这两个哨兵将边界的位置占领，而我们真正用来存放数据的结点处于链表的中心，不必再多花费心思在后续操作时处理边界条件。

将以上的哨兵结点再进行抽象封装，如下：

1.4 结点的能力

链表起初的功能肯定是如何插入数据

现在我们让每个结点都拥有一个能力（结构的行为，也就是函数），就是这个结点能在它的前面或者后面插入一个结点

这种能力是每个结点自身附带的，也就是定义在结点的结构内的函数

• 其中，在B的前面插入一个结点，和在A的后面插入一个结点属于等价的操作

• 同样，在B的后面插入一个结点，和在C的前面插入一个结点属于等价的操作

那么，链表常用的三种插入结点操作

1. 插入在第一个位置
2. 插入在最后一个位置
3. 插入到任意位置

全部可以同等的转化为在单个结点的前面插入或者后面插入，本质上就是这样

1. 插入在第一个位置，可以转化为在header哨兵的后面插入一个结点
2. 插入在最后一个位置，可以转化为在trailer哨兵的前面插入一个结点
3. 插入到任意位置，可以转化为在任意结点的前面或者后面插入一个结点

tips 哨兵结点本质上也是一个结点，应当具备普通结点拥有的能力

这样代码的复用性就提高了。

单个结点结构如下：

#include 
using namespace std;

template 
struct ListNode
{
    T data;		// 数据
    ListNode* pred;		// 前驱结点
    ListNode* succ;		// 后继结点
    
    ListNode () {};
    
    // 初始化列表
    ListNode (T e, ListNode *p = NULL, ListNode *s = NULL) :
    data(e), pred(p), succ(s) {};
    
    ListNode* insertAsPred(T const &e) {
        // 下文
    }
    
    ListNode* insertAsSucc(T const &e) {
        // 下文
    }
};

而双链表的单个结点的结构如上，而正是由一个一个结点构成双链表，所以下面会构造一个双链表的类，单个结点结构将会称为双链表类的成员，这里先对结点本身的前后结点进行操作。

---

在一个结点前插入一个新的结点操作如下

1. 将当前结点的pred指针指向新结点

2. 将原前驱结点的succ指针指向新结点

3. 将新结点的pred指针指向原前驱结点
4. 将新结点的succ指针指向当前结点

整理后如下：

代码如下：

template 
ListNode* ListNode::insertAsPred(T const &e) {
    
    ListNode* x = new ListNode(e, pred, this);
    
    this->pred->succ = x;
    this->pred = x;
    return x;
}

---

在一个结点后插入新结点的操作如下

1. 将当前结点的succ指针指向新结点
2. 将后驱结点的pred指针指向新结点

3. 将新节点的pred指针指向当前结点
4. 将新节点的succ指针指向原后驱结点

整理后如下：

代码如下：

template 
ListNode* ListNode::insertAsSucc(T const  &e) {
    
    ListNode* x = new ListNode(e, this, succ);
    
    this->succ->pred = x; // 顺序不能乱
    
    this->succ = x;
    return x;
}

1.2 双链表的构成

双链表代码实现如下：

#include 
// #include "ListNode.h" 将单个结点的结构包含进来
using namespace std;

template 
class List
{
private:
	
	int _size;
    
	ListNode* header;  // 头结点
	ListNode* trailer;  // 尾结点
public:
	
	void init() {
        
		this->header = new ListNode;
		this->trailer = new ListNode;
		header->succ = trailer;
		trailer->pred = header;
		header->pred = nullptr;
		trailer->succ = nullptr;
	}
};

2. 双链表常用的操作 2.1 双链表的大小与判空

1. 双链表的大小

template 
int List::Size() const {
    return _size;
}

2. 双链表是否为空

template 
bool List::Empty() const {
    if _size <= 0 {
		return true;
    } else {
		return false;
    }
}

2.2 双链表结点查找

1. 双链表首结点，返回链表的首元素，而链表的首结点就是定义的header结点的succ结点

template 
ListNode* List::First() const {
    return header->succ;
}

2. 双链表的末结点，返回链表的末结点，而链表的末结点就是定义的trailer结点的pred结点

template 
ListNode* List::Last() const {
    return trailer->pred;
}

3. 在设计查找功能的时候，需要设计两种查找方式，一种是整个链表查找，一种是范围查找，但是细细一想，整个链表的查找不就是查找范围为链表的长度吗？也就是说整个链表的查找是范围查找的子集。

这里的查找方向为从后向前查找

范围查找：

template 
ListNode* List::find(T const &e, int n, ListNode* p) const {
    ListNode* x = p;
    while ( 0 < n--) {  // 在前 n 个前驱中寻找重点
        if (e == p->data) {
            return p;  // 找到
        } else {
            p = p->pred;  // 没找到就接着找上一个元素
        }
    }
    return nullptr;  // 最终没找到返回空指针
}

全局查找：

实际上就是调用范围查找，将查找范围设置为链表的长度

template 
ListNode* List::find(T const &e) const {
    return find(e, _size, Last());
}

2.3 双链表结点插入

1. 将结点插入在首位，

因为双链表中存在哨兵结点，将新的结点插在首位实际上就是把结点插入在头结点（哨兵结点）的后一个结点

template 
ListNode* List::insertAsFirst() (T const &e) {
    _size += 1;  // 链表长度加一
    return header->insertAsSucc(e);
}

2. 将链表插入在末位

这里也一样，插入在末位实际上就是trailer结点的pred结点

template 
ListNode* List::insertAsLast (T const &e) {
    _size += 1;  // 链表长度加一
    return trailer->insertAsPred(e);
}

3. 将结点插入在链表指定结点的前面或者后面

前面：

template 
ListNode* List::insertA(ListNode* p, T const &e) {
    _size += 1;
    return p->insertAsPred(e);
}

后面：

template 
ListNode* List::insertB(ListNode* p, T const &e) {
    _size += 1;
    return p->insertAsSucc(e);
}

2.4 双链表遍历

双链表遵循按位查找，通过首节点可以逐个访问链表中的结点。

这里的访问默认为打印结点的值。

template 
void List::print() {
    ListNode* p = header->succ;
    while (p != trailer) {
        cout << p->data << " ";
        p = p->succ;
    }
    cout << endl;
}

2.5 双链表结点删除

1. 将要被删除的结点的pred 的 succ 设置为 要被删除结点的succ
2. 将要被删除的结点的succ 的 pred 设置为 要被删除结点的pred

销毁要被删除的结点，双链表的结点数量 - 1，整理如下

2.6 双链表排序

这里主要是选择排序

选择排序的思想为：

1. 将一个序列分为两个无序前缀和有序后缀两部分，并且一直保持有序后缀任意一个元素都大于无序前缀中的任何一个元素
2. 每次从无序前缀中选择最大的元素，加入到有序后缀中
3. 有序后缀不断扩展，无序前缀不断收缩，前缀为空时排序完成

总结：一条长度为n的链表中，在任何时刻，后缀(r, n)已经有序，且不小于前缀[0, r]

挑选最大的元素：

template 
ListNode* List::selectMax(ListNode *p, int n) const {
    ListNode* max = p; // 暂时将p当作最大的元素
    ListNode* cur = max->succ; // p->succ为当前元素
    while (1 < n--) {
        if (max->data <= cur->data) {  // 一旦当前元素大于 max,
            max = cur;  //  max就更新为当前元素
            cur = cur->succ;  // 当前元素继续向后挪动
        } else {
            cur = cur->succ;  // 要是不大于，也向后挪动
        }
    }
    return max;  // 返回最大元素
}

实现（局部排序）：

template 
void List::selectSort(ListNode *p, int n) {
    ListNode* head = p->pred;
    ListNode* tail = p;  // 排序的区间为 （head, tail） 左开右开区间
    for (int i = 0; i < n; i++) {
        tail = tail->succ;
    }
    while (1 < n) {
        ListNode* max = selectMax(head->succ, n);  // 找到最大的元素
        insertA(tail, remove(max));  // 将最大的元素放到有序序列第一个位置
        tail = tail->pred; // 有序序列扩展
        n--; // 无序序列范围收缩
    }
}

调用：

template 
void List::sort() {
    selectSort(First(), _size);  // 全局排序
}

2.7 双链表去重

将双链表中多余的元素删除

2.7.1 无序链表去重

思路：

将一个链表分成两个部分，前缀初始大小为0，后缀为包含整个链表

• 从后缀中取出一个结点，考察结点是否在前缀中出现过

  • 如果出现过，删除这个结点

  • 如果没有出现过，将这个结点加入前缀

• 接着考察后缀中的下一个结点

代码：

template 
int List::deduplicate() {
    if (_size < 2) {  // 长度小于2肯定不重复
        return 0;
    }
    int oldSize = _size; // 将原来的大小记录下来
    ListNode* p = header->succ; // 指向逻辑上第一个结点
    int start = 0;
    while (p != trailer) {  // 遍历整个链表
        ListNode* q = find(p->data, start, p);   // 在没有重复的序列中查找是否包含了将要加入的p结点的数值
        if (q == nullptr) {  // 如果没有在没有重复的序列中找到p
            start += 1; // 没有重复的序列范围拓展
        } else {  // 找到了重复的就将重复的移除
            remove(q);
        }
        p = p->succ;  // 继续下一个结点的查找
    }
    return oldSize - _size;  // 返回删除的元素的数量
}

2.7.2 有序链表去重

当一个双链表排序之后，相同大小的元素的元素都是紧靠着的，可以通过双指针法去重

使用两个紧靠着的指针fast和slow，分别指向相邻的结点，若二者相同，删除fast，转向下一对相邻的结点

template 
int List::uniquify() {
    if (_size < 2) return 0;
    int oldSize = _size;
    ListNode* slow = First();  // 首结点为fast
    ListNode* fast = slow->succ;  // 第二个结点为slow
    while (fast != trailer) {  // 遍历链表
        if (slow->data == fast->data) {  // 如果相同，删除fast
            remove(fast);
        } else {
            slow = fast;  // 不相同则slow向前一步
        }
        fast = fast->succ;  // fast 指向下一步
    }
    return oldSize - _size;
}

2.8 双链表清空

清空就是把除了两个哨兵以外的所有结点remove掉

template 
int List::clear() {
    int oldSize = _size;
    while (header->succ != trailer) {  // 双链表不为空
        remove(header->succ);  // 逐个将元素删除
    }
    return oldSize;  // 返回原链表的长度
}

析构函数

析构函数需要把两个哨兵也删除

template 
List::~List() {
    clear();  // 先将链表清空
    delete header;  // 删除头结点
    delete trailer;  // 删除尾结点
}