数据结构-链表-第二天

2024-08-22 09:28

本文主要是介绍数据结构-链表-第二天,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

结合leetcode学习c++
链表比数组更易增加和删除数据,但访问速度更慢
在这里插入图片描述

定义

链表(linked list)是一种线性数据结构,其中的每个元素都是一个节点对象,各个节点通过“引用”相连接。
引用记录了下一个节点的内存地址,通过它可以从当前节点访问到下一个节点。

在这里插入图片描述

在这里插入图片描述

1 单向链表通常用于实现栈、队列、哈希表和图等数据结构。

栈与队列:当插入和删除操作都在链表的一端进行时,它表现的特性为先进后出,对应栈;当插入操作在链表的一端进行,删除操作在链表的另一端进行,它表现的特性为先进先出,对应队列。
哈希表:链式地址是解决哈希冲突的主流方案之一,在该方案中,所有冲突的元素都会被放到一个链表中。
图:邻接表是表示图的一种常用方式,其中图的每个顶点都与一个链表相关联,链表中的每个元素都代表与该顶点相连的其他顶点。

2 双向链表常用于需要快速查找前一个和后一个元素的场景。

高级数据结构:比如在红黑树、B 树中,我们需要访问节点的父节点,这可以通过在节点中保存一个指向父节点的引用来实现,类似于双向链表。
浏览器历史:在网页浏览器中,当用户点击前进或后退按钮时,浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
LRU 算法:在缓存淘汰(LRU)算法中,我们需要快速找到最近最少使用的数据,以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

3 环形链表常用于需要周期性操作的场景,比如操作系统的资源调度。

时间片轮转调度算法:在操作系统中,时间片轮转调度算法是一种常见的 CPU 调度算法,它需要对一组进程进行循环。每个进程被赋予一个时间片,当时间片用完时,CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
数据缓冲区:在某些数据缓冲区的实现中,也可能会使用环形链表。比如在音频、视频播放器中,数据流可能会被分成多个缓冲块并放入一个环形链表,以便实现无缝播放。

1 c++中的单链表

在 C++ 中,单链表通常是由一系列节点组成的,每个节点包含两个部分:数据部分 (val) 和指向下一个节点的指针 (next)。

单链表结构体定义

struct SinglyListNode {int val;       // 数据域,存储节点的值SinglyListNode *next; // 指针域,指向下一个节点SinglyListNode(int x) : val(x), next(NULL) {} // 构造函数,初始化节点
};

成员变量

  1. val: 用于存储节点的值。在这个例子中,val 是一个 int 类型的变量,但也可以是其他类型。
  2. next: 用于存储指向链表中下一个节点的指针。初始化为 NULL 表示这是一个新创建的节点,还没有被链接到链表中。

构造函数

  1. SinglyListNode(int x): 这是一个构造函数,用于创建新的 SinglyListNode 实例。构造函数接收一个整数参数 x 并将其赋值给 val,同时将 next 指针初始化为 NULL

构造函数的初始化列表

构造函数使用了初始化列表的形式来初始化成员变量:

SinglyListNode(int x) : val(x), next(NULL) {}

这里,val(x)next(NULL) 分别初始化 valnext 成员变量。具体来说:

  • val(x): 将构造函数传入的参数 x 赋值给成员变量 val
  • next(NULL): 将成员变量 next 初始化为 NULL,表示这个新创建的节点目前还没有指向下一个节点。

使用示例

下面是一个简单的示例,展示了如何使用 SinglyListNode 结构体创建并操作单向链表:

#include <iostream>
using namespace std;// Definition for singly-linked list.
struct SinglyListNode {int val;SinglyListNode *next;SinglyListNode(int x) : val(x), next(NULL) {}
};int main() {// 创建链表SinglyListNode *head = new SinglyListNode(1); // 创建第一个节点head->next = new SinglyListNode(2);           // 创建第二个节点并连接head->next->next = new SinglyListNode(3);     // 创建第三个节点并连接// 打印链表中的值SinglyListNode *current = head;while (current != NULL) {cout << current->val << " ";current = current->next;}// 释放内存while (head != NULL) {SinglyListNode *temp = head;head = head->next;delete temp;}return 0;
}

输出

1 2 3

创建多个节点并连接

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// 构建节点之间的引用
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

总结

单链表的定义和构造函数的设计是为了方便创建和操作链表。通过这样的设计,你可以轻松地在链表中插入、删除和查找节点,同时也能够有效地管理内存,避免内存泄漏等问题。

2 双链表

/* 双向链表节点结构体 */
struct ListNode {int val;         // 节点值ListNode *next;  // 指向后继节点的指针ListNode *prev;  // 指向前驱节点的指针ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}  // 构造函数
};

3 环形链表

环形链表(Circular Linked List)是一种特殊类型的链表,其中最后一个节点的指针不是指向 NULL,而是指向链表的头节点,形成一个闭环。这种结构使得遍历链表时可以从任何一个节点开始,并且在到达末尾节点后可以无缝地回到头节点。

环形链表(Circular Linked List)是一种特殊类型的链表,其中最后一个节点的指针不是指向 NULL,而是指向链表的头节点,形成一个闭环。这种结构使得遍历链表时可以从任何一个节点开始,并且在到达末尾节点后可以无缝地回到头节点。

环形链表的基本概念

  1. 节点: 环形链表中的每个节点包含数据和一个指向下一个节点的指针。
  2. 头节点 (Head): 链表的第一个节点,通常用来标识整个链表的开始。
  3. 尾节点 (Tail): 链表的最后一个节点,其指针指向头节点。

环形链表的类型

环形链表可以根据节点间的连接方式分为不同的类型:

  • 单向环形链表 (Singly Circular Linked List): 每个节点只包含一个指向下一个节点的指针。
  • 双向环形链表 (Doubly Circular Linked List): 每个节点包含两个指针,一个指向前一个节点,另一个指向后一个节点。

环形链表的操作

环形链表支持多种操作,包括但不限于:

  1. 插入节点:

    • 头部插入: 在链表的头部添加一个新节点。
    • 尾部插入: 在链表的尾部添加一个新节点。
    • 中间插入: 在指定位置插入一个新节点。
  2. 删除节点:

    • 删除头部节点.
    • 删除尾部节点.
    • 删除中间节点.
  3. 查找节点: 根据给定的值或索引查找对应的节点。

  4. 遍历链表: 由于链表形成闭环,可以方便地从任意节点开始遍历整个链表。

环形链表的优点

  • 方便的遍历: 无需担心遍历到最后一个节点时如何返回头节点的问题。
  • 节省空间: 对于单向环形链表,不需要额外的空间来存储尾节点的指针,因为最后一个节点直接指向头节点。

环形链表的缺点

  • 检测环形: 对于外部用户来说,需要额外的逻辑来确定链表是否已经遍历完整个环。
  • 额外的复杂性: 与普通链表相比,环形链表的插入和删除操作可能需要更多的指针更新。

示例代码

下面是一个使用 C++ 实现单向环形链表的简单示例:

#include <iostream>
using namespace std;// 定义节点结构
struct Node {int data;Node *next;Node(int x) : data(x), next(NULL) {}
};// 定义环形链表类
class CircularLinkedList {
public:Node *head;CircularLinkedList() : head(NULL) {}void append(int data) {Node *newNode = new Node(data);if (!head) {head = newNode;head->next = head;} else {Node *temp = head;while (temp->next != head) {temp = temp->next;}temp->next = newNode;newNode->next = head;}}void prepend(int data) {Node *newNode = new Node(data);if (!head) {head = newNode;head->next = head;} else {Node *temp = head;while (temp->next != head) {temp = temp->next;}newNode->next = head;head = newNode;temp->next = head;}}void deleteNode(int key) {if (!head) {return;}Node *prev = NULL;Node *cur = head;do {if (cur->data == key) {if (cur == head) {Node *temp = head;while (temp->next != head) {temp = temp->next;}head = cur->next;temp->next = head;} else {prev->next = cur->next;}delete cur;return;}prev = cur;cur = cur->next;} while (cur != head);}void printList() {if (!head) {cout << "Empty List" << endl;return;}Node *temp = head;do {cout << temp->data << " ";temp = temp->next;} while (temp != head);cout << endl;}
};int main() {CircularLinkedList cll;cll.append(1);cll.append(2);cll.prepend(0);cll.deleteNode(1);cll.printList();return 0;
}

输出

0 2

总结

环形链表是一种特殊类型的链表,它在最后的节点处闭合成一个环。这种结构在某些应用场景中非常有用,特别是当需要频繁遍历整个链表时。

这篇关于数据结构-链表-第二天的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1095878

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

Java基础回顾系列-第二天-面向对象编程

面向对象编程 Java类核心开发结构面向对象封装继承多态 抽象类abstract接口interface抽象类与接口的区别深入分析类与对象内存分析 继承extends重写(Override)与重载(Overload)重写(Override)重载(Overload)重写与重载之间的区别总结 this关键字static关键字static变量static方法static代码块 代码块String类特

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(