Alex_McAvoy

想要成为渔夫的猎手

双链表

发表于 分类于 ， ，
本文字数： 6k 阅读时长 ≈ 5 分钟

【双链表】

双链表是在单链表的基础上在每个结点中多加入了前驱指针 prior，其指向当前结点的前驱结点

1
2
3
4
5
6
template <typename T> 
struct DNode {       //双链表结点
    T data;          //数据域
    DNode<T> *prior; //前驱指针
    DNode<T> *next;  //后继指针
};

在单链表中，在进行插入与删除时，若仅知道待操作结点，是无法取得其前驱结点的，而由于双链表引入了前驱指针，这就使得双链表在插入与删除时，当仅知道待操作结点时，能够快速得知其前驱结点

此外，对于最基本的 CRUD 操作，除非已经给出待操作结点（此时双链表插入与删除为 $O(1)$ ），否则单链表与双链表都需要从头到尾按序遍历，时间复杂度都是 $O(n)$

双链表的结构优势在于可以在 $O(1)$ 的时间内找到前驱结点，若算法需要对待操作结点的前驱结点大量处理，则双链表比单链表更有优势，但若从工程角度考量，双链表的维护性和可读性都更低

为提高维护性与可读性，双链表一般采取带头结点的实现，其实现类如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename T> 
class DoubleLinkList {
  public:
    DoubleLinkList();                              //无参构造函数，初始化表
    DoubleLinkList(T data[], int len);             //有参构造函数，链表建立
    ~DoubleLinkList();                             //析构函数，链表销毁
    int getLen();                                  //求表长
    bool empty();                                  //判空
    void print();                                  //输出
    DNode<T> *getNodeByValue(T elem);              //按值查找
    DNode<T> *getNodeByLocate(int pos);            //按位查找
    bool insertNextNode(DNode<T> *p, T elem);      //后插，用于按位插入
    bool insertPreNode(DNode<T> *p, T elem);       //前插，用于按位插入
    bool insertNode(int pos, T elem);              //按位插入
    bool deleteNodeByLocate(DNode<T> *p, T &elem); //删除指定结点p
    void headInsert(T data[], int len);            //头插法
    void tailInsert(T data[], int len);            //尾插法
  private:
    DNode<T> *first;                               //头指针
};

需要说明的是，对于单链表和双链表来说，除了两者的插入与删除操作不同外，其余操作均相同

【初始化表与销毁表】

初始化与双链表的建立

对于双链表来说，其与单链表相似，在初始化完毕后，即可对于给定的数据序列 data[] 来建立双链表，建立双链表的两种方式与单链表的类似，同样一种是头插法，另一种是尾插法

在进行初始化时，需要为头指针 first 建立一个头结点，并使头结点的前驱指针 prior 永远指向 NULL，代表无前驱；令头结点的后继指针 next 暂时指向 NULL，代表目前是空表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T>
DoubleLinkList<T>::DoubleLinkList() {             //无参构造函数，初始化
    first = (DNode<T> *)malloc(sizeof(DNode<T>)); //分配一头结点
    first->prior = NULL;                          //头结点的前驱永远指向NULL
    first->next = NULL;                           //空表
}
template <typename T>
DoubleLinkList<T>::DoubleLinkList(T data[], int len) { //有参构造函数，链表建立
    first = (DNode<T> *)malloc(sizeof(DNode<T>));      //分配一头结点
    first->prior = NULL;                               //头结点的前驱永远指向NULL
    first->next = NULL;                                //空表

    this->headInsert(data, len);                       //头插法
    // this->tailInsert(data, len);                    //尾插法
}

双链表的销毁

1
2
3
4
5
6
7
8
template <typename T>
DoubleLinkList<T>::~DoubleLinkList() { //析构函数，链表销毁
    while (first != NULL) {
        DNode<T> *p = first;           //暂存要被释放的结点
        first = first->next;           //头指针指向要被释放的结点的下一个结点
        free(p);                       //释放空间
    }
}

【基本操作】

求表长

1
2
3
4
5
6
7
8
9
10
template <typename T> 
int DoubleLinkList<T>::getLen() { //求表长
    int len = 0;
    DNode<T> *p = first;          //为保证头指针指向不变，建立临时指针变量进行枚举
    while (p->next != NULL) {     //判断下一结点是否为 NULL
        p = p->next;
        len++;
    }
    return len;
}

判空

1
2
3
4
5
6
template <typename T> 
bool DoubleLinkList<T>::empty() { //判空
    if (first->next == NULL)
        return true;
    return false;
}

输出

