扬舲blog

数据结构和算法是编程的内功，深厚的内功可以有效保障写出的代码性能良好，可以提前预估代码运行达到预期目的，提高工作产出，也能让学习其他编程语言和框架变得事半功倍。

本系列所有示例均采用JavaScript，旨在入门数据结构与算法。

本节主要是讲解下基础数据结构 - 线性表 相关的内容。

线性表 与 非线性表

线性表（Linear List）：就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。数组、链表、队列、栈 等就是典型线性表结构。

非线性表：数据之间并不是简单的前后关系。二叉树、堆、图 就是非线性表。

数组

  • 定义
    数组 (Array) 是一个有序的数据集合，我们可以通过数组名称 (name) 和索引 (index) 进行访问。
    数组的索引是从 0 开始的。

  • 特点
    数组是用一组连续的内存空间来存储的。 所以数组支持 随机访问，根据下标随机访问的时间复杂度为 O(1)。

低效的插入和删除。 数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效，因为底层通常是要进行大量的数据搬移来保持数据的连续性。 插入与删除的时间复杂度如下： 插入：从最好 O(1) ，最坏 O(n) ，平均 O(n) 删除：从最好 O(1) ，最坏 O(n) ，平均 O(n)

  • 实现
    JavaScript 原生支持数组，而且提供了很多操作方法，JavaScript数组支持的方法可见下表：
方法 描述
concat() 连接两个或更多的数组，并返回结果。
copyWithin() 从数组的指定位置拷贝元素到数组的另一个指定位置中。
entries() 返回数组的可迭代对象。
every() 检测数值元素的每个元素是否都符合条件。
fill() 使用一个固定值来填充数组。
filter() 检测数值元素，并返回符合条件所有元素的数组。
find() 返回符合传入测试（函数）条件的数组元素。
findIndex() 返回符合传入测试（函数）条件的数组元素索引。
forEach() 数组每个元素都执行一次回调函数。
from() 通过给定的对象中创建一个数组。
includes() 判断一个数组是否包含一个指定的值。
indexOf() 搜索数组中的元素，并返回它所在的位置。
isArray() 判断对象是否为数组。
join() 把数组的所有元素放入一个字符串。
keys() 返回数组的可迭代对象，包含原始数组的键(key)。
lastIndexOf() 搜索数组中的元素，并返回它最后出现的位置。
map() 通过指定函数处理数组的每个元素，并返回处理后的数组。
pop() 删除数组的最后一个元素并返回删除的元素。
push() 向数组的末尾添加一个或更多元素，并返回新的长度。
reduce() 将数组元素计算为一个值（从左到右）。
reduceRight() 将数组元素计算为一个值（从右到左）。
reverse() 反转数组的元素顺序。
shift() 删除并返回数组的第一个元素。
slice() 选取数组的的一部分，并返回一个新数组。
some() 检测数组元素中是否有元素符合指定条件。
sort() 对数组的元素进行排序。
splice() 从数组中添加或删除元素。
toString() 把数组转换为字符串，并返回结果。
unshift() 向数组的开头添加一个或更多元素，并返回新的长度。
valueOf() 返回数组对象的原始值。

栈

  • 定义
    • 后进者先出，先进者后出，简称 后进先出（LIFO），这就是典型的栈结构。
    • 在栈里，新元素都靠近栈顶，旧元素都接近栈底。
    • 从栈的操作特性来看，是一种 操作受限的线性表，只允许在一端插入和删除数据。
    • 不包含任何元素的栈称为空栈。

栈被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈、前端路由等。

  • 实现
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
function Stack() {
  this.data = [];

  /**
   * 添加一个（或几个）新元素到栈顶。
   */
  this.push = function (element) {
    this.data.push(element);
  };
  /**
   * 移除栈顶的元素，同时返回被移除的元素。
   */
  this.pop = function () {
    return this.data.pop();
  };
  /**
   * 返回栈顶的元素，不对栈做任何修改。
   */
  this.peek = function () {
    return this.data[this.data.length - 1];
  };
  /**
   * 如果栈里没有任何元素就返回 true，否则返回 false
   */
  this.isEmpty = function () {
    return this.data.length === 1;
  };
  /**
   * 移除栈里的所有元素
   */
  this.clear = function () {
    this.data = [];
  };
  /**
   * 返回栈里的元素个数。
   */
  this.size = function () {
    return this.data.length;
  };
  // 打印栈里的元素
  this.print = function () {
    console.log(this.data.toString());
  };
}
  • 使用场景

