线性表
由于我是搞前端的为了更友好的描述数据结构，所以全部代码示例都是用TypeScript来编写。
1、线性表类型
- 1.顺序存储结构（数组）
- 2.链式存储结构（链表）
1.1、顺序存储
一般指数组，内部数据的存储单元在内存中相邻
优势： 查询很快，时间复杂度为O(1)
劣势：
- 元素增、删操作时间复杂度为O(n)
- 使用时需要提前确定长度
- 需要占据连续内存空间
1.2、链式存储
n 个数据元素的有限序列，通常为链式，叫作线性链表或链表。链表中的元素为结点，结点是一块内存空间存储一条数据。结点通常由两个部分组成：
- 节点存储的数据
- 指向下一个节点的指针
来看一下链表的typescript实现
class ListNode {
val: number
next: ListNode | null
constructor(val?: any, next?: ListNode | null) {
this.val = val
this.next = (next===undefined ? null : next)
}
}
2、链表类型
链表类型大体分为下列：
- 带头、不带头
- 单向、双向
- 循环、非循环
2.1 带头不带头
链表都有头指针，带头结点的链表头指针指向的是头结点，不带头结点的头指针直接指向首元结点。
首元节点：链表中用来存储元素节点的第一个节点
带头：
不带头：
操作差异： 删除和新增操作中，无论操作位置，带头结点的链表不需要修改头指针的值，而不带头结点的有时候需要。清空操作中，带头结点的保留头结点，不带头结点的要销毁。
结构差异： 带头链表不论链表是否为空，均含有一个头结点，不带头单链表均无结点。
一般使用链表都为带头链表
2.2、双向链表
单项链表中，仅有一个指针指向下一个节点的位置，双向链表中，每个节点有有个指针：
- pre：指向上一个节点位置
- next：指向下一个节点位置
双向链表节点图：
双向链表节点数据结构：
class TwoWayListNode {
val: number
pre: ListNode | null
next: ListNode | null
constructor(val?: any, pre?: ListNode | null, next?: ListNode | null) {
this.val = val
this.next = (next===undefined ? null : next)
}
}
双向链表图：
// 简单的来实现一下上述结构，实际使用时可自行封装统的类
const p1 = new TwoWayListNode('p1', null, null)
const p2 = new TwoWayListNode('p2', null, null)
const p3 = new TwoWayListNode('p3', null, null)
p1.next = p2
p2.pre = p1
p2.next = P3
2.3、循环链表
链表中最后一个节点指向头节点
// 简单的来实现一下上述结构，实际使用时可自行封装统的类
const p1 = new ListNode('p1', null)
const p2 = new ListNode('p2', null)
const p3 = new ListNode('p3', null)
p1.next = p2
p2.pre = p1
p2.next = P3
p3.next = p1
以此类推还有双向项循环链表，这里就不展开了
3、线性表数据处理分析
3.1、顺序存储操作
查询:
由于顺序存储中数据按照逻辑顺序依次放入连续的存储单元中，所以在顺序表结构中很容易实现查询操作，直接通过下标去拿即可。时间复杂度为O(1)
插入:
在顺序存储结构中, 插入尾部的时间复杂度为O(1)，其他位置时间复杂度为O(n)。
如下图想要在3位置插入一条数据 "六"，需要将"四", "五" 位置的数据依次向后移动一个单位
删除:
在顺序存储结构中, 删除尾部的时间复杂度为O(1)，其他位置时间复杂度为O(n)。
如下图想删除数据 "六"，先将3位置的数据设置为空，"四", "五" 位置的数据依次向前移动一个单位
3.2 链式存储
插入：
// p1 -> p2 -> p3 -> p4
p1.next = p5
p5.next = p2
删除：
// p1 -> p2 -> p3 -> p4
p1.next = p3
p2.next = null
查询：
链表中查找只能从链表的头指针出发，顺着连标指针逐个结点查询，直到查到想要的结果为止，时间复杂度O(n)
作者：siegaii
链接：https://juejin.cn/post/7031868181203386405
