单链表的结构、操作与实现代码是什么？ | 客服服务营销数智化洞察_晓观点
  1. 客服服务营销数智化洞察首页
  2. 智能化前沿
  3. 技术洞察
       

单链表的结构、操作与实现代码是什么？

研发专家-严舒畅 • • 技术洞察 • 阅读 65

链表是一种重要的数据结构，它允许我们在不需要预先定义数组大小的情况下动态地存储数据。链表中的每个元素都包含数据部分和指向下一个元素的指针。对于不重复整数的存储，单链表是一个简单而有效的选择。本文将详细介绍单链表的结构，包括其节点的定义、插入、删除和查找操作，并最后展示完整的单链表代码以及循环链表的代码示例。

一、单链表是什么？单链表的基本构成

链表元素由数据和指针构成，因此链表的节点可以由一个包含这两种元素的结构体代表：

// 单链表节点
struct SingleListNode {
    int data;
    SingleListNode* next;
    SingleListNode(int val, SingleListNode* ptr = nullptr);
};

链表包含插入、删除操作，而插入、删除又必须先查找元素是否存在，因此查找方法也必不可少。

//单链表
class SingleList {
public:
    SingleListNode* dummy;
    SingleList();
    ~SingleList();
public:
    void add(int);
    void remove(int);
    SingleListNode* find(int);
};

二、单链表插入操作

单链表的结构、操作与实现代码是什么？

例如：我们需要在伪头节点（不包含数据）和含有1的节点之间插入一个节点，发现，只需要改变dummy的指针和需要插入的指针即可。那么很容易想到下面的步骤：

  • 将dummy的指针指向要添加的节点
  • 将要添加节点的指针指向之前的下一个节点
单链表的结构、操作与实现代码是什么？单链表的结构、操作与实现代码是什么？

这样我们就添加了一个节点。

但是发现了一个问题：因为单向链表只能通过前一个的指针寻找下一个元素，如果该指针指向改变了，我们就永远也找不到下一个元素了，因此，上面步骤2是错误的。那我们应该如何添加元素？

正确的添加顺序：

  • 先将要添加的元素的指针指向dummy节点的后一个节点
  • 再将dummy节点的指针指向要添加的节点
单链表的结构、操作与实现代码是什么？单链表的结构、操作与实现代码是什么？

插入的情况讨论：

  • 插入时这里为了方便统一在dummy节点之后插入，也即每次插入一个新元素都在开头插入

图例：

初始插入2插入3
单链表的结构、操作与实现代码是什么？单链表的结构、操作与实现代码是什么？单链表的结构、操作与实现代码是什么？

插入的代码逻辑：

  • 读取find函数返回值判读元素是否已存在
  • 存在则输出插入失败，并返回
  • 不存在则执行插入操作
void SingleList::add(int val) {
    auto ptr = find(val);
    if (ptr) {
        std::cerr << val << " exists, add failed!" << std::endl;
        return;
    } else {
        auto temp = new SingleListNode(val);
        temp->next = dummy->next;
        dummy->next = temp;
    }
}

三、单链表删除操作

相比于插入，删除要简单一些：

单链表的结构、操作与实现代码是什么？

例如我们要删除上图包含2的节点，只需执行下面的步骤：

  • 将需要删除的节点的前一个节点的指针指向需要删除的节点的下一个节点，也即dummy的节点指向1
  • 再将需要删除的节点释放掉
单链表的结构、操作与实现代码是什么？单链表的结构、操作与实现代码是什么？

删除的代码逻辑：

  • 读取find函数的返回值判断元素是否存在
  • 不存在则输出错误提示并返回
  • 存在则执行删除操操作
void SingleList::remove(int val) {
    auto ptr = find(val);
    if (ptr == nullptr) {
        std::cerr << val << " does not exist, remove failed!" << std::endl;
        return;
    } else {
        auto temp = ptr->next;
        ptr->next = ptr->next->next;
        delete temp;
    }
}

四、单链表查找操作

