线性表

由于我是搞前端的为了更友好的描述数据结构,所以全部代码示例都是用TypeScript来编写。


1、线性表类型



  • 1.顺序存储结构(数组)
  • 2.链式存储结构(链表)

1.1、顺序存储


一般指数组,内部数据的存储单元在内存中相邻



优势: 查询很快,时间复杂度为O(1)


劣势:



  1. 元素增、删操作时间复杂度为O(n)
  2. 使用时需要提前确定长度



  1. 需要占据连续内存空间

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

0 个评论

要回复文章请先登录注册