举一个判断回文的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function isPalindrome(word) {
  var s = new Stack();
  for (var i = 0; i < word.length; i++) {
    s.push(word[i]);
  }
  var rword = "";
  while (s.length() > 0) {
    rword += s.pop();
  }

  return word == rword;
}

console.log(isPalindrome("level")); // true
console.log(isPalindrome("1001")); // true
console.log(isPalindrome("word")); // false

队列

  • 定义
    • 队列是遵循 FIFO（First In First Out，先进先出）原则的一组有序的项。
    • 队列在尾部添加新元素，并从顶部移除元素。
    • 最新添加的元素必须排在队列的末尾。
    • 队列只有 入队 push() 和出队 pop()。
    • 队列又可以细分为普通队列、优先队列、循环队列。

普通队列

  • 实现
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
// Queue类
function Queue() {
  this.data = [];

  // 向队列尾部添加元素
  this.enqueue = function (element) {
    this.data.push(element);
  };

  // 移除队列的第一个元素，并返回被移除的元素
  this.dequeue = function () {
    return this.data.shift();
  };

  // 返回队列的第一个元素
  this.front = function () {
    return this.data[0];
  };

  // 判断是否为空队列
  this.isEmpty = function () {
    return this.data.length === 0;
  };

  // 获取队列的长度
  this.size = function () {
    return this.data.length;
  };

  // 清空队列
  this.clear = function () {
    this.data = [];
  };

  // 打印队列里的元素
  this.print = function () {
    console.log(this.data.toString());
  };
}

优先队列

  • 定义
    优先队列中元素的添加和移除会根据优先级来处理

  • 场景
    优先队列一个典型的场景就是机场登机，头等舱和商务舱乘客的优先级要高于经济舱乘客。

  • 分类

    • 最小优先队列，优先级值越小的元素在越前面
    • 最大优先队列，优先级值越大的元素在越前面

  • 实现
    实现最小优先队列

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
// MinPriorityQueue类
function MinPriorityQueue() {
  this.data = [];

  // 向队列尾部添加元素
  this.enqueue = function (element, priority) {
    //若队列为空则直接将元素入列，否则需要比较该元素与其他元素的优先级
    if (this.isEmpty()) {
      this.data.push({ element, priority });
    } else {
      let added = false;
      for (let i = 0, length = this.size(); i < length; i++) {
        if (priority < this.data[i].priority) {
          this.data.splice(i, 0, { element, priority });
          added = true;
          break;
        }
      }
      if (!added) {
        this.data.push({ element, priority });
      }
    }
  };

  // 移除队列的第一个元素，并返回被移除的元素
  this.dequeue = function () {
    return this.data.shift();
  };

  // 返回队列的第一个元素
  this.front = function () {
    return this.data[0];
  };

  // 判断是否为空队列
  this.isEmpty = function () {
    return this.data.length === 0;
  };

  // 获取队列的长度
  this.size = function () {
    return this.data.length;
  };

  // 清空队列
  this.clear = function () {
    this.data = [];
  };

  // 打印队列里的元素
  this.print = function () {
    const info = this.data.map((item) => `${item.priority}: ${item.element}`);
    console.log(info.toString());
  };
}

