循环链表

循环链表（Circular LinkedList）是一种特殊的链表数据结构：

在普通链表的基础上，最后一个节点的下一个节点不再是 null，而是指向链表的第一个节点。

这样形成了一个环，使得链表能够被无限遍历。

这样，可以在单向循环链表中从任意一个节点出发，不断地遍历下一个节点，直到回到起点。

重构 LinkedList（方便继承）

对之前实现的链表进行重构

新增尾部节点 及判断方法

1
2
3
4
5
6
7
8
9
10
// protected 子类可访问
  protected head: Node<T> | null = null;
  protected length: number = 0;
  protected tail: Node<T> | null = null;
  get size() {
    return this.length;
  }
  private isTail(node: Node<T>) {
    return this.tail === node;
  }

append 重构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 追加元素 重构
  append(value: T): void {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      // let current = this.head;
      // while (current.next) current = current.next;
      // current.next = node;
      this.tail!.next = node;
    }
    this.tail = node;
    this.length++;
  }

traverse 重构

1
2
3
4
5
6
7
8
9
10
11
12
13
// 遍历
  traverse(): string {
    const value: T[] = [];
    let current = this.head;
    while (current) {
      value.push(current.val);
      // 针对循环链表 避免无限循环打印
      if (this.isTail(current)) {
        current = null;
      } else {
        current = current.next;
      }
    }

insert 重构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 下标插入
  insert(value: T, position: number): boolean {
    // 判断越界
    if (position < 0 || position > this.size) return false;
    // 添加到第一个位置
    const newNode = new Node(value);
    let current = this.head;
    if (position === 0) {
      this.head = newNode;
      newNode.next = current;
    } else {
      const previous = this.getNode(position - 1);
      newNode.next = previous!.next;
      previous!.next = newNode;
      if (position === this.length) this.tail = newNode;
    }
    this.length++;
    return true;
  }

removeAt 重构

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
// 删除指定元素
  removeAt(position: number): T | null {
    // 越界
    if (position < 0 || position > this.size) return null;
    let current = this.head;
    let remove: Node<T> | null = null;
    // 删除head
    if (position === 0) {
      this.head = current?.next ?? null;
      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      }
    } else {
      const previous = this.getNode(position - 1);
      remove = previous!.next;
      previous!.next = previous?.next?.next ?? null;

      if (position === this.length - 1) {
        this.tail = previous;
      }
    }
    this.length--;
    return remove?.val ?? null;
  }

indexOf 重构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
indexOf(value: T): number {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.val === value) return index;
      if (this.isTail(current)) {
        current = null;
      } else {
        current = current.next;
      }
      index++;
    }
    return -1;
  }

循环链表实现

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
import LinkedList from "./01_单向链表-重构";

class CircularirLinkList<T> extends LinkedList<T> {
  append(value: T) {
    super.append(value);
    this.tail!.next = this.head;
  }
  traverse(): string {
    return super.traverse();
  }
  insert(value: T, position: number): boolean {
    const isSuccess = super.insert(value, position);
    // 因为insert执行成功 this.length++ 所以这里position === this.length - 1
    if ((isSuccess && position === 0) || position === this.length - 1) {
      this.tail!.next = this.head;
    }
    return isSuccess;
  }
  removeAt(position: number): T | null {
    const value = super.removeAt(position);
    if ((value && this.tail && position === 0) || position === this.length) {
      this.tail!.next = this.head;
    }
    return value;
  }
  indexOf(value: T): number {
    return super.indexOf(value);
  }
  isEmpty(): boolean {
    return super.isEmpty();
  }
  remove(value: T): T | null {
    return super.remove(value);
  }

  update(value: T, position: number): boolean {
    return super.update(value, position);
  }
}
const cLinkList = new CircularirLinkList();
cLinkList.append("AAA");
cLinkList.append("BBB");

cLinkList.append("CCC");
cLinkList.append("DDD");

cLinkList.insert("EEE", 4);
cLinkList.insert("000", 0);
cLinkList.removeAt(6);
console.log(cLinkList.indexOf("000"));
console.log(cLinkList.indexOf("111"));
console.log(cLinkList.isEmpty());
cLinkList.remove("000");
cLinkList.update("JJJ", 2);
console.log(cLinkList.traverse());