数据结构TypeScript之链表实现详解
前端技术獭 人气:0链表结构特点
链表是线性表的其中一种,用于存储有固定顺序的元素。而元素之间会通过”链“连接在一起。
链表存储的元素称为节点。每个节点内部存在两个值。如下:
this.element
:链表需要存储的单个元素this.next
:指向下一个节点,也就是链表中的”链“,将节点连接在一起。
尝试手动构建链表结构。过程如下:
class LinkedListNode { constructor(element) { this.element = element // 链表要存储的值 this.next = null // 当前节点的下一个节点 } } let A = new LinkedListNode('A') // 第一个节点A let B = new LinkedListNode('B') // 第二个节点B let C = new LinkedListNode('C') // 第三个节点C // 节点之间通过this.next属性值连起来,如下: A.next = B // 节点A下一个是节点B B.next = C // 节点B下一个是节点C console.log(A) // 输出链表:A -> B -> C
面向对象方法封装链表
构造函数
基本单元:链表节点
class LinkedListNode { element: any next: (null | LinkedListNode) constructor(element: any) { this.element = element this.next = null } }
主体:链表
class LinkedList { length: number head: (null | LinkedListNode) constructor() { this.length = 0 this.head = null } }
查找节点
设计一个方法,可以获取当前节点的前中后三个节点。这样可以极大的方便接下来的增删操作。如下:
getLinkedListNode(index: number): (void | { [index: number]: (null | LinkedListNode) }) { if (this.isEmpty()) { throw new Error('LinkedList is empty') } else if (index < 0 || index >= this.length) { throw new Error(`${index} does exist in [0, ${this.length})`) } else if (index >= 0 && index < this.length) { let previous: (null | LinkedListNode) = null let current: (null | LinkedListNode) = this.head for (let i = 0; i < index; i++) { previous = current current = current!.next } return { 0: previous, 1: current, 2: current!.next } } }
增加节点
新节点可插入的范围:index >= 0 && index <= this.length
。也就是说,可以在每个节点的前后都可以插入新的节点。
增加节点的情况分为四种,如下分析:
- 链表为空,不存在节点:直接将新节点的值赋给头节点。
- 在头部之前插入节点(存在index参数且范围符合):利用新节点的
next
缓存当前头节点,然后新节点覆盖头节点。 - 在两个节点之间插入节点(存在index参数且范围符合):利用新节点的
next
缓存当前节点,改变前一个节点的next
指向新节点。 - 在尾部插入节点:遍历到最后一个节点,在节点末尾插入节点。
insert(element: any, index?: number): LinkedList { let node: (null | LinkedListNode) = new LinkedListNode(element) if (this.isEmpty()) { this.head = node } else if (index !== undefined && (index >= 0 && index < this.length)) { if (index === 0) { node.next = this.head this.head = node } else { let current: (void | object) = this.getLinkedListNode(index) node.next = current[0]!.next current[0]!.next = node } } else if (index !== undefined && (index < 0 || index > this.length)) { throw new Error(`${index} does exist in [0, ${this.length}]`) } else if (index === undefined || index === this.length) { let current: (null | LinkedListNode) = this.head while (current!.next !== null) { current = current!.next } current!.next = node } this.length++ return this }
删除节点
链表节点的删除范围:index >= 0 && index < this.length
。打个比方,链表长度为3,那么可删除的位置为0,1,2。
删除节点的情况分为三种,如下分析:
- 删除头节点:链表长度为1,头节点置空。链表长度大于1,头节点的下一个节点覆盖当前头节点。
- 删除中间节点(存在index参数且范围符合):前一个节点的
next
直接指向当前节点的下一个节点。 - 删除尾节点:找到尾节点的前一个节点,将它的
next
属性置空。
注意:每次删除都将改变链表的长度,而节点的删除位置也会跟着改变。
remove(index: number): LinkedList { if (this.isEmpty()) { throw new Error('LinkedList is empty') } else { if (index === 0) { this.head = (this.length === 1) ? null : this.head!.next } else if (index > 0 && index < this.length) { let current: (void | object) = this.getLinkedListNode(index) current[0]!.next = (index + 1 === this.length) ? null : current[2] } else { throw new Error(`${index} does exist in [0, ${this.length})`) } this.length-- return this } }
本文相关代码已放置我的Github仓库
加载全部内容