实现最大优先队列

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
// MaxPriorityQueue类
function MaxPriorityQueue() {
  this.data = [];

  // 向队列尾部添加元素
  this.enqueue = function (element, priority) {
    //若队列为空则直接将元素入列，否则需要比较该元素与其他元素的优先级
    if (this.isEmpty()) {
      this.data.push({ element, priority });
    } else {
      let added = false;
      for (let i = 0, length = this.size(); i < length; i++) {
        if (priority > this.data[i].priority) {
          this.data.splice(i, 0, { element, priority });
          added = true;
          break;
        }
      }
      if (!added) {
        this.data.push({ element, priority });
      }
    }
  };

  // 移除队列的第一个元素，并返回被移除的元素
  this.dequeue = function () {
    return this.data.shift();
  };

  // 返回队列的第一个元素
  this.front = function () {
    return this.data[0];
  };

  // 判断是否为空队列
  this.isEmpty = function () {
    return this.data.length === 0;
  };

  // 获取队列的长度
  this.size = function () {
    return this.data.length;
  };

  // 清空队列
  this.clear = function () {
    this.data = [];
  };

  // 打印队列里的元素
  this.print = function () {
    const info = this.data.map((item) => `${item.priority}: ${item.element}`);
    console.log(info.toString());
  };
}

循环队列

循环队列的一个例子就是击鼓传花游戏（Hot Potato）。在这个游戏中，孩子们围城一个圆圈，击鼓的时候把花尽快的传递给旁边的人。某一时刻击鼓停止，这时花在谁的手里，谁就退出圆圈直到游戏结束。重复这个过程，直到最后一个孩子为最后胜利者。

基于上面的普通队列，实现这个游戏：

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

// 实现击鼓传花
function hotPotato(nameList, num) {
  var queue = new Queue();

  for (var i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }

  var eliminated = "";

  while (queue.size() > 1) {
    // 循环 num 次，队首出来去到队尾
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    // 循环 num 次过后，移除当前队首的元素
    eliminated = queue.dequeue();
    console.log(`${eliminated} 在击鼓传花中被淘汰！`);
  }

  // 最后只剩一个元素
  return queue.dequeue();
}

// 测试
var nameList = ["张三", "李四", "王五", "马六", "牛七"];
var winner = hotPotato(nameList, 5);
console.log(`最后的胜利者是：${winner}`);

// => 牛七 在击鼓传花中被淘汰！
// => 张三 在击鼓传花中被淘汰！
// => 王五 在击鼓传花中被淘汰！
// => 马六 在击鼓传花中被淘汰！
// => 最后的胜利者是：李四

链表

  • 定义
    链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的，它是通过 指针 将 零散的内存块 串连起来的。

每个元素由一个存储元素本身的 节点和一个指向下一个元素的 指针组成。

简单的链接结构图:

上图中，data 中保存着数据，next 保存着下一个链表的指针。 上图中，我们说 data2 跟在 data1 后面，而不是说 data2 是链表中的第二个元素。需要注意的是，我们将链表的尾元素指向了 null 节点，表示链接结束的位置。

  • 特点

    • 低效的访问： 链表是通过指针将零散的内存块串连起来的。 所以链表不支持 随机访问，如果要找特定的项，只能从头开始遍历，直到找到某个项。 所以访问的时间复杂度为 O(n)。

    • 高效的插入和删除。 链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移节点，因为链表的存储空间本身就不是连续的，只需要考虑相邻节点的指针改变。 所以，在链表中插入和删除一个数据是非常快速的，时间复杂度为 O(1)。

  • 分类
    常见列表可以分为三类：

    • 单向链表
    • 双向链表
    • 循环链表

单向链表

  • 定义

由于链表的起始点的确定比较麻烦，因此很多链表的实现都会在链表的最前面添加一个特殊的节点，称为 头节点，表示链表的头部。

  • 特点

    • 只能单向遍历，操作灵活性不高

  • 实现

需要实现的以下常用操作：

