爱囡囡，爱前端

0%

TypeScript数据结构与算法：链表

发表于 分类于 ， ，

上一篇《TypeScript 数据结构与算法：队列》实现了 Typescript 中队列的数据结构与算法，本篇继续实现链表。

链表 存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。下图展示了一个链表的结构。

与传统的数组对比，链表：

  • 优点：添加或移除元素的时候不需要移动其他元素；
  • 缺点：访问链表中间的一个元素，需要从起点（表头）开始迭代链表直到找到所需的元素；

数据结构

链表

链表应有的方法如下所示：

  • push(element)：向链表尾部添加一个新元素。
  • insert(element, position)：向链表的 position 插入一个新元素。
  • getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回 undefined。
  • remove(element)：从链表中移除一个元素。
  • indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回 -1。
  • removeAt(position)：从链表的 position 位置移除一个元素。
  • isEmpty()：返回链表是否为空。
  • size()：返回链表包含的元素个数。
  • toString()：返回表示整个链表的字符串。

在写 LinkedList 类之前，先写几个辅助的工具：

  • IEqualsFunction：自定义相等比较函数的 type；
  • defaultEquals：默认的相等比较函数；
  • Node：链表中的每个节点，有 element 和 next 两个属性；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 规定了自定义相等比较函数的类型
export type IEqualsFunction<T> = (a: T, b: T) => boolean;

/**
 * @description: 默认的相等比较函数，三等比较
 * @param {T} a
 * @param {T} b
 * @return {boolean} 返回a、b是否相等
 */
export function defaultEquals<T>(a: T, b: T): boolean {
  return a === b;
}

export class Node<T> {
  constructor(public element: T, public next?: Node<T>) {}
}

链表类（LinkedList）的核心思想就两点：

  1. 查找的时候就从 head 开始，沿着每个 node 实例的 next 指向一直查下去；
  2. 增删改的时候，就调整对应位置的 next 指向；

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
import { defaultEquals, IEqualsFunction } from '../util';
import { Node } from './models/linked-list-models';

export default class LinkedList<T> {
  protected count = 0;
  protected head?: Node<T>;

  constructor(protected equalsFn: IEqualsFunction<T> = defaultEquals) {}

  /**
   * @description: 向链表尾部添加一个元素
   * @param {T} element
   */
  push(element: T) {
    const node = new Node(element);
    let current;

    if (this.head == null) {
      // 第一个元素时直接添加
      this.head = node;
    } else {
      // 找到最后一个元素，在它之后添加
      current = this.getNodeAt(this.size() - 1);
      current.next = node;
    }

    // 最后把计数+1
    this.count++;
  }
  /**
   * @description: 获取指定索引处的节点
   * @param {number} index 索引
   * @return {Node<T>} 返回指定索引处的node
   */
  getNodeAt(index: number): Node<T> {
    if (index >= 0 && index <= this.count) {
      let node = this.head;
      // 在第几位上就迭代多少次
      for (let i = 0; i < index && node != null; i++) {
        node = node.next;
      }
      return node;
    }
    return undefined;
  }

  /**
   * @description: 获取指定索引处的元素
   * @param {number} index 索引
   * @return {T} 返回指定索引处的元素
   */
  getElementAt(index: number): T {
    return this.getNodeAt(index)?.element;
  }