通过对插入和删除的讨论，我们了解到，插入调用find函数时，并不需要操作其返回值，所以，返回值具体是该元素的节点还是其前面的节点并没有影响；但是，由于单链表只能通过前一个的指针寻找下一个元素，因此，删除操作时我们必须得到需要删除节点的前一个节点，因此find的返回值必须设为需要寻找的节点的前一个节点，而第一个节点的前一个节点是dummy，这也是我们需要dummy这个伪头节点的原因之一。

查找代码的逻辑：

  • 从第一个含有元素的节点开始寻找，依次向后
  • 如果找到该节点，则返回之
  • 如果链表遍历完也没有找到，就返回nullptr
SingleListNode* SingleList::find(int val) {
    auto prev = dummy;
    auto temp = dummy->next;
    while (temp) {
        if (temp->data == val)
            return prev;
        prev = prev->next;
        temp = temp->next;
    }
    return nullptr;
}

循环链表的查找

当单链表为循环链表时，最后一个元素的next指针不是指向nullptr，而是dummy节点，因此，查找代码有一些小变化，同时构造、析构以及测试代码都围绕dummy的next指针有相应的小变化（详见代码）

SingleListNode* SingleList::find(int val) {
    auto prev = dummy;
    auto temp = dummy->next;
    while (temp != dummy) {        //循环条件变为temp不等于dummy
        if (temp->data == val)
            return prev;
        prev = prev->next;
        temp = temp->next;
    }
    return nullptr;
}

五、单链表完整代码

// SingleList.h 单链表类定义

// 单链表节点
struct SingleListNode {
    int data;
    SingleListNode* next;
    SingleListNode(int val, SingleListNode* ptr = nullptr);
};

//单链表
class SingleList {
public:
    SingleListNode* dummy;
    SingleList();
    ~SingleList();
public:
    void add(int);
    void remove(int);
    SingleListNode* find(int);
};
// SingleList.cpp 单链表类的函数实现及静态成员定义
#include <iostream>
#include "SingleList.h"

SingleListNode::SingleListNode(int val, SingleListNode* ptr)
    : data(val), next(ptr) { }

SingleList::SingleList() : dummy(new SingleListNode(-1)) { }

SingleList::~SingleList() {
    auto ptr = dummy->next;
    while (ptr) {
        auto temp = ptr;
        ptr = ptr->next;
        delete temp;
        std::cout << "Element deleted!" << std::endl;
    }
    delete dummy;
    std::cout << "SingleList Destroyed!" << std::endl;
}

void SingleList::add(int val) {
    auto ptr = find(val);
    if (ptr) {
        std::cerr << val << " exists, add failed!" << std::endl;
        return;
    } else {
        auto temp = new SingleListNode(val);
        temp->next = dummy->next;
        dummy->next = temp;
    }
}

void SingleList::remove(int val) {
    auto ptr = find(val);
    if (ptr == nullptr) {
        std::cerr << val << " does not exist, remove failed!" << std::endl;
        return;
    } else {
        auto temp = ptr->next;
        ptr->next = ptr->next->next;
        delete temp;
    }
}

SingleListNode* SingleList::find(int val) {
    auto prev = dummy;
    auto temp = dummy->next;
    while (temp) {
        if (temp->data == val)
            return prev;
        prev = prev->next;
        temp = temp->next;
    }
    return nullptr;
}
// SingleListTest.cpp 对该单链表的测试代码

#include <iostream>
#include "SingleList.h"

int main(void) {
        SingleList list;

        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(4);        // 添加已存在元素
        list.remove(0); // 末尾元素
        list.remove(2); // 中间元素
        list.remove(4); // 开头元素
        list.remove(4); // 删除不存在元素
        for (auto temp = list.dummy->next; temp; temp = temp->next)
                std::cout << temp->data << " ";
        std::cout << std::endl;
        /*期望的输出
        4 exists, add failed!
        4 does not exist, remove failed!
        3 1
        Element deleted!
        Element deleted!
        SingleList Destroyed!
        */
        return 0;
}