方法名 描述
append(element) 尾部添加元素。
insert(position, element) 特定位置插入一个新的项。
removeAt(position) 特定位置移除一项。
remove(element) 移除一项。
indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素则返回 -1。
isEmpty() 如果链表中不包含任何元素，返回 true，如果链表长度大于 0，返回 false。
size() 返回链表包含的元素个数，与数组的 length 属性类似。
getHead() 返回链表的第一个元素。
toString() 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值。
print() 打印链表的所有元素。
list() 获取整个链表 
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
// 单链表
function SinglyLinkedList() {
  // 节点
  function Node(element) {
    this.element = element; // 当前节点的元素
    this.next = null; // 下一个节点指针
  }

  let length = 0; // 链表的长度
  let head = null; // 链表的头节点

  // 向链表尾部添加一个新的节点
  this.append = function (element) {
    let node = new Node(element);

    // 判断是否为空链表
    if (head === null) {
      // 是空链表，就把当前节点作为头部节点
      head = node;
    } else {
      let currentNode = head;
      // 从 head 开始一直找到最后一个 node
      while (currentNode.next) {
        // 后面还有 node
        currentNode = currentNode.next;
      }
      // 把最后一个节点的 next 指针指向新的节点
      currentNode.next = node;
    }
    // 链表的长度加 1
    length++;
  };

  // 向链表特定位置插入一个新节点
  this.insert = function (position, element) {
    if (position < 0 || position > length) {
      // 越界
      return false;
    } else {
      let node = new Node(element);
      let index = 0;
      let currentNode = head;
      let previousNode;

      // 在最前插入节点
      if (position === 0) {
        node.next = currentNode;
        head = node;
      } else {
        // 循环找到位置
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        // 把前一个节点的指针指向新节点，新节点的指针指向当前节点，保持连接性
        previousNode.next = node;
        node.next = currentNode;
      }

      length++;

      return true;
    }
  };

  // 从链表的特定位置移除一项
  this.removeAt = function (position) {
    if ((position < 0 || position >= length) || length === 0) {
      // 越界
      return false;
    } else {
      let currentNode = head;
      let index = 0;
      let previousNode;

      if (position === 0) {
        head = currentNode.next;
      } else {
        // 循环找到位置
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        // 把当前节点的 next 指针 指向 当前节点的 next 指针，即是 删除了当前节点
        previousNode.next = currentNode.next;
      }

      length--;

      return true;
    }
  };

  // 从链表中移除指定项
  this.remove = function (element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  };

  // 返回元素在链表的索引，如果链表中没有该元素则返回 -1
  this.indexOf = function (element) {
    let currentNode = head;
    let index = 0;

    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }

      index++;
      currentNode = currentNode.next;
    }

    return -1;
  };

  // 如果链表中不包含任何元素，返回 true，如果链表长度大于 0，返回 false
  this.isEmpty = function () {
    return length === 0;
  };

  // 返回链表包含的元素个数，与数组的 length 属性类似
  this.size = function () {
    return length;
  };

  // 获取链表头部元素
  this.getHead = function () {
    return head.element;
  };

  // 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值
  this.toString = function (cur) {
    let currentNode = cur || head;
    let string = "";

    while (currentNode) {
      string += "," + currentNode.element;
      currentNode = currentNode.next;
    }

    return string.slice(1);
  };

  // 打印链表数据
  this.print = function (cur) {
    console.log(this.toString(cur));
  };

  // 获取整个链表
  this.list = function () {
    console.log("head: ", head);
    return head;
  };
}

双向链表

上面说的单向链表只有一个方向，节点只有一个后继指针 next 指向后面的节点。

