C++实现双链表（Double Linked List）

语言这个东西不用真的会忘，我记得前前后后C++的基本语法我也看了好几遍了，一直没有动手写过什么东西，所以一遍遍的看，一遍遍的忘... ...

正好最近在看数据结构，想着自己用C++来实现一下，一方面是熟悉整个逻辑过程，加深对数据结构的理解，另一方面，也熟悉一下C++。

双链表与单链表相同，都是由结点（Node）组成，但结点结构有所不同，结点中有一个数据域和两个指针域，数据域存放结点中的数据，一个指针域指向下一个结点的地址，另一个指针指向上一个结点的地址。同单链表一样，我们所实现的双链表是带有头结点的。下图是结点和双链表结构的示意图。

结点示意图：

Node.png

双链表示意图：

Double Linked List.png

需要说明的是，我的这个程序中的索引是从0开始的，而且默认数据都是正的int类型。

双链表是从单链表中扩充出来的，除了删除结点（deleteByIndex）和增加结点（insertByIndex）以及双链表的初始化创建（create）以外很多操作和单链表是相同的，这里就不再给出实现代码了。

单链表的类定义：

class List {
private:
    class Node {
    public:
        int data;
        Node *prior;
        Node *next;
    };
    Node *head;
    int length = 0;
public:
    List();

    void print();

    void create(int n);

    int getLength() const;

    void insertByIndex(int index, int data);//在索引为index之前的位置插入数据为data的结点

    void deleteByIndex(int index);//删除索引为index的结点
};

类中的函数实现：

List::List() {
    head = new Node;
    head->data = 0;
    head->next = nullptr;
    head->prior = nullptr;
}

void List::print() {
    Node *cur = head->next;
    if (!length) {
        cout << "链表为空！" << endl;
        return;
    }
    cout << endl;
    cout << "*******************" << endl;
    cout << "链表中的元素为：" << endl;
    while (cur) {
        cout << cur->data << " ";
        cur = cur->next;
    }
    cout << endl;
    cout << "*******************" << endl;
}

void List::create(int n) {
    Node *pre = head;
    length = n;
    int i = 1;
    while (i <= n) {
        cout << "请输入第" << i << "个结点的数据：";
        Node *cur = new Node;
        cin >> cur->data;
        ++i;
        pre->next = cur;
        cur->prior = pre;
        pre = cur;
        cur->next = nullptr;
    }
}

int List::getLength() const {
    cout << "链表中的元素个数为：" << length << endl;
    return length;
}

void List::insertByIndex(int index, int data) {
    if (index < 0 || index >= length) {
        cout << "索引位置不合法" << endl;
    } else {
        Node *cur = head;
        int pos = 0;
        while (pos != index) {
            cur = cur->next;
            ++pos;
        }
        Node *temp = new Node;
        temp->data = data;
        temp->next = cur->next;
        temp->prior = cur;
        cur->next->prior = temp;
        cur->next = temp;
        ++length;
        cout << data << "插入成功！" << endl;
    }
}

void List::deleteByIndex(int index) {
    if (index < 0 || index >= length) {
        cout << "索引输入错误！" << endl;
    } else {
        Node *cur = head;
        int pos = 0;
        while (pos != index) {
            cur = cur->next;
            ++pos;
        }
        Node *temp = cur->next;
        temp->next->prior = temp->prior;
        temp->prior->next = temp->next;
        delete temp;
        --length;
        cout << "删除成功!" << endl;
    }
}

测试代码：

/*
 * Software:Jetbrains clion 2022.1
 * Created by xiaoxin_zh@foxmail.com
 * Implementing Double Linked List with C++
 */

#include <iostram>

using std::cin;
using std::cout;
using std::endl;

int main() {
    List list;
    int n;
    cout << "请输入链表中的结点的个数：";
    cin >> n;
    list.create(n);
    list.print();
    list.getLength();
    int index, data;
    cout << "请输入需要插入结点的位置索引和数值：";
    cin >> index >> data;
    list.insertByIndex(index, data);
    list.print();
    list.getLength();
    int deleteIndex;
    cout << "请输入需要删除结点的索引值：";
    cin >> deleteIndex;
    list.deleteByIndex(deleteIndex);
    list.print();
    list.getLength();
    return 0;
}

注意：一定要注意在删除和插入结点时的顺序，否则会发生“断链”！

假设实现的原始单链表有3个结点，数值分别为12、23、34结构如图所示：

create.png

在索引为2的前面插入一个数值为88的结点，其步骤如图所示：

insert.png

删除索引为1的结点，其步骤如图所示：

delete.png

测试代码执行：

EXE.png

最后编辑于：2022.05.14 20:41:37