  /**
   * @description: 在指定索引位置处插入元素
   * @param {T} element 待插入的元素
   * @param {number} index 插入位置索引
   * @return {boolean} 返回是否插入成功
   */
  insert(element: T, index: number) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);

      // 插入元素同样分“第一个”和“非第一个”两种情况
      if (index === 0) {
        const current = this.head;
        node.next = current;
        this.head = node;
      } else {
        // 解开该位置的next链接，插入新的节点
        const previous = this.getNodeAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      // 最后给count++并返回true
      this.count++;
      return true;
    }
    return false;
  }

  /**
   * @description: 移除指定索引位置处的元素
   * @param {number} index 索引
   * @return {T} 返回移除掉的元素
   */
  removeAt(index: number) {
    if (index >= 0 && index < this.count) {
      let current = this.head;

      // 插移除元素同样分“第一个”和“非第一个”两种情况
      if (index === 0) {
        this.head = current.next;
      } else {
        const previous = this.getNodeAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      // 把计数减一
      this.count--;
      return current.element;
    }
    return undefined;
  }

  /**
   * @description: 移除指定元素
   * @param {T} element 待移除的元素
   * @return {T} element 返回移除的元素
   */
  remove(element: T): T {
    // 调用了removeAt
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

  /**
   * @description: 返回指定元素的索引（只返回从前面数第一个相等的）
   * @param {T} element 元素
   * @return {number} index 索引
   */
  indexOf(element: T): number {
    let current = this.head;

    // 迭代着寻找相等的元素
    for (let i = 0; i < this.size() && current != null; i++) {
      // 用到了判断相等的方法
      if (this.equalsFn(element, current.element)) {
        return i;
      }
      current = current.next;
    }

    return -1;
  }

  /**
   * @description: 返回链表是否为空
   * @return {boolean}
   */
  isEmpty(): boolean {
    return this.size() === 0;
  }

  /**
   * @description: 返回链表的元素数目
   * @return {number}
   */
  size(): number {
    return this.count;
  }

  /**
   * @description: 获取链表的第一个节点
   * @return {Node<T>}
   */
  getHead(): Node<T> {
    return this.head;
  }

  /**
   * @description: 清空链表
   */
  clear() {
    this.head = undefined;
    this.count = 0;
  }

  /**
   * @description: 替代默认toString
   * @return {string}
   */
  toString(): string {
    if (this.head == null) {
      return '';
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current != null; i++) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }
}

双向链表

双向链表和普通链表的区别在于，在链表中，一个节点只有指向下一个节点的链接（next）；而在双向链表中，链接是双向的：一个链向下一个元素（next），另一个链向前一个元素（prev）。

双向链表由于需要每一个节点能指向前一个的节点，所以需要对工具类进行修改，添加一个 prev 的指针：

1
2
3
4
5
6
7
8
9
export class DoublyNode<T> extends Node<T> {
  constructor(
    public element: T,
    public next?: DoublyNode<T>,
    public prev?: DoublyNode<T>
  ) {
    super(element, next);
  }
}

双向链表类（LinkedList）可以继承普通链表类，而且基本上只需要修改“增删”三种方法就可以，需要特别注意的地方是对 tail 的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
import { defaultEquals, IEqualsFunction } from '../util';
import LinkedList from './linked-list';
import { DoublyNode } from './models/linked-list-models';

// 双向链表继承自普通链表
export default class DoublyLinkedList<T> extends LinkedList<T> {
  // 多了一个尾部节点tail，重写了head
  protected head?: DoublyNode<T>;
  protected tail?: DoublyNode<T>;

  constructor(protected equalsFn: IEqualsFunction<T> = defaultEquals) {
    super(equalsFn);
  }

  /**
   * @description: 向双向链表尾部添加一个元素
   * @param {T} element
   */
  push(element: T) {
    const node = new DoublyNode(element);

    if (this.head == null) {
      this.head = node;
      this.tail = node; // 👈 新增
    } else {
      // 👇 修改
      // 添加到尾部，互相交换指针
      this.tail.next = node;
      node.prev = this.tail;
      // 最后把node设为tail
      this.tail = node;
    }
    this.count++;
  }

  /**
   * @description: 在指定索引位置处插入元素
   * @param {T} element 待插入的元素
   * @param {number} index 插入位置索引
   * @return {boolean} 返回是否插入成功
   */
  insert(element: T, index: number): boolean {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(element);
      let current = this.head;

      // 👇 插入到第一个
      if (index === 0) {
        // 链表为空
        if (this.head == null) {
          this.head = node;
          this.tail = node;
          // 链表不为空
        } else {
          node.next = this.head;
          this.head.prev = node; // NEW
          this.head = node;
        }
        // 👇 插入到最后一个
      } else if (index === this.count) {
        current = this.tail; // {2}
        current.next = node;
        node.prev = current;
        this.tail = node;
        // 👇 普通情况
      } else {
        const previous = this.getNodeAt(index - 1);
        current = previous.next;
        node.next = current;
        previous.next = node;

        current.prev = node; // NEW
        node.prev = previous; // NEW
      }
      this.count++;
      return true;
    }
    return false;
  }

  /**
   * @description: 移除指定索引位置处的元素
   * @param {number} index 索引
   * @return {T} 返回移除掉的元素
   */
  removeAt(index: number): T {
    if (index >= 0 && index < this.count) {
      let current = this.head;

      // 👇 删除第一个
      if (index === 0) {
        this.head = this.head.next;
        // 如果只有一个元素，需要同时调整tail
        if (this.count === 1) {
          this.tail = undefined;
        } else {
          this.head.prev = undefined;
        }
        // 👇 删除最后一个
      } else if (index === this.count - 1) {
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = undefined;
        // 👇 普通删除
      } else {
        current = this.getNodeAt(index);
        const previous = current.prev;
        const next = current.next;
        previous.next = next;
        next.prev = previous;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

  /**
   * @description: 获取链表的最后一个节点
   * @return {Node<T>}
   */
  getTail(): DoublyNode<T> {
    return this.tail;
  }

  /**
   * @description: 清空链表
   */
  clear() {
    super.clear();
    this.tail = undefined;
  }

  /**
   * @description: 从尾向头输出string
   * @return {string}
   */
  inverseToString() {
    if (this.tail == null) {
      return '';
    }
    let objString = `${this.tail.element}`;
    let previous = this.tail.prev;
    while (previous != null) {
      objString = `${objString},${previous.element}`;
      previous = previous.prev;
    }
    return objString;
  }
}

循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）指向第一个元素（head）。

循环链表类（CircularLinkedList）同样可以继承自普通链表类，也是基本上只需要修改“增删”三种方法，需要特别注意的地方是对 tail 和 head 之间的指向问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import { defaultEquals, IEqualsFunction } from '../util';
import LinkedList from './linked-list';
import { Node } from './models/linked-list-models';

// 循环链表也继承自普通链表
export default class CircularLinkedList<T> extends LinkedList<T> {
  constructor(protected equalsFn: IEqualsFunction<T> = defaultEquals) {
    super(equalsFn);
  }

  /**
   * @description: 向链表尾部添加一个元素
   * @param {T} element
   */
  push(element: T) {
    const node = new Node(element);
    let current;

    if (this.head == null) {
      this.head = node;
    } else {
      current = this.getNodeAt(this.size() - 1);
      current.next = node;
    }

    node.next = this.head; // 👈 要记得把最后一个node的next指向head

    this.count++;
  }

  /**
   * @description: 在指定索引位置处插入元素
   * @param {T} element 待插入的元素
   * @param {number} index 插入位置索引
   * @return {boolean} 返回是否插入成功
   */
  insert(element: T, index: number) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      let current = this.head;

      if (index === 0) {
        // 👇 插入到第一个时分两种情况
        if (this.head == null) {
          // 没有元素
          this.head = node;
          node.next = this.head; // 👈 特殊
        } else {
          // 已有若干元素
          let tail = this.getNodeAt(this.size() - 1);
          this.head = node;
          node.next = current;
          tail.next = this.head; // 👈 特殊
        }
      } else {
        const previous = this.getNodeAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  /**
   * @description: 移除指定索引位置处的元素
   * @param {number} index 索引
   * @return {T} 返回移除掉的元素
   */
  removeAt(index: number) {
    if (index >= 0 && index < this.count) {
      let current = this.head;

      if (index === 0) {
        // 👇 删除第一个时分两种情况
        if (this.size() === 1) {
          // 只有一个元素
          this.head = undefined;
        } else {
          // 有若干个元素
          let tail = this.getNodeAt(this.size() - 1);
          this.head = this.head.next;
          tail.next = this.head; // 👈 next指向head
        }
      } else {
        const previous = this.getNodeAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }
}

有序链表

有序链表是指保持元素有序的链表结构。

有序链表在插入时需要通过比较来判断插入位置，所以需要一个“比较”工具方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 规定自定义Compare的类型
export type ICompareFunction<T> = (a: T, b: T) => number;

// 比较结果的枚举值
export enum Compare {
  LESS_THAN = -1,
  BIGGER_THAN = 1,
  EQUALS = 0,
}

/**
 * @description: 默认的大小比较函数
 * @param {T} a
 * @param {T} b
 * @return {Compare} 返回 -1 0 1 代表 小于 等于 大于
 */
export function defaultCompare<T>(a: T, b: T): Compare {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

有序链表类（SortedLinkedList）也继承自普通链表类，因为在插入时就需要排到正确的位置，所以只需要修改“增”的两种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import {
  Compare,
  defaultCompare,
  defaultEquals,
  ICompareFunction,
  IEqualsFunction,
} from '../util';
import LinkedList from './linked-list';

// 排序链表也继承自普通链表
export default class SortedLinkedList<T> extends LinkedList<T> {
  constructor(
    protected equalsFn: IEqualsFunction<T> = defaultEquals,
    protected compareFn: ICompareFunction<T> = defaultCompare
  ) {
    super(equalsFn);
  }

  /**
   * @description: 向链表添加一个元素
   * @param {T} element
   */
  push(element: T) {
    if (this.isEmpty()) {
      super.push(element);
    } else {
      const index = this.getIndexNextSortedElement(element);
      super.insert(element, index);
    }
  }

  /**
   * @description: 向链表添加一个元素
   * @param {T} element
   */
  insert(element: T, index: number = 0) {
    if (this.isEmpty()) {
      return super.insert(element, 0);
    }
    index = this.getIndexNextSortedElement(element);
    return super.insert(element, index);
  }

  /**
   * @private 私有方法
   * @description: 获取元素应该插入的位置
   * @param {T} element
   * @return {Number} index
   */
  private getIndexNextSortedElement(element: T) {
    let current = this.head;
    let i = 0;

    // 迭代比较，通过compareFn比较找到合适位置
    for (; i < this.size() && current; i++) {
      const comp = this.compareFn(element, current.element);
      if (comp === Compare.LESS_THAN) {
        return i;
      }
      current = current.next;
    }

    return i;
  }
}

下一篇来分析集合。

前端记事本，不定期更新，欢迎关注！

👆 全文结束，棒槌时间到 👇