最为对比，双向链表就有两个方向的指针，每个节点不止有一个后继指针 next 指向后面的节点，还有一个前驱指针 prev 指向前面的节点。

  • 与单向列表比较

    • 内存空间比单向链表大，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址
    • 可以双向操作，灵活性更高，查找/插入/删除更高效

  • 实现
    在实现了单向链表后，双向链表就没那么难了，直接上代码：

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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
// 创建双向链表 DoublyLinkedList 类
function DoublyLinkedList() {
  function Node(element) {
    this.element = element; //当前节点的元素
    this.next = null; //下一个节点指针
    this.previous = null; //上一个节点指针
  }

  let length = 0; // 链表长度
  let head = null; // 链表头部
  let tail = null; // 链表尾部

  // 向链表尾部添加一个新的项
  this.append = function (element) {
    let node = new Node(element);
    let currentNode = tail;

    // 判断是否为空链表
    if (currentNode === null) {
      // 空链表
      head = node;
      tail = node;
    } else {
      currentNode.next = node;
      node.previous = currentNode;
      tail = node;
    }

    length++;
  };

  // 向链表特定位置插入一个新的项
  this.insert = function (position, element) {
    if (position < 0 || position > length) {
      // 越界
      return false;
    } else {
      let node = new Node(element);
      let index = 0;
      let currentNode = head;
      let previousNode;
      if (position === 0) {
        //在头部添加
        if (!head) {
          head = node;
          tail = node;
        } else {
          node.next = currentNode;
          currentNode.previous = node;
          head = node;
        }
      } else if (position === length) {
        //在末尾添加
        this.append(element);
        return true;
      } else if (length - 1 - position > position) {
        //position离head更近
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }

        previousNode.next = node;
        node.next = currentNode;

        node.previous = previousNode;
        currentNode.previous = node;
      } else {
        //position离tail更近，则从tail开始向前查找
        index = length - 1;
        currentNode = tail;

        while (index > position) {
          index--;
          currentNode = currentNode.previous;
          previousNode = currentNode.previous;
        }

        previousNode.next = node;
        node.next = currentNode;
        node.previous = previousNode;
        currentNode.previous = node;
      }

      length++;

      return true;
    }
  };

  // 从链表的特定位置移除一项
  this.removeAt = function (position) {
    if (position < 0 || position >= length || length === 0) {
      // 越界
      return false;
    } else {
      let currentNode = head;
      let index = 0;
      let previousNode;
      if (position === 0) {
        // 移除第一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          head = currentNode.next;
          head.previous = null;
        }
      } else if (position === length - 1) {
        // 移除最后一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          currentNode = tail;
          tail = currentNode.previous;
          tail.next = null;
        }
      } else if (length - 1 - position > position) {
        //position离head更近
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
        currentNode.next.previous = previousNode;
      } else {
        //position离tail更近，则从tail开始向前查找
        index = length - 1;
        currentNode = tail;

        while (index > position) {
          index--;
          currentNode = currentNode.previous;
          previousNode = currentNode.previous;
        }
        previousNode.next = currentNode.next;
        currentNode.next.previous = previousNode;
      }

      length--;

      return true;
    }
  };

  // 从链表中移除指定项
  this.remove = function (element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  };

  // 返回元素在链表的索引，如果链表中没有该元素则返回 -1
  this.indexOf = function (element) {
    let currentNode = head;
    let index = 0;

    let currentNode2 = tail;
    let index2 = length - 1;

    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }
      if (currentNode2.element === element) {
        return index2;
      }

      index++;
      currentNode = currentNode.next;
      index2--;
      currentNode2 = currentNode2.previous;
    }
    return -1;
  };

  // 如果链表中不包含任何元素，返回 true ，如果链表长度大于 0 ，返回 false
  this.isEmpty = function () {
    return length == 0;
  };

  // 返回链表包含的元素个数，与数组的 length 属性类似
  this.size = function () {
    return length;
  };

  // 获取链表头部元素
  this.getHead = function () {
    return head.element;
  };

  // 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值
  this.toString = function () {
    let currentNode = head;
    let string = "";

    while (currentNode) {
      string += "," + currentNode.element;
      currentNode = currentNode.next;
    }

    return string.slice(1);
  };

  this.print = function () {
    console.log(this.toString());
  };

  // 获取整个链表
  this.list = function () {
    console.log("head: ", head);
    return head;
  };
}

单向链表 VS 双向链表 性能对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let singlyList = new SinglyLinkedList();
console.time("singlyList-time");
for (let i = 0; i < 100000; i++) {
  singlyList.insert(i, "Tom" + i);
}
console.timeEnd("singlyList-time");


let doublyList = new DoublyLinkedList();
console.time("doublyLinked-time");
for (let i = 0; i < 100000; i++) {
  doublyList.insert(i, "Tom" + i);
}
console.timeEnd("doublyList-time");

// >> singlyList-time: 34532.815ms
// >> doublyList-time: 64.111ms