1
2
3
4
5
6
7
8
9
template <typename T> 
void DoubleLinkList<T>::print() { //输出
    DNode<T> *p = first->next;    //指向第1个结点
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

【查找】

按值查找

1
2
3
4
5
6
7
template <typename T>
DNode<T> *DoubleLinkList<T>::getNodeByValue(T elem) { //按值查找
    DNode<T> *p = first->next;                        //从头结点开始
    while (p != NULL && p->data != elem)
        p = p->next;
    return p;
}

按位查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename T>
DNode<T> *DoubleLinkList<T>::getNodeByLocate(int pos) { //按位查找
    if (pos < 0)                                        //越界判断
        return NULL;
    if (pos == 0)                                       //返回头结点
        return first;

    DNode<T> *p;     //扫描器，当前扫描到的工作结点
    p = first;       //扫描器从头结点开始，头结点是第0个结点
    int now_pos = 0; //累加器，记录p指向的第几个结点

    while (p != NULL && now_pos < pos) { //查找第pos个结点
        p = p->next;
        now_pos++;
    }
    return p;
}

【插入】

后插

后插，是指在给定 p 结点后插入元素 elem，一般用于按位插入，不单独使用

由于对指针的操作顺序有很多，但由于双向链表实质上可看作两条反向的单链表，所以插入操作的核心是：先处理每个方向的远端指针，再处理近端指针

原则上，插入一个结点需要连接 4 个指针，但考虑插入时的特殊情况，即在空表或表尾插入一个结点时，新结点的右指针指向为空，此时只需连接 3 个指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T>
bool DoubleLinkList<T>::insertNextNode(DNode<T> *p, T elem) { //后插，用于按位插入
    if (p == NULL)
        return false;

    DNode<T> *s = (DNode<T> *)malloc(sizeof(DNode<T>)); //申请新结点

    //对新结点s操作
    s->data = elem;         //存数据
    s->next = p->next;      //新结点s的后继指针指向p的后继
    s->prior = p;           //新结点s的前驱指针指向p

    //对工作结点p操作
    p->next = s;            //工作结点p的后继指针指向新结点

    //对新结点s的后继结点操作
    if (s->next != NULL)    //如果新结点s的后继结点存在
        s->next->prior = s; //新节点s的后继结点的前驱指针指向新结点s

    return true;
}

前插

前插与后插一样，一般用于按位插入，不单独使用

由于对指针的操作顺序有很多，但由于双向链表实质上可看作两条反向的单链表，所以插入操作的核心是：先处理每个方向的远端指针，再处理近端指针

原则上，插入一个结点需要连接 4 个指针，但考虑插入时的特殊情况，即在空表或表尾插入一个结点时，新结点的右指针指向为空，此时只需连接 3 个指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename T>
bool DoubleLinkList<T>::insertPreNode(DNode<T> *p, T elem) { //前插，用于按位插入
    if (p == NULL)
        return false;

    DNode<T> *s = (DNode<T> *)malloc(sizeof(DNode<T>)); //申请新结点

    //对新结点s操作
    s->data = elem;         //存数据
    s->prior = p->prior;    //新结点s的前驱指向p的前驱
    s->next = p;            //新结点s的后继指针指向p

    //对新结点s的前驱结点操作
    s->prior->next = s; //新节点s的前驱结点的后继指针指向新结点s

    //对工作结点p操作
    p->prior = s;            //工作结点p的后继指针指向新结点

    return true;
}

按位插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename T> 
bool DoubleLinkList<T>::insertNode(int pos, T elem) { //按位插入
    if (pos < 1)                                //越界判断
        return false;

    //后插
    DNode<T> *p = getNodeByLocate(pos - 1);     //找到第pos-1个位置
    if (p == NULL)                              //插入位置异常
        return false;
    return insertNextNode(p, elem);             //在pos-1个位置后插入元素

    //前插
    // DNode<T> *p = getNodeByLocate(pos);      //找到第pos个位置
    // if (p == NULL)                           //插入位置异常
    //     return false;
    // return insertPreNode(p, elem);           //在pos个位置前插入元素
}

【删除】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
bool DoubleLinkList<T>::deleteNodeByLocate(DNode<T> *p, T &elem) { //删除指定结点p
    if (p == NULL)
        return false;
    elem = p->data;                //存储数据
    if (p->next == NULL)           //p为表尾元素
        p->prior->next = NULL;     //p的前驱结点的后继指针指向NULL
    else {                         //p为非表尾元素
        p->next->prior = p->prior; //p的后继结点的前驱指针指向p的前驱结点
        p->prior->next = p->next;  //p的前驱结点的后继指针指向p的后继结点
    }
    free(p);
    return true;
}

【头插法与尾插法】

头插法

对于双链表的头插法，每次插入都是对头结点进行后插操作

1
2
3
4
5
template <typename T> 
void DoubleLinkList<T>::headInsert(T data[], int len) { //头插法
    for (int i = 0; i < len; i++)                       //每一次对头结点进行后插操作
        insertNextNode(first, data[i]);
}

尾插法

对于双链表的尾插法，不断地申请新结点，填充数据域，并通过尾指针 tail 来建立后继关系与前驱关系

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T> 
void DoubleLinkList<T>::tailInsert(T data[], int len) { //尾插法
    DNode<T> *tail = first;                             //尾指针
    for (int i = 0; i < len; i++) {
        DNode<T> *p = (DNode<T> *)malloc(sizeof(DNode<T>)); //申请新结点
        p->data = data[i];                                  //填充数据域
        tail->next = p;                                     //建立后继关系
        p->prior = tail;                                    //建立前驱关系
        tail = p;                                           //更改尾指针为新结点p地址
    }
    tail->next = NULL;                                      //建立完毕，尾指针指针域置空
}
感谢您对我的支持，让我继续努力分享有用的技术与知识点！