循环链表 – 双向链表

认识循环链表

前面我们已经从零去封装了一个链表结构，其实我们还可以封装更灵活的链表结构：循环链表和双向链表。

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

在普通链表的基础上，最后一个节点的下一个节点不再是 null，而是指向链表的第一个节点。
这样形成了一个环，使得链表能够被无限遍历。
这样，我们就可以在单向循环链表中从任意一个节点出发，不断地遍历下一个节点，直到回到起点。

单向循环链表我们有两种实现方式：

方式一：从零去实现一个新的链表，包括其中所有的属性和方法；
方式二：继承自之前封装的 LinkedList，只实现差异化的部分；

重构 LinkedList（方便继承）

1.修饰符改成 protected

2.添加 tail 指向尾部节点

append 方法：
- ✓ this.tail.next = newNode
- ✓ this.tail = newNode
insert 方法：判断是否是插入最后一个节点
removeAt 方法：
- ✓ this.length === 1
  - ➢ this.tail = null
  - ➢ this.head = null
- ✓ position === length – 1
  - ➢ this.tail = previous

append 重构

insert 重构

removeAt 重构

新增判断最后节点方法

添加判断是否是最后一个节点

实现 append 方法

重构 traverse 方法

实现 insert 方法

实现 removeAt 方法

重构 indexOf 方法

双向链表的结构

双向链表:

既可以从头遍历到尾, 又可以从尾遍历到头.
也就是链表相连的过程是双向的. 那么它的实现原理, 你能猜到吗?
一个节点既有向前连接的引用 prev, 也有一个向后连接的引用 next. 双向链表有什么缺点呢?
每次在插入或删除某个节点时, 需要处理四个引用, 而不是两个. 也就是实现起来要困难一些
并且相当于单向链表, 必然占用内存空间更大一些.
但是这些缺点和我们使用起来的方便程度相比, 是微不足道的.

双向链表的画图

双向链表的节点封装

双向链表的节点，需要进一步添加一个 prev 属性，用于指向前一个节点：

双向链表的实现

双向链表中添加、删除方法的实现和单向链表有较大的区别，所以我们可以对其方法进行重新实现：

append方法：在尾部追加元素
prepend方法：在头部添加元素
postTraverse方法：从尾部遍历所有节点
insert方法：根据索引插入元素
removeAt方法：根据索引删除元素 那么接下来我们就一个个实现这些方法，其他方法都是可以继承的。

append 方法

prepend 方法

insert 方法

removeAt

typescript

// 08_高阶链表结构/LinkedNode.ts

// 1.创建Node节点类
export class Node<T> {
  value: T;
  next: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

export class DoublyNode<T> extends Node<T> {
  prev: DoublyNode<T> | null = null;
  next: DoublyNode<T> | null = null;
}

typescript

// types/IList.ts

export default interface IList<T> {
  // peek
  peek(): T | undefined;
  // 判断是否为空
  isEmpty(): boolean;
  // 元素的个数
  size(): number;
}

typescript

// 08_高阶链表结构/ILinkedList.ts

import IList from "../types/IList";

interface ILinkedList<T> extends IList<T> {
  append(value: T): void;
  traverse(): void;
  insert(value: T, position: number): boolean;
  removeAt(position: number): T | null;
  get(positon: number): T | null;
  update(value: T, position: number): boolean;
  indexOf(value: T): number;
  remove(value: T): T | null;
}

export default ILinkedList;

typescript

// 08_高阶链表结构/01_实现单向链表LinkedList.ts

import ILinkedList from "./ILinkedList";
import { Node } from "./LinkedNode";

// 2.创建LinkedList的类
export default class LinkedList<T> implements ILinkedList<T> {
  protected head: Node<T> | null = null;
  protected length: number = 0;

  // 新增属性: 总是指向链表的尾部
  protected tail: Node<T> | null = null;

  size() {
    return this.length;
  }

  peek(): T | undefined {
    return this.head?.value;
  }

  // 封装私有方法
  // 根据position获取到当前的节点(不是节点的value, 而是获取节点)
  protected getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current.next;
    }
    return current;
  }

  // 判断是否是最后一个节点
  private isTail(node: Node<T>) {
    return this.tail === node;
  }

  // 追加节点
  append(value: T) {
    // 1.根据value创建一个新节点
    const newNode = new Node(value);

    // 2.判断this.head是否为null
    if (!this.head) {
      this.head = newNode;
    } else {
      this.tail!.next = newNode;
    }
    this.tail = newNode;

    // 3.size++
    this.length++;
  }

  // 遍历链表的方法
  traverse() {
    const values: T[] = [];

    let current = this.head;
    while (current) {
      values.push(current.value);
      if (this.isTail(current)) {
        // 已经遍历最后一个接地那
        current = null;
      } else {
        // 不是最后一个节点
        current = current.next;
      }
    }

    // 循环链表
    if (this.head && this.tail?.next === this.head) {
      values.push(this.head.value);
    }

    console.log(values.join("->"));
  }

  // 插入方法:
  insert(value: T, position: number): boolean {
    // 1.越界的判断
    if (position < 0 || position > this.length) return false;

    // 2.根据value创建新的节点
    const newNode = new Node(value);

    // 3.判断是否需要插入头部
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } 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(position: number): T | null {
    // 1.越界的判断
    if (position < 0 || position >= this.length) return null;

    // 2.判断是否是删除第一个节点
    let current = this.head;
    if (position === 0) {
      this.head = current?.next ?? null;

      if (this.length === 1) {
        this.tail = null;
      }
    } else {
      const previous = this.getNode(position - 1);
      current = previous!.next;
      previous!.next = previous?.next?.next ?? null;

      if (position === this.length - 1) {
        this.tail = previous;
      }
    }

    this.length--;

    return current?.value ?? null;
  }

  // 获取方法:
  get(position: number): T | null {
    // 越界问题
    if (position < 0 || position >= this.length) return null;

    // 2.查找元素, 并且范围元素
    return this.getNode(position)?.value ?? null;
  }

  // 更新方法:
  update(value: T, position: number): boolean {
    if (position < 0 || position >= this.length) return false;
    // 获取对应位置的节点, 直接更新即可
    const currentNode = this.getNode(position);
    currentNode!.value = value;
    return true;
  }

  // 根据值, 获取对应位置的索引
  indexOf(value: T): number {
    // 从第一个节点开始, 向后遍历
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.value === value) {
        return index;
      }

      if (this.isTail(current)) {
        current = null;
      } else {
        current = current.next;
      }

      index++;
    }

    return -1;
  }

  // 删除方法: 根据value删除节点
  remove(value: T): T | null {
    const index = this.indexOf(value);
    return this.removeAt(index);
  }

  // 判读单链表是否为空的方法
  isEmpty() {
    return this.length === 0;
  }
}

export {};

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

typescript

// 08_高阶链表结构/双向链表DoublyLinkedList.ts

import LinkedList from "./01_实现单向链表LinkedList";
import { DoublyNode } from "./LinkedNode";

class DoublyLinkedList<T> extends LinkedList<T> {
  protected head: DoublyNode<T> | null = null;
  protected tail: DoublyNode<T> | null = null;

  append(value: T): void {
    const newNode = new DoublyNode(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      // 不能将一个父类的对象, 赋值给一个子类的类型
      // 可以将一个子类的对象, 赋值给一个父类的类型(多态)
      newNode.prev = this.tail;
      this.tail = newNode;
    }

    this.length++;
  }
  // 新的方法
  prepend(value: T): void {
    const newNode = new DoublyNode(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }

    this.length++;
  }

  postTraverse() {
    const values: T[] = [];
    let current = this.tail;
    while (current) {
      values.push(current.value);
      current = current.prev;
    }

    console.log(values.join("->"));
  }

  // 根据索引插入元素
  insert(value: T, position: number): boolean {
    if (position < 0 && position > this.length) return false;

    if (position === 0) {
      this.prepend(value);
    } else if (position === this.length) {
      this.append(value);
    } else {
      const newNode = new DoublyNode(value);
      const current = this.getNode(position) as DoublyNode<T>;

      current.prev!.next = newNode;
      newNode.next = current;
      newNode.prev = current.prev;
      current.prev = newNode;

      this.length++;
    }

    return true;
  }

  // 根据索引删除元素
  removeAt(position: number): T | null {
    if (position < 0 || position >= this.length) return null;

    let current = this.head;
    if (position === 0) {
      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      } else {
        this.head = this.head!.next;
        this.head!.prev = null;
      }
    } else if (position === this.length - 1) {
      current = this.tail;
      this.tail = this.tail!.prev;
      this.tail!.next = null;
    } else {
      current = this.getNode(position) as DoublyNode<T>;
      current.next!.prev = current.prev;
      current.prev!.next = current.next;
    }

    this.length--;

    return current?.value ?? null;
  }
}

// 测试append方法
console.log("-------------- append/prepend --------------");
const dLinkedList = new DoublyLinkedList<string>();
dLinkedList.append("aaa");
dLinkedList.append("bbb");
dLinkedList.append("ccc");
dLinkedList.append("ddd");

dLinkedList.prepend("abc");
dLinkedList.prepend("cba");

dLinkedList.traverse();
dLinkedList.postTraverse();

console.log("-------------- insert --------------");
dLinkedList.insert("why", 0);
dLinkedList.insert("kobe", 7);
dLinkedList.insert("james", 3);
dLinkedList.traverse();
dLinkedList.postTraverse();

console.log("-------------- removeAt --------------");
dLinkedList.removeAt(0);
dLinkedList.removeAt(7);
dLinkedList.removeAt(2);
dLinkedList.traverse();
dLinkedList.postTraverse();

console.log("------------ 测试get ------------");
console.log(dLinkedList.get(0));
console.log(dLinkedList.get(1));
console.log(dLinkedList.get(2));

console.log("------------ 测试update ------------");
dLinkedList.update("why", 1);
dLinkedList.update("kobe", 2);
dLinkedList.traverse();

console.log("------------ 测试indexOf ------------");
console.log(dLinkedList.indexOf("cba"));
console.log(dLinkedList.indexOf("why"));
console.log(dLinkedList.indexOf("kobe"));
console.log(dLinkedList.indexOf("james"));

console.log("------------ 测试remove ------------");
dLinkedList.remove("why");
dLinkedList.remove("cba");
dLinkedList.remove("kobe");
dLinkedList.traverse();
console.log(dLinkedList.isEmpty());
console.log(dLinkedList.size());

循环链表 – 双向链表 ​

认识循环链表 ​

重构 LinkedList（方便继承） ​

append 重构 ​

insert 重构 ​

removeAt 重构 ​

新增判断最后节点方法 ​

实现 append 方法 ​

重构 traverse 方法 ​

实现 insert 方法 ​

实现 removeAt 方法 ​

重构 indexOf 方法 ​

双向链表的结构 ​

双向链表的画图 ​

双向链表的节点封装 ​

双向链表的实现 ​

append 方法 ​

prepend 方法 ​

insert 方法 ​

removeAt ​

循环链表 – 双向链表

认识循环链表

重构 LinkedList（方便继承）

append 重构

insert 重构

removeAt 重构

新增判断最后节点方法

实现 append 方法

重构 traverse 方法

实现 insert 方法

实现 removeAt 方法

重构 indexOf 方法

双向链表的结构

双向链表的画图

双向链表的节点封装

双向链表的实现

append 方法

prepend 方法

insert 方法

removeAt