前言

单链表和双链表实现

单链表
  1. type LinkNode = {
  2.   value: any;
  3.   next: LinkNode;
  4. } | null;
  6. const loopIndex = Symbol();
  7. class LinkedList {
  8.   nodes: LinkNode[] = [];
  9.   isLoop: boolean = false;
  10.   constructor(isLoop: boolean = false) {
  11.     this.isLoop = isLoop;
  12.   }
  13.   get size(): number {
  14.     return this.nodes.length;
  15.   }
  16.   get head(): LinkNode {
  17.     return this.size ? this.nodes[0] : null;
  18.   }
  19.   get tail(): LinkNode {
  20.     return this.size ? this.nodes[this.size - 1] : null;
  21.   }
  22.   [loopIndex](index: number): number {
  23.     if (index < 0) return this.size + index;
  24.     if (index > this.size) return this.size;
  25.     return index;
  26.   }
  27.   insertAt(index: number, value: any) {
  28.     index = this[loopIndex](index);
  29.     const previous: LinkNode = this.nodes[index - 1] || null;
  30.     const next: LinkNode = this.nodes[index] || null;
  31.     const node: LinkNode = {
  32.       value: value,
  33.       next: next,
  34.     };
  35.     if (previous) previous.next = node;
  36.     // 循环链表，首尾需要处理
  37.     if (index === this.size && this.isLoop) node.next = this.head;
  38.     if (index === 0 && this.isLoop) this.tail.next = node;
  39.     this.nodes.splice(index, 0, node);
  40.   }
  41.   insertHead(value: any) {
  42.     this.insertAt(0, value);
  43.   }
  44.   insertTail(value: any) {
  45.     this.insertAt(this.size, value);
  46.   }
  47.   removeAt(index: number): LinkNode[] {
  48.     index = this[loopIndex](index);
  49.     let previous: LinkNode = this.nodes[index - 1] || null;
  50.     let next: LinkNode = this.nodes[index + 1] || null;
  51.     // 循环链表，首部处理
  52.     if (this.isLoop && index === 0) {
  53.       previous = this.tail;
  54.     }
  55.     // 循环链表，尾部处理
  56.     if (this.isLoop && index === this.size - 1) {
  57.       next = this.head;
  58.     }
  59.     if (previous) previous.next = next;
  60.     return this.nodes.splice(index, 1);
  61.   }
  62.   getAt(index: number): LinkNode {
  63.     index = this[loopIndex](index);
  64.     return this.nodes[index];
  65.   }
  66.   clear() {
  67.     this.nodes = [];
  68.   }
  69.   reverse() {
  70.     return this.nodes.reduce((acc, { value }) => {
  71.       return [{ value: value, next: acc[0] || null }, ...acc];
  72.     }, []);
  73.   }
  74.   *[Symbol.iterator]() {
  75.     yield* this.nodes;
  76.   }
  77. }

双向链表
  1. type LinkNode = {
  2.   value: any;
  3.   next: LinkNode;
  4.   previous: LinkNode;
  5. } | null;
  7. const loopIndex = Symbol();
  8. class DoubleLinkedList {
  9.   nodes: LinkNode[] = [];
  10.   isLoop: boolean = false;
  11.   constructor(isLoop = false) {
  12.     this.isLoop = isLoop;
  13.   }
  14.   get size(): number {
  15.     return this.nodes.length;
  16.   }
  17.   get head(): LinkNode {
  18.     return this.size ? this.nodes[0] : null;
  19.   }
  20.   get tail(): LinkNode {
  21.     return this.size ? this.nodes[this.size - 1] : null;
  22.   }
  23.   [loopIndex](index: number): number {
  24.     if (index < 0) return this.size + index;
  25.     if (index > this.size) return this.size;
  26.     return index;
  27.   }
  28.   insertAt(index: number, value: any) {
  29.     index = this[loopIndex](index);
  30.     const previous: LinkNode = this.nodes[index - 1] || null;
  31.     const next: LinkNode = this.nodes[index] || null;
  32.     const node: LinkNode = {
  33.       value: value,
  34.       previous: previous,
  35.       next: next,
  36.     };
  37.     if (previous) previous.next = node;
  38.     if (next) next.previous = node;
  39.     // 循环链表，首尾需要处理
  40.     if (this.isLoop && index === 0) {
  41.       node.previous = this.tail;
  42.       this.tail.next = node;
  43.     }
  44.     if (this.isLoop && index === this.size) {
  45.       node.next = this.head;
  46.       this.head.previous = node;
  47.     }
  48.     this.nodes.splice(index, 0, node);
  49.   }
  50.   insertHead(value: any) {
  51.     this.insertAt(0, value);
  52.   }
  53.   insertTail(value: any) {
  54.     this.insertAt(this.size, value);
  55.   }
  56.   removeAt(index: number): LinkNode[] {
  57.     index = this[loopIndex](index);
  58.     let previous: LinkNode = this.nodes[index - 1] || null;
  59.     let next: LinkNode = this.nodes[index + 1] || null;
  60.     // 循环列表，首部处理
  61.     if (this.isLoop && index === 0) {
  62.       previous = this.tail;
  63.     }
  64.     // 循环列表，尾部处理
  65.     if (this.isLoop && index === this.size - 1) {
  66.       next = this.head;
  67.     }
  68.     if (previous) previous.next = next;
  69.     if (next) next.previous = previous;
  70.     return this.nodes.splice(index, 1);
  71.   }
  72.   getAt(index: number): LinkNode {
  73.     index = this[loopIndex](index);
  74.     return this.nodes[index];
  75.   }
  76.   clear() {
  77.     this.nodes = [];
  78.   }
  79.   reverse() {
  80.     return this.nodes.reduce((acc, { value }) => {
  81.       const next = acc[0] || null;
  82.       const node = {
  83.         value: value,
  84.         next: next,
  85.         previous: null,
  86.       };
  87.       if (next) next.previous = node;
  88.       return [node, ...acc];
  89.     }, []);
  90.   }
  91.   *[Symbol.iterator]() {
  92.     yield* this.nodes;
  93.   }
  94. }

反转链表
  1. function reverse(list){
  2.     let cur = list.head;
  3.   let previous = null;
  4.   while(cur !== null){
  5.       let temp = cur.next;
  6.     cur.next = previous;
  7.     previous = cur;
  8.     cur = temp;
  9.   }
  10. }