数据结构之链表（二）：双向循环链表

马谦马谦马谦

615
文章

17
评论

2020 年 2 月 14 日 16:53:58数据结构和算法评论269字数 730阅读 2 分 26 秒阅读模式

本篇文章是基于前篇《数据结构之链表（一）：单向链表》实现的，和单向链表重复的细节不再描述。

一、双向链表

双向链表和单向链表类似，唯一的区别是链表节点中除了有指向下一个节点的指针以外，还有一个指向上一个节点的指针。

数据结构之链表（二）：双向循环链表-图片1

节点的定义：

数据结构之链表（二）：双向循环链表-图片2

template<typename T>
class list_node {
public:
    friend class doubly_linkedlist<T>;
private:
    T data;
    list_node<T> *prev; // 指向前一个节点
    list_node<T> *next; // 指向后一个节点
};

template<typename T>

class list_node {

public:

friend class doubly_linkedlist<T>;

private:

T data;

list_node<T> *prev; // 指向前一个节点

list_node<T> *next; // 指向后一个节点

};

链表的定义：

template<typename T>
class doubly_linkedlist {
public:
    doubly_linkedlist() : head(nullptr), tail(nullptr), len(0) {}
private:
    size_t len; // 链表长度
    list_node<T> *head; // 头节点
    list_node<T> *tail; // 尾结点
};

template<typename T>

class doubly_linkedlist {

public:

doubly_linkedlist() : head(nullptr), tail(nullptr), len(0) {}

private:

size_t len; // 链表长度

list_node<T> *head; // 头节点

list_node<T> *tail; // 尾结点

};

二、插入操作

双链表的插入操作和单链表基本没有差别，就只是多了一个修改 prev 节点的步骤。

以下是添加节点 node2 的过程：

数据结构之链表（二）：双向循环链表-图片3

操作主要有两步：

修改 node2 的 prev 和 next 指向，分别指向前后节点。
修改前节点 node1 的 next 指针指向 node2，修改后节点 node2 的 prev 指针指向 node2 。

插入函数实现：

/*
 * 添加节点操作
 * @new_node 新节点，不为空
 * @prev 前驱节点
 * @next 后继节点
 */
void add_node(list_node<T> *new_node, list_node<T> *prev, list_node<T> *next) {
    if (new_node == nullptr)
        return;
    
    len++;
    new_node->next = next;
    new_node->prev = prev;

    if (prev) {
        prev->next = new_node;
    }

    if (next) {
        next->prev = new_node;
    }
}

* 添加节点操作

* @new_node 新节点，不为空

* @prev 前驱节点

* @next 后继节点

void add_node(list_node<T> *new_node, list_node<T> *prev, list_node<T> *next) {

if (new_node == nullptr)

return;

len++;

new_node->next = next;

new_node->prev = prev;

if (prev) {

prev->next = new_node;

}

if (next) {

next->prev = new_node;

}

实现了这个函数之后，单链表中所有的头插、尾插函数都不用修改了，直接调用这个函数就完成了。

其实后面的删除元素也是一样，前面所说的把添加和删除逻辑抽离出来的好处就在这里。

三、删除操作

删除 node2 节点的操作步骤：

数据结构之链表（二）：双向循环链表-图片4

过程描述：

删除 node2 的 prev 和 next 指针指向。
修改 node1 的 next 指针指向 node3，修改 node3 的 prev 指针指向 node1 。

删除代码实现：

void remove_node(list_node<T> *del_node, list_node<T> *prev, list_node<T> *next) {
    len--;
    del_node->next = nullptr;
    del_node->prev = nullptr;

    if (prev) {
        prev->next = next;
    }

    if (next) {
        next->prev = prev;
    }
}