(二）链表结构

备注：根据coderwhy数据结构与算法课程进行笔记总结

1.数组缺点：

• 数组创建通常需要申请一段连续的内存空间，且大小固定，因此当前数组不能满足容量需求时，就需要扩容。
• 在数组开头或中间位置插入数据成本很高，需要进行大量元素的位移。

2.链表优势：

• 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。
• 内存空间不是必须连续的。可利用计算机内存，实现灵活的内存动态管理
• 不必在创建时就确定大小，并且可以无限延申下去

3.链表缺点：访问元素时，需从头开始一个个找，访问效率比较低

简要介绍

链表类似于火车，有一个火车头，火车头会连接一个节点，节点上有乘客（数据），该节点连接下一个节点，以此类推

 

 

封装类结构

封装一个Node类，用于封装每个节点上的信息；

封装一个LinkedList类，用于表示链表结构

// 1.创建Node节点类
class Node<T> {value:T;next:Node<T> | null = null;constructor(value:T) {this.value = value}
}// 2.创建LinkedList类
class LinkedList<T> {head:Node<T> | null = null;private size:number = 0;
}
export {}

封装链表相关方法

列表常见操作：

 

1.append()

 

2.traverse()方法

3.插入节点：可分两种情况：

从头部插入；从其它地方插入

4.removeAt方法：根据位置移除对应数据； 根据数据，找到相应位置，在移除数据

• 删除第一项时，直接让head指向第二项；

 

• 删除其它项时，首先通过while循环找到正确的位置，让上一项的next指向current的next→中间项无引用指向它→就不存在于链表后，后面会被回收掉！！！

 

5.根据索引查找对应元素：get

6.将查找当前节点的逻辑部分抽取出来进行封装→实现复用

7.更新方法

8.indexOf

9.根据value删除节点

10.判断链表是否为空

// 1.创建Node节点类
class Node<T> {value:T;next:Node<T> | null = null;constructor(value:T) {this.value = value}
}// 2.创建LinkedList类
class LinkedList<T> {head:Node<T> | null = null;private size:number = 0;get length() {return this.size}// 封装私有方法// 根据position获取当前的节点private getNode(position:number): Node<T> | null{let current = this.headlet index = 0while(index++ < position && current) {current = current.next}return current}// 1.追加节点append(value:T) {// 1.根据value创建一个新节点const newNode = new Node(value)// 2.判断this.head是否为nulif(this.head === null) {this.head = newNode}else {let current = this.headwhile(current.next){current = current.next}// 直到Node.next为null时，退出循环current.next = newNode}this.size++}// 2.遍历链表traverse() {const values:T[] = []let current = this.headwhile(current) {values.push(current.value)current = current.next}console.log(values.join('->'));//aaa->bbb->ccc->ddd}// 3.插入方法insert(value: T, position: number): boolean {// 1. 边界条件判断if (position < 0 || position > this.size) return false;// 2. 根据 value 创建新的节点const newNode = new Node(value);// 3. 判断是否需要插入头部if (position === 0) {newNode.next = this.head;this.head = newNode;} else {// 4.找到插入位置的前一个节点/* let current = this.head;let previous: Node<T> | null = null;let index = 0;while(current && index < position ){previous = currentcurrent = current.next;index++}previous!.next = newNode;newNode.next = current; */// 重构代码const previous = this.getNode(position - 1);newNode.next = previous?.next ?? null;previous!.next = newNode;}// 6. 更新链表大小this.size++;return true;}// 4.删除方法removeAt(position:number): T | null {// 1.越界判断if(position < 0 || position >= this.size) return null;// 2.判断是否删除第一个节点let current = this.head;if(position === 0) {this.head = current?.next ?? null;}else{/* let previous: Node<T> | null = null;let index = 0;while(index++ < position && current) {previous = current;current = current.next}// 找到需要的节点previous!.next = current?.next ?? null; */// 重构为如下代码const previous = this.getNode(position - 1)previous!.next = previous?.next?.next ?? null;}this.size--;return null;}// 5.获取方法get(position:number): T | null {// 5.1越界命题if(position < 0 || position >= this.size) return null;// 5.2查找元素return this.getNode(position)?.value  ?? null;}// 7.更新方法update(value:T,position:number): boolean {if(position < 0 || position >= this.size) return false;const currentNode = this.getNode(position)currentNode!.value = value;return true;}// 8.根据值获取对应位置的索引indexOf(value:T): number {// 从第一个节点开始，向后遍历let current = this.head;let index = 0;while(current) {if(current.value === value) {return index}index++current = current.next}return -1;}// 9.根据value删除节点remove(value:T): T | null {const index = this.indexOf(value)return this.removeAt(index)}// 10.判断链表是否为空isEmpty(): boolean {return this.size === 0}
}const linkedList = new LinkedList<string>()
linkedList.append('aaa')
linkedList.append('bbb')
linkedList.append('ccc')
linkedList.append('ddd')
linkedList.insert('eee',0)//eee->aaa->bbb->ccc->ddd
linkedList.traverse()
linkedList.insert('abc',3)//eee->aaa->bbb->abc->ccc->ddd
linkedList.traverse()
linkedList.insert('cdn',6)//eee->aaa->bbb->abc->ccc->ddd->cdn
linkedList.traverse()// 测试删除节点
linkedList.removeAt(0)//aaa->bbb->abc->ccc->ddd->cdn
linkedList.traverse()
linkedList.removeAt(2)
linkedList.traverse()//aaa->bbb->ccc->ddd->cdn// 测试get
console.log(linkedList.get(0));
console.log(linkedList.get(1));
console.log(linkedList.get(2));// 测试update
linkedList.update('abc',1)
linkedList.traverse()//aaa->abc->ccc->ddd->cdn// 测试索引值
console.log(linkedList.indexOf('abc'));//1// 测试remove
linkedList.remove('cdn')
linkedList.traverse()//aaa->abc->ccc->ddd
linkedList.remove('aaa')
linkedList.remove('abc')
linkedList.traverse()//ccc->ddd
console.log(linkedList.isEmpty());//falseexport {}

常见面试题

237.删除链表中的节点（237. 删除链表中的节点 - 力扣（LeetCode））

206.反转链表（206. 反转链表 - 力扣（LeetCode））

1.栈结构实现:先存入栈结构中，再从栈结构中一个个取出，但是要注意将最后一个对象的指针指向Null

class ListNode {val: numbernext: ListNode | nullconstructor(val?: number, next?: ListNode | null) {this.val = (val===undefined ? 0 : val)this.next = (next===undefined ? null : next)}
}
function reverseList(head: ListNode | null): ListNode | null {// 生命情况下链表需要处理// 1.head本身为nullif(head === null) return null// 2.head只有一个节点if(head.next === null) return head// 3.head有多个节点// 3.1数组模拟栈结构const stack:ListNode[] = []while(head){stack.push(head)head = head.next}// 依次从栈结构中取出元素，放到一个新的链表中去const newHead: ListNode = stack.pop()!let current = newHeadwhile(stack.length>0) {const node = stack.pop()!current!.next = nodecurrent = current!.next}// 注意：获取到最后一个节点时，需将该节点的next设置为null→否则会出现循环引用的问题// 对象是存在指针的，如果不给它赋值为空，它依旧指向前一个节点current!.next = nullreturn newHead
};// 测试代码
const node = new ListNode(1)
node.next = new ListNode(2)
node.next.next = new ListNode(3)
const newHead = reverseList(node)let current = newHead
while(current){console.log(current.val);current = current.next
}
export{}

2.非递归实现:

 

class ListNode {val: numbernext: ListNode | nullconstructor(val?: number, next?: ListNode | null) {this.val = (val===undefined ? 0 : val)this.next = (next===undefined ? null : next)}
}
function reverseList(head: ListNode | null): ListNode | null {// 1.判断节点为null或只有一个节点，直接返回即可if(head === null || head.next === null) return head//2.反转链表结构 let newHead:ListNode | null = nullwhile(head) {let current: ListNode | null = head.nexthead.next = newHead//即nullnewHead = headhead = current}return newHead
};// 测试代码
const node = new ListNode(1)
node.next = new ListNode(2)
node.next.next = new ListNode(3)
const newHead = reverseList(node)let current = newHead
while(current){console.log(current.val);current = current.next
}export{}

3.递归实现:

class ListNode {val: numbernext: ListNode | nullconstructor(val?: number, next?: ListNode | null) {this.val = (val===undefined ? 0 : val)this.next = (next===undefined ? null : next)}
}
function reverseList(head: ListNode | null): ListNode | null {// 1.如果是递归，必须存在结束条件if(head === null || head.next === null) return headconst newHead = reverseList(head?.next ?? null)// 2.完成想要做的操作，是在这个位置// 第一次来到这里的时候是倒数第二个节点head.next.next = headhead.next = nullreturn newHead
};// 测试代码
const node = new ListNode(1)
node.next = new ListNode(2)
node.next.next = new ListNode(3)
const newHead = reverseList(node)let current = newHead
while(current){console.log(current.val);current = current.next
}export{}

查找算法的性能对比

算法复杂度即算法在输入规模变化时的运行效率

顺序查找的时间复杂度为O(n)

function sequentSearch(array:number[],num:number) {for (let i = 0; i < array.length; i++) {if (array[i] === num) {return i}}return -1
}const index = sequentSearch([1,3,9,10,22,50,66,77,99,100],99)
console.log(index);

二分查找的时间复杂度为O(log n)

function binarySearch(array:number[],num:number) {// 1.定义左边的索引let left = 0// 2.定义右边的索引let right = array.length - 1// 3.开始查找while(left <= right) {let mid = Math.floor((left + right) / 2)const midNum = array[mid]if(midNum === num){return mid}else if (midNum < num) {left = mid + 1}else{right = mid - 1}}return -1
}const index = binarySearch([1,2,5,6,8,9,15,18],15)
console.log(index);export{}

测试不同算法的消耗时间：

import sequentSearch from "./01-查找算法-顺序查找";
import binarySearch from "./02-查找算法-二分查找";const nums = new Array(1000000).fill(0).map((_,index) => index)
const num = 500000// 顺序查找
/* const start = performance.now()
const index = sequentSearch(nums,num)
const end = performance.now()
console.log("索引的位置:",index,"消耗的事件：",(end - start ));//2.4978999998420477ms */// 二分查找
const start = performance.now()
const index = binarySearch(nums,num)
const end = performance.now()
console.log("索引的位置:",index,"消耗的事件：",(end - start ));//0.03710000030696392msexport{}

我们也可以将检查其消耗时间的逻辑封装成一个包，安装后，直接调用

1.安装：

npm install hy-algokit

2.使用：

import {testOrderSearchEfficiency} from "hy-algokit"
import sequentSearch from "./01-查找算法-顺序查找";
import binarySearch from "./02-查找算法-二分查找";testOrderSearchEfficiency(sequentSearch)
testOrderSearchEfficiency(binarySearch)export{}

大O表示由来和 推导过程

推导过程：

 

常见的对数阶：

 

空间复杂度

与时间复杂度类似，通常需要分析程序中需要额外分配的内存空间，如数组、变量、对象、递归等

举例：

• 对于一个递归算法来说，每次调用都会在内存中分配新的栈帧，这种栈帧占据了额外的空间→其空间复杂度为O(n)
• 对于迭代算法来说，每次迭代中不需要额外分配空间（无指针直接销毁），故其复杂度为O(1)

数组和链表复杂度对比

1.数组是一种连续的存储结构，通过下标可直接访问到数组中的任意元素

2.链表是一种链式结构，通过指针连接起来的节点组成，访问链表中的元素需从头开始遍历

时间复杂度对比：

操作	数组（Array）	链表（Linked List）
访问元素（按索引）	O(1)	O(n)
插入元素（在头部）	O(n)	O(1)
插入元素（在中间）	O(n)	O(1)（找到位置后）
插入元素（在尾部）	O(1)（动态数组为 O(1) 平均）	O(1)
删除元素（在头部）	O(n)	O(1)
删除元素（在中间）	O(n)	O(1)（找到位置后）
删除元素（在尾部）	O(1)（动态数组为 O(1) 平均）	O(1)
搜索元素	O(n)	O(n)

空间复杂度：

数据结构	空间复杂度
数组	O(n)
链表	O(n)（每个节点包含指针）

在实际开发中的选择：

• 如果数量不大且需要频繁随机访问元素，使用数组更好；
• 如果数据量大，或者需要频繁插入和删除元素，使用链表更好