TypeScript数据结构与算法系列(一) —— 链表

2024-09-07 04:52

本文主要是介绍TypeScript数据结构与算法系列(一) —— 链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

TypeScript目录

    • 链表常用操作
      • 1.初始化链表
      • 2. 插入节点
      • 3. 删除节点
      • 4. 访问节点
      • 5. 查找节点

图源:你好算法
内存空间是所有程序的公共资源,在一个复杂的系统运行环境下,空闲的内存空间可能散落在内存各处。我们知道,存储数组的内存空间必须是连续的,而当数组非常大时,内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。

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

链表的设计使得各个节点可以分散存储在内存各处,它们的内存地址无须连续。
在这里插入图片描述
观察图例,链表的组成单位是节点(node)对象。每个节点都包含两项数据:节点的“值”和指向下一节点的“引用”

链表的首个节点被称为“头节点”,最后一个节点被称为“尾节点”
尾节点指向的是“空”,它在 Java、C++ 和 Python 中分别被记为 nullnullptr None
在 C、C++、Go 和 Rust 等支持指针的语言中,上述“引用”应被替换为“指针”
如以下代码所示,链表节点 ListNode 除了包含值,还需额外保存一个引用(指针)。因此在相同数据量下,链表比数组占用更多的内存空间

/* 链表节点类 */
class ListNode {val: number;next: ListNode | null;constructor(val?: number, next?: ListNode | null) {this.val = val === undefined ? 0 : val;        // 节点值this.next = next === undefined ? null : next;  // 指向下一节点的引用}
}

链表常用操作

1.初始化链表

建立链表分为两步,第一步是初始化各个节点对象,第二步是构建节点之间的引用关系。初始化完成后,我们就可以从链表的头节点出发,通过引用指向 next 依次访问所有节点。

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

数组整体是一个变量,比如数组nums包含元素nums[0]nums[1] 等,而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称,比如以上代码中的链表可记作链表 n0

2. 插入节点

在链表中插入节点非常容易。如图例所示,假设我们想在相邻的两个节点n0n1 之间插入一个新节点 P ,则只需改变两个节点引用(指针)即可,时间复杂度为 O(1)
相比之下,在数组中插入元素的时间复杂度为O(n) ,在大数据量下的效率较低。
在这里插入图片描述

/* 在链表的节点 n0 之后插入节点 P */
function insert(n0: ListNode, P: ListNode): void {const n1 = n0.next;P.next = n1;n0.next = P;
}

3. 删除节点

如图 4-7 所示,在链表中删除节点也非常方便,只需改变一个节点的引用(指针)即可。

请注意,尽管在删除操作完成后节点 P 仍然指向 n1 ,但实际上遍历此链表已经无法访问到 P ,这意味着 P 已经不再属于该链表了。
在这里插入图片描述

/* 删除链表的节点 n0 之后的首个节点 */
function remove(n0: ListNode): void {if (!n0.next) {return;}// n0 -> P -> n1const P = n0.next;const n1 = P.next;n0.next = n1;
}

4. 访问节点

在链表中访问节点的效率较低。如上一节所述,我们可以在O(1)时间下访问数组中的任意元素。链表则不然,程序需要从头节点出发,逐个向后遍历,直至找到目标节点。也就是说,访问链表的第i个节点需要循环 i-1轮,时间复杂度为 O(n)。

/* 访问链表中索引为 index 的节点 */
function access(head: ListNode | null, index: number): ListNode | null {for (let i = 0; i < index; i++) {if (!head) {return null;}head = head.next;}return head;
}

5. 查找节点

遍历链表,查找其中值为 target的节点,输出该节点在链表中的索引。此过程也属于线性查找。代码如下所示:

/* 在链表中查找值为 target 的首个节点 */
function find(head: ListNode | null, target: number): number {let index = 0;while (head !== null) {if (head.val === target) {return index;}head = head.next;index += 1;}return -1;
}

数组VS链表
在这里插入图片描述
双向链表示例:

/* 双向链表节点类 */
class ListNode {val: number;next: ListNode | null;prev: ListNode | null;constructor(val?: number, next?: ListNode | null, prev?: ListNode | null) {this.val = val  ===  undefined ? 0 : val;        // 节点值this.next = next  ===  undefined ? null : next;  // 指向后继节点的引用this.prev = prev  ===  undefined ? null : prev;  // 指向前驱节点的引用}
}

在这里插入图片描述

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

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

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

  • 高级数据结构:比如在红黑树B 树中,我们需要访问节点的父节点,这可以通过在节点中保存一个指向父节点的引用来实现,类似于双向链表.

  • 浏览器历史:在网页浏览器中,当用户点击前进或后退按钮时,浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。

  • LRU 算法:在缓存淘汰(LRU)算法中,我们需要快速找到最近最少使用的数据,以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

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

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

这篇关于TypeScript数据结构与算法系列(一) —— 链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin