单链表
单链表：链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。
头节点：我们习惯性地把第一个结点
尾节点：习惯把最后一个节点叫做尾节点，指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
链表 vs 数组
插入删除
数组：在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。
链表：在链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的 O(1)。
链表要想随机访问第 k 个元素
数组：时间复杂度为 O(1)。
链表：链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。
与数组一样，链表也支持数据的查找、插入和删除操作。
// 头部插入节点 尾部插入节点 删除节点 打印节点值等interface List<T> { insertToHead: (value: T) => void; // 头部插入 insertToTail: (value: T) => void; // 尾部插入 findByValue: (value: T) => SingleNode<T> | null; // 按值查询 findByIndex: (index: number) => SingleNode<T> | null; // 按索引查询 insertToIndex: (value: T, index: number) => void; // 按索引插入 remove: (value: T) => boolean; // 删除链表的某个节点 toString:()=>string // print 节点value}//链表节点class SingleNode<T> { value: T; // tip: 静态成员不能使用泛型的类型参数。 next: SingleNode<T> | null; constructor(value: T, next: SingleNode<T> | null = null) { this.value = value; this.next = null; }}
class SingleLinkedList<T> implements List<T> { // 哨兵头节点 private readonly head: SingleNode<T>;
constructor() { this.head = new SingleNode<any>(null); } insertToHead(value: T): void { const newNode = new SingleNode(value); newNode.next = this.head.next; this.head.next = newNode; } insertToTail(value: T) { const newNode = new SingleNode(value); let p = this.head; while (p.next !== null) { p = p.next; } p.next = newNode; } insertToIndex(value: T, index: number) { const newNode = new SingleNode(value); let p = this.head; let pos = 0; while (p.next !== null && pos !== index) { p = p.next; pos++; } if (p.next === null) return ""; newNode.next = p.next; p.next = newNode; }
findByValue(value: T): SingleNode<T> | null { let p = this.head; while (p.next !== null) { if (p.next.value === value) return p.next; p = p.next; } return p.next; }
findByIndex(index: number): SingleNode<T> | null { let p = this.head; let pos = 0; while (p.next !== null && pos !== index) { p = p.next; pos++; } return p.next; }
remove(value: T): boolean { let p = this.head; while (p.next !== null) { if (p.next.value === value) break; p = p.next; } if (p.next === null) return false; p.next = p.next.next; return true; } toString():string{ let ret: string ='' let p = this.head; while(p.next !== null) { ret = `${ret}-${p.next.value}` p= p.next } console.log(`print-${ret}`) return ret }}const singleLinkedList = new SingleLinkedList<string>()singleLinkedList.insertToHead('my')singleLinkedList.insertToTail('god')singleLinkedList.insertToIndex('great',1)singleLinkedList.toString() // my-great-god
复制代码
虽然写程序接近 7 年的时间了，但是之前总是为了完成而完成，不去思考问什么会这样。
后续打算记录对常见算法、设计模式的理解。
Come on , let's master programmer!
reference: 俩张图片引用王争 大佬的《数据结构与算法之美》https://time.geekbang.org/column/intro/100017301?tab=catalog
评论