六、循环链表的代码

链表的结构仅有查找函数有变化同时，测试的代码也有相应的变化：

// SingleList.h 单循环链表类定义

// 单循环链表节点
struct SingleListNode {
    int data;
    SingleListNode* next;
    SingleListNode(int val, SingleListNode* ptr = nullptr);
};

//单循环链表
class SingleList {
public:
    SingleListNode* dummy;
    SingleList();
    ~SingleList();
public:
    void add(int);
    void remove(int);
    SingleListNode* find(int);
};
// SingleList.cpp 单循环链表类的函数实现及静态成员定义
#include <iostream>
#include "SingleList.h"

SingleListNode::SingleListNode(int val, SingleListNode* ptr)
    : data(val), next(ptr) { }

SingleList::SingleList() 
    : dummy(new SingleListNode(-1)) { // 构造dummy时，需要把next指向本身
    dummy->next = dummy; 
}

SingleList::~SingleList() {
    auto ptr = dummy->next;
    while (ptr != dummy) { // 析构条件变为ptr != dummy
        auto temp = ptr;
        ptr = ptr->next;
        delete temp;
        std::cout << "Element deleted!" << std::endl;
    }
    delete dummy;
    std::cout << "SingleList Destroyed!" << std::endl;
}

void SingleList::add(int val) {
    auto ptr = find(val);
    if (ptr) {
        std::cerr << val << " exists, add failed!" << std::endl;
        return;
    } else {
        auto temp = new SingleListNode(val);
        temp->next = dummy->next;
        dummy->next = temp;
    }
}

void SingleList::remove(int val) {
    auto ptr = find(val);
    if (ptr == nullptr) {
        std::cerr << val << " does not exist, remove failed!" << std::endl;
        return;
    } else {
        auto temp = ptr->next;
        ptr->next = ptr->next->next;
        delete temp;
    }
}

SingleListNode* SingleList::find(int val) {
    auto prev = dummy;
    auto temp = dummy->next;
    while (temp != dummy) { //循环条件变为temp不等于dummy
        if (temp->data == val)
            return prev;
        prev = prev->next;
        temp = temp->next;
    }
    return nullptr;
}
// SingleListTest.cpp 对该单循环链表的测试代码

#include <iostream>
#include "SingleList.h"

int main(void) {
        SingleList list;

        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(4);        // 添加已存在元素
        list.remove(0); // 末尾元素
        list.remove(2); // 中间元素
        list.remove(4); // 开头元素
        list.remove(4); // 删除不存在元素
        for (auto temp = list.dummy->next; temp != list.dummy; temp = temp->next) // 循环链表循环条件为temp != list.dummy
                std::cout << temp->data << " ";
        std::cout << std::endl;
        /*期望的输出
        4 exists, add failed!
        4 does not exist, remove failed!
        3 1
        Element deleted!
        Element deleted!
        SingleList Destroyed!
        */
        return 0;
}

结语

通过对单链表和循环链表的详细介绍，我们了解了链表这种数据结构的基本构成和关键操作。单链表通过灵活的指针操作实现了元素的动态存储和访问，而循环链表则通过环形结构在某些场景下提供了更加高效的解决方案。无论是单链表还是循环链表，它们都是计算机科学中不可或缺的数据结构之一。希望本文能够帮助读者更好地理解链表的工作原理，并为后续的学习和实践提供有益的参考。

延展阅读：

客户因不满意而投诉？电商主管怎么通过实时告警迅速解决风险避免影响网店评分

大促寄件物流成本太高？商家如何快速查询菜鸟裹裹券包及福利活动

新客服培训周期长？电商客服主管怎么用AI工具让新客服快速掌握催单技巧

咨询方案 获取更多方案详情                        
赞 (0)
研发专家-严舒畅研发专家-严舒畅
上一篇 2024年10月31日 下午6:43
下一篇 2024年11月2日 上午9:43

相关推荐