单向链表结构
链表属于线性表的一类，与数组不同的是，单向链表是链式存储，其地址不一定连续，大致结构如图
链表存储的是一个一个的节点（Node），节点之间通过
next
属性相连，要存储的值存于
value
中，而链表通过
head
属性将这些节点串联起来
接口
通过学习，链表应该具有对外暴露以下接口
interface List<E> {
clear: () => void // 清空链表
add(element: E, index?: number): void // 在指定位置添加元素，默认为最后
set(index: number, element: E): E // 设置特定位置的值
isEmpty: () => boolean// 链表是否为空
get: (index: number) => E// 获取特定位置的值
remove: (index: number) => E // 删除指定位置的元素
contains: (element: E) => boolean // 是否包含某个元素
indexOf(element: E): number // 获取元素的位置
}
实现
创建单向链表类
单向链表类应该具有以下属性
- size 链表的长度
- head 指向第一个 node
同时实现了 上面的
List
接口
class SingleLinkList<E> implements List<E> {
#size: number = 0
#head: Node<E> | null = null
clear() {}
add(element: E, index: number = this.#size){}
set(index: number, element: E): E {return element}
isEmpty(){return false}
get(index: number): E{return (1 as E)}
remove(index:number):E {{return (1 as E)}}
contains (element: E) {return false}
indexOf(element: E): number {return 0}
}
是#
新增语法用于创建一个es2022
属性，所以一会还会多两个pravite
用于访问这两个属性getter
创建节点类
class Node<E> {
constructor(public value: E, public next: Node<E> | null) {}
}
具体方法实现
clear
clear
是用来清空链表的，所以很简单，直接将
size
与
head
初始化即可
clear() {
this.#head = null
this.#size = 0
}
isEmpty
isEmpty
是用来判断链表是否为空，所以直接判断
size
是否为0即可
isEmpty() {
return this.#size === 0
}
add
add
方法用来向链表中添加元素，在只传入了一个参数的情况下，默认将元素存为链表最后，即为索引值等于
size
。
首先要明确
add
方法的作用：
- 创建新节点
- 插入到指定位置
而
add
方法涉及到了索引值，所以我们需要对传入的参数进行边界判断，由于是向链表添加元素，所以条件如下
为了方便以后用到索引的方法进行判断，我将其抽离成了一个私有方法
#checkRangeForAdd(index: number) {
if (index < 0 || index > this.#size) {
throw new Error(`${index} out of range`)
}
}
我对于
add
方法的思路如下
- 首先判断
index
head
next
head
- 如果不是0的位置，那么我们就可以获取传入索引节点的前一个元素，并且将他的
next
next
next
add(element: E, index: number = this.#size) {
this.#checkRangeForAdd(index)
if (index === 0) {
//如果是第一个元素，就将head指向新元素就好
this.#head = new Node<E>(element, this.#head)
} else {
// 如果不是第一个元素，就获取插入位置的前一个元素
let preNode = this.#node(index - 1)
// 将前一个元素的next作为新节点的next
let newNode = new Node<E>(element, preNode.next)
// 将前一个节点的next指向新节点
preNode.next = newNode
}
this.#size++
}
/**
* 获取索引位置的节点
* @param index 索引
*/
#node(index: number) {
this.#checkRange(index) // 边界判断
let node = this.#head as Node<E> // 拿到head节点
for (let i = 0; i < index; i++) {
node = node.next as Node<E>
}
return node
}
node方法是我用来根据索引获取节点的方法，他从head节点开始遍历所有节点，直到索引满足要求，就返回节点
get / set
get
用来获取特定位置的值，有了上面的
node
方法后这俩就很简单了
set(index: number, element: E): E {
const node = this.#node(index) // 获取当前节点
const oldValue = node.value // 获取旧值
node.value = element
return oldValue
}
get(index: number): E {
return this.#node(index).value
}
结束语
剩余的方法在之后实现，数据结构还是太难了呀