结论： 同样插入100000条数据，双向链表的速度优势明显；

循环链表

循环链表是一种特殊的单链表。 循环链表和单链表相似，节点类型都是一样。 唯一的区别是，循环链表的尾节点指向了头节点，形成了一个循环。如下图所示:

  • 实现
    基于单向链表实现循环链表，主要区别在于要将循环链表的尾节点指向头节点
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
// 循环链表
function CircularLinkedList() {
  // 节点
  function Node(element) {
    this.element = element; // 当前节点的元素
    this.next = null; // 下一个节点指针
  }

  let length = 0; // 链表的长度
  let head = null; // 链表的头节点
  let tail = null; // 链表的尾节点

  // 向链表尾部添加一个新的节点
  this.append = function (element) {
    let node = new Node(element);

    // 判断是否为空链表
    if (head === null) {
      // 是空链表，就把当前节点作为头部节点
      head = node;
      head.next = head;
      tail = head;//区别于单向链表的点
    } else {
      let currentNode = head;
      // 从 head 开始一直找到最后一个 node
      while (currentNode.next !== head) {
        // 后面还有 node
        currentNode = currentNode.next;
      }
      // 把最后一个节点的 next 指针指向新的节点
      currentNode.next = node;
      // 把新插入的节点的next指向head
      node.next = head;
      tail = node; // 把新加入的节点设为尾节点
    }
    // 链表的长度加 1
    length++;
  };

  // 向链表特定位置插入一个新节点
  this.insert = function (position, element) {
    if (position < 0 || position > length) {
      // 越界
      return false;
    } else if (length === 0) {
       //空链表时使用append插入第一个节点
      this.append(element);
    } else {
      let node = new Node(element);
      let index = 0;
      let currentNode = head;
      let previousNode;

      // 在最前插入节点
      if (position === 0) {
        node.next = head;
        head = node;
        tail.next = head; //区别于单向链表的点
      } else {
        // 循环找到位置
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        // 把前一个节点的指针指向新节点，新节点的指针指向当前节点，保持连接性
        previousNode.next = node;
        node.next = currentNode;
      }

      length++;

      return true;
    }
  };

  // 从链表的特定位置移除一项
  this.removeAt = function (position) {
    if (position < 0 || position >= length || length === 0) {
      // 越界
      return false;
    } else {
      let currentNode = head;
      let index = 0;
      let previousNode;

      if (position === 0) {
        head = head.next;
        tail.next = head; //区别于单向链表的点
      } else {
        // 循环找到位置
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        // 把当前节点的 next 指针 指向 当前节点的 next 指针，即是 删除了当前节点
        previousNode.next = currentNode.next;
      }

      length--;

      return true;
    }
  };

  // 从链表中移除指定项
  this.remove = function (element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  };

  // 返回元素在链表的索引，如果链表中没有该元素则返回 -1
  this.indexOf = function (element) {
    let currentNode = head;
    let index = 0;

    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }

      index++;
      currentNode = currentNode.next;
    }

    return -1;
  };

  // 如果链表中不包含任何元素，返回 true，如果链表长度大于 0，返回 false
  this.isEmpty = function () {
    return length === 0;
  };

  // 返回链表包含的元素个数，与数组的 length 属性类似
  this.size = function () {
    return length;
  };

  // 获取链表头部元素
  this.getHead = function () {
    return head.element;
  };

  // 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值
  this.toString = function () {
    let currentNode = head;
    let string = "";
    let index = 0;

    while (currentNode && index < length) {
      string += "," + currentNode.element;
      currentNode = currentNode.next;
      index++;
    }

    return string.slice(1);
  };

  // 打印链表数据
  this.print = function (cur) {
    console.log(this.toString(cur));
  };

  // 获取整个链表
  this.list = function () {
    console.log("head: ", head);
    return head;
  };
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://blog.kobingo.xyz/algorithms-%E7%BA%BF%E6%80%A7%E8%A1%A8%E5%9F%BA%E7%A1%80%E6%B1%87%E6%80%BB/

评论