深入解析双向链表与单向链表的区别:示例详解

文章目录

  • 一、单向链表与双向链表的定义及结构
  • 二、单向链表与双向链表的区别示例
    • 插入操作
    • 删除操作
  • 三、完整示例
  • 四、总结

在这里插入图片描述


链表是一种灵活的数据结构,它通过指针连接一系列节点,实现了动态数组的特性。在众多链表类型中,单向链表和双向链表是最为常见的两种。本文将重点探讨这两种链表的区别,并通过示例进行详细说明。

一、单向链表与双向链表的定义及结构

单向链表
定义:单向链表是链表的一种,每个节点包含数据域和一个指向下一个节点的指针。

结构示例:

节点Node {
    int data; // 数据域
    Node next; // 指针域,指向下一个节点
}

双向链表
定义:双向链表是链表的一种,每个节点包含数据域、一个指向前一个节点的指针和一个指向下一个节点的指针。

结构示例:

节点Node {
    int data; // 数据域
    Node prev; // 指针域,指向前一个节点
    Node next; // 指针域,指向下一个节点
}

二、单向链表与双向链表的区别示例

插入操作

假设要在链表中的某个节点后插入一个新的节点,以下是单向链表和双向链表的插入操作示例。

单向链表插入操作:

// 假设要在节点p后插入新节点newNode
newNode.next = p.next;
p.next = newNode;

双向链表插入操作:

// 假设要在节点p后插入新节点newNode
newNode.prev = p;
newNode.next = p.next;
if (p.next != null) {
    p.next.prev = newNode;
}
p.next = newNode;

从上述示例可以看出,双向链表在插入操作时需要同时维护前驱节点和后继节点的指针,而单向链表只需维护后继节点的指针。

删除操作

假设要删除链表中的某个节点,以下是单向链表和双向链表的删除操作示例。

单向链表删除操作:

// 假设要删除节点p
if (p.prev != null) {
    p.prev.next = p.next;
}

双向链表删除操作:

// 假设要删除节点p
if (p.prev != null) {
    p.prev.next = p.next;
} else {
    // p是头节点,需要更新头节点
    head = p.next;
}
if (p.next != null) {
    p.next.prev = p.prev;
}

从上述示例可以看出,双向链表在删除操作时需要同时维护前驱节点和后继节点的指针,而单向链表只需维护前驱节点的指针。

三、完整示例

以下是双向链表的一个简单示例(C++):

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node* prev;

    Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;

    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void insertAtHead(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    void printList() const {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " <-> ";
            temp = temp->next;
        }
        std::cout << "NULL" << std::endl;
    }

    ~DoublyLinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
};

int main() {
    DoublyLinkedList list;

    list.insertAtHead(3);
    list.insertAtHead(2);
    list.insertAtHead(1);

    list.printList();

    return 0;
}

在这个示例中,我们创建了一个双向链表,并在链表头部插入新结点。注意,插入操作中需要同时更新新结点的next和prev指针,以及前一个结点的prev指针和后一个结点的next指针。

以下是单向链表的一个简单示例(C++):

#include <iostream>

struct Node {
    int data;
    Node* next;

    Node(int data) : data(data), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;

    LinkedList() : head(nullptr) {}

    void insertAtHead(int data) {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
    }

    void printList() const {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "NULL" << std::endl;
    }

    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
};

int main() {
    LinkedList list;

    list.insertAtHead(3);
    ist.insertAtHead(2);
    list.insertAtHead(1);

    list.printList();

    return 0;
}

四、总结

通过以上示例,我们可以总结出单向链表与双向链表以下几个主要区别:

  • 结构差异:双向链表每个节点有两个指针域,分别指向前一个节点和后一个节点;单向链表只有一个指针域,指向下一个节点。
  • 操作差异:双向链表在插入和删除操作时,需要同时维护前驱节点和后继节点的指针;单向链表只需维护一个方向的指针。
  • 功能差异:双向链表可以快速访问前驱节点和后继节点,适用于需要双向遍历的场景;单向链表只能单向遍历,适用于只需单向访问的场景。
  • 空间占用:双向链表由于每个节点有两个指针域,因此占用空间较大;单向链表占用空间较小。
  • 实现复杂度:双向链表实现相对复杂,需要考虑前驱节点和后继节点的指针修改;单向链表实现简单。

在实际应用中,根据具体需求和场景选择合适的链表类型,可以提高程序的性能和效率。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/797499.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue2学习笔记2-老规矩,从Hello World开始,了解Vue实例和模板

想要实现的效果&#xff1a;在页面上展示“Hello&#xff0c;World”字符串 1、准备一个【容器】div 想要把“Hello&#xff0c;World”放置在页面上&#xff0c;首先需要准备一个HTML的块级元素div&#xff0c;来承接内容。所以&#xff0c;我们先在<body>中定义<di…

Android12 MultiMedia框架之GenericSource extractor

前面两节学习到了各种Source的创建和extractor service的启动&#xff0c;本节将以本地播放为例记录下GenericSource是如何创建一个extractor的。extractor是在PrepareAsync()方法中被创建出来的&#xff0c;为了不过多赘述&#xff0c;我们直接从GenericSource的onPrepareAsyn…

《昇思25天学习打卡营第17天|K近邻算法实现红酒聚类》

K近邻算法原理介绍 K近邻算法&#xff08;K-Nearest-Neighbor, KNN&#xff09;是一种用于分类和回归的非参数统计方法&#xff0c;最初由 Cover和Hart于1968年提出是机器学习最基础的算法之一。它正是基于以上思想&#xff1a;要确定一个样本的类别&#xff0c;可以计算它与所…

springboot在线教育平台-计算机毕业设计源码68562

摘要 在数字化时代&#xff0c;随着信息技术的飞速发展&#xff0c;在线教育已成为教育领域的重要趋势。为了满足广大学习者对于灵活、高效学习方式的需求&#xff0c;基于Spring Boot的在线教育平台应运而生。Spring Boot以其快速开发、简便部署以及良好的可扩展性&#xff0c…

TypeError: Rule.__init__() got an unexpected keyword argument ‘method‘报错的解法

报错如图&#xff1a; 原代码&#xff1a; app.route(/query,method[get,post]) 解决办法很简单&#xff0c;method后加s​​​​​​​ app.route(/query,methods[get,post]) 重新执行代码&#xff0c;不报错了

C++ QT开发 学习笔记(1)

C QT开发 学习笔记(1) 考试系统 创建项目 新建Qt桌面应用程序&#xff0c;项目名&#xff1a;ExamSys。 类信息&#xff1a;类名LoginDialog继承自QDialog &#xff08;1&#xff09; ExamSys.pro 工程文件&#xff0c;包含当前工程的相关信息。 QDialog 是 Qt 框架中用…

大数据基础:Hadoop之MapReduce重点架构原理

文章目录 Hadoop之MapReduce重点架构原理 一、MapReduce概念 二、MapReduce 编程思想 2.1、Map阶段 2.2、Reduce阶段 三、MapReduce处理数据流程 四、MapReduce Shuffle 五、MapReduce注意点 六、MapReduce的三次排序 Hadoop之MapReduce重点架构原理 一、MapReduce概…

JavaScript中的面向对象编程

OPP在JavaScript的表现方式&#xff1a;原型 传统的OPP&#xff1a;类 ● 对象&#xff08;实例&#xff09;由类实例化&#xff0c;类的功能类似于蓝图&#xff0c;通过蓝图来实现建筑&#xff08;实例&#xff09; ● 行为&#xff08;方法&#xff09;从类复制到所有实例 …

【2-1:RPC设计】

RPC 1. 基础1.1 定义&特点1.2 具体实现框架1.3 应用场景2. RPC的关键技术点&一次调用rpc流程2.1 RPC流程流程两个网络模块如何连接的呢?其它特性RPC优势2.2 序列化技术序列化方式PRC如何选择序列化框架考虑因素2.3 应用层的通信协议-http2.3.1 基础概念大多数RPC大多自…

并查集——AcWing 239. 奇偶游戏

目录 并查集 定义 运用情况 注意事项 解题思路 AcWing 239. 奇偶游戏 题目描述 运行代码 代码思路 改进思路 并查集 定义 并查集&#xff08;Disjoint Set Union&#xff0c;简称DSU&#xff09;&#xff0c;是一种树形的数据结构&#xff0c;常用于处理一些不交集…

jvm 07 GC算法,内存池

01 垃圾判断算法 1.1引用计数算法 最简单的垃圾判断算法。在对象中添加一个属性用于标记对象被引用的次数&#xff0c;每多一个其他对象引用&#xff0c;计数1&#xff0c; 当引用失效时&#xff0c;计数-1&#xff0c;如果计数0&#xff0c;表示没有其他对象引用&#xff0c;…

一文详解DDL同步及其应用场景

目录 一、什么是DDL&#xff1f; 二、什么是DDL同步&#xff1f; 三、DDL同步的痛点 1、缺少自动DDL同步机制 2、缺少DDL变更监测预警 四、解决方案 五、应用场景及案例 案例一 案例二 案例三 在现代数据管理中&#xff0c;数据库的结构变更频繁且不可避免&#xff0c;特别是在…

计算机视觉之Vision Transformer图像分类

Vision Transformer&#xff08;ViT&#xff09;简介 自注意结构模型的发展&#xff0c;特别是Transformer模型的出现&#xff0c;极大推动了自然语言处理模型的发展。Transformers的计算效率和可扩展性使其能够训练具有超过100B参数的规模空前的模型。ViT是自然语言处理和计算…

卑微的LDAR第三方检测公司该如何应对政府强制使用LDAR系统

最近两年各个地方环保局和园区都再上LDAR管理系统&#xff0c;本来上系统是好事&#xff0c;监管企业和第三方检测公司规范开展检测业务&#xff0c;但是部分系统给第三方检测企业增加了大量的工作量&#xff0c;有的甚至由于系统不稳定&#xff0c;造成企业无法开展工作&#…

各种Attention|即插即用|适用于YoloV5、V7、V8、V9、V10(一)

摘要 本文总结了各种注意力&#xff0c;即插即用&#xff0c;方便大家将注意力加到自己的论文中。 SE import torch from torch import nn class SEAttention(nn.Module): """ SENet&#xff08;Squeeze-and-Excitation Networks&#xff09;中的注意力…

排序——交换排序

在上篇文章我们详细介绍了排序的概念与插入排序&#xff0c;大家可以通过下面这个链接去看&#xff1a; 排序的概念及插入排序 这篇文章就介绍一下一种排序方式&#xff1a;交换排序。 一&#xff0c;交换排序 基本思想&#xff1a;两两比较&#xff0c;如果发生逆序则交换…

Linux 下 redis 集群部署

目录 1. redis下载 2. 环境准备 3. redis部署 3.1 修改系统配置文件 3.2 开放端口 3.3 安装 redis 3.4 验证 本文将以三台服务器为例&#xff0c;介绍在 linux 系统下redis的部署方式。 1. redis下载 下载地址&#xff1a;Index of /releases/ 选择需要的介质下载&am…

【笔记】在虚拟中的主从数据库连接实体数据库成功后的从数据库不同步问题解决方法1

130是主数据库 131是从数据 数据可以说是一点没同步 解决方法; 重新设置主从连接 在虚拟机中mysql账号xiaoming&#xff08;主从数据库的桥梁账号&#xff09;登录 主数据要做的&#xff1a; show master status&#xff1b; 可以发现 这两个值发送了变化 从数据库mysql中…

探索4D毫米波雷达和摄像头在自动驾驶中的潜力

随着自动驾驶技术的快速发展&#xff0c;关于各种传感器的必要性&#xff0c;尤其是LiDAR&#xff08;激光雷达&#xff09;与毫米波雷达结合摄像头的作用&#xff0c;激发了激烈的讨论。在这篇博客中&#xff0c;我们将探讨4D毫米波雷达和摄像头的组合是否可能成为自动驾驶车辆…

一篇学通Axios

Axios 是一个基于 Promise 的 HTTP 客户端&#xff0c;用于浏览器和 node.js 环境。它提供了一种简单易用的方式来发送 HTTP 请求&#xff0c;并支持诸如请求和响应拦截、转换数据、取消请求以及自动转换 JSON 数据等功能。 Axios 名字的由来 Axios 的名字来源于希腊神话中的…