首发于全栈修炼

JavaScript 数据结构与算法之美 - 线性表（数组、栈、队列、链表）

夜尽天明

前言

基础知识就像是一座大楼的地基，它决定了我们的技术高度。
我们应该多掌握一些可移值的技术或者再过十几年应该都不会过时的技术，数据结构与算法就是其中之一。

栈、队列、链表、堆是数据结构与算法中的基础知识，是程序员的地基。

笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。

1. 线性表与非线性表

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

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

本文主要讲线性表，非线性表会在后面章节讲。

2. 数组

定义

特点

注意

但是因为 JavaScript 是弱类型的语言，弱类型则允许隐式类型转换。

隐式：是指源码中没有明显的类型转换代码。也就是说，一个变量，可以赋值字符串，也可以赋值数值。

let str = "string"
str = 123 
console.log(str)  //   123

你还可以直接让字符串类型的变量和数值类型的变量相加，虽然得出的最终结果未必是你想象的那样，但一定不会报错。

let a = 123
let b = "456"
let c = a + b
// 数值加字符串，结果是字符串
console.log(c)  //   "123456"

数组的每一项可以是不同的类型，比如：

// 数组的类型有 数值、字符串，还可以随意变更类型
const arr = [ 12, 34, "abc" ]
arr[2] = { "key": "value" }  // 把数组的第二项变成对象
console.log(arr) //  [ 12, 34,  { "key": "value"} ]

定义的数组的大小是可变的，不像强类型语言，定义某个数组变量的时候就要定义该变量的大小。

const arr = [ 12, 34, "abc"] 
arr.push({ "key": "value" }) // 添加一项 对象
consolelog(arr) //  [ 12, 34, "abc", { "key": "value" } ]

实现

JavaScript 原生支持数组，而且提供了很多操作方法，这里不展开讲。

3. 栈

定义

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

实现

栈的方法：

// Stack类
function Stack() {
  this.items = [];

  // 添加新元素到栈顶
  this.push = function(element) {
    this.items.push(element);
  };
  // 移除栈顶元素，同时返回被移除的元素
  this.pop = function() {
    return this.items.pop();
  };
  // 查看栈顶元素
  this.peek = function() {
    return this.items[this.items.length - 1];
  };
  // 判断是否为空栈
  this.isEmpty = function() {
    return this.items.length === 0;
  };
  // 清空栈
  this.clear = function() {
    this.items = [];
  };
  // 查询栈的长度
  this.size = function() {
    return this.items.length;
  };
  // 打印栈里的元素
  this.print = function() {
    console.log(this.items.toString());
  };
}

测试：

// 创建Stack实例
var stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5); // undefined
stack.push(8); // undefined
console.log(stack.peek()); // 8
stack.push(11); // undefined
console.log(stack.size()); // 3
console.log(stack.isEmpty()); // false
stack.push(15); // undefined
stack.pop(); // 15
console.log(stack.size()); // 3
stack.print(); // 5,8,11
stack.clear(); // undefined
console.log(stack.size()); // 0

栈的应用实例： JavaScript 数据结构与算法之美 - 实现一个前端路由，如何实现浏览器的前进与后退？

4. 队列

普通队列

定义

实现

队列里面有一些声明的辅助方法：

代码：

// Queue类
function Queue() {
	this.items = [];

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

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

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

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

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

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

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

测试：

// 创建Queue实例
var queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue('John'); // undefined
queue.enqueue('Jack'); // undefined
queue.enqueue('Camila'); // undefined
queue.print(); // "John,Jack,Camila"
console.log(queue.size()); // 3
console.log(queue.isEmpty()); // false
queue.dequeue(); // "John"
queue.dequeue(); // "Jack"
queue.print(); // "Camila"
queue.clear(); // undefined
console.log(queue.size()); // 0

优先队列

定义

优先队列中元素的添加和移除是依赖优先级的。

应用

优先队列分为两类

最小优先队列是把优先级的值最小的元素被放置到队列的最前面（代表最高的优先级）。比如：有四个元素："John", "Jack", "Camila", "Tom"，他们的优先级值分别为 4，3，2，1。那么最小优先队列排序应该为："Tom"，"Camila"，"Jack"，"John"。

最大优先队列正好相反，把优先级值最大的元素放置在队列的最前面。以上面的为例，最大优先队列排序应该为："John", "Jack", "Camila", "Tom"。

实现

实现一个优先队列，有两种选项：

这里最小优先队列和最大优先队列我都采用第一种方式实现，大家可以尝试一下第二种。

下面只重写 enqueue() 方法和 print() 方法，其他方法和上面的普通队列完全相同。

实现最小优先队列

// 定义最小优先队列
function MinPriorityQueue () {
  this.items = [];

  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.isEmpty = isEmpty;
  this.size = size;
  this.clear = clear;
  this.print = print;
}

实现最小优先队列 enqueue() 方法和 print() 方法：

// 优先队列添加元素，要根据优先级判断在队列中的插入顺序
function enqueue (element, priority) {
  var queueElement = {
    element: element,
    priority: priority
  };

  if (this.isEmpty()) {
    this.items.push(queueElement);
  } else {
    var added = false;
    for (var i = 0; i < this.size(); i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break ;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }
}

// 打印队列里的元素
function print () {
  var strArr = [];

  strArr = this.items.map(function (item) {
    return `${item.element}->${item.priority}`;
  });

  console.log(strArr.toString());
}

最小优先队列测试：

// 创建最小优先队列minPriorityQueue实例
var minPriorityQueue = new MinPriorityQueue();

console.log(minPriorityQueue.isEmpty());     // true
minPriorityQueue.enqueue("John", 1);         // undefined
minPriorityQueue.enqueue("Jack", 3);         // undefined
minPriorityQueue.enqueue("Camila", 2);       // undefined
minPriorityQueue.enqueue("Tom", 3);          // undefined
minPriorityQueue.print();                    // "John->1,Camila->2,Jack->3,Tom->3"
console.log(minPriorityQueue.size());        // 4
console.log(minPriorityQueue.isEmpty());     // false
minPriorityQueue.dequeue();                  // {element: "John", priority: 1}
minPriorityQueue.dequeue();                  // {element: "Camila", priority: 2}
minPriorityQueue.print();                    // "Jack->3,Tom->3"
minPriorityQueue.clear();                    // undefined
console.log(minPriorityQueue.size());        // 0

实现最大优先队列

// 最大优先队列 MaxPriorityQueue 类
function MaxPriorityQueue () {
  this.items = [];

  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.isEmpty = isEmpty;
  this.size = size;
  this.clear = clear;
  this.print = print;
}

// 优先队列添加元素，要根据优先级判断在队列中的插入顺序
function enqueue (element, priority) {
  var queueElement = {
    element: element,
    priority: priority
  };

  if (this.isEmpty()) {
    this.items.push(queueElement);
  } else {
    var added = false;

    for (var i = 0; i < this.items.length; i++) {
      // 注意，只需要将这里改为大于号就可以了
      if (queueElement.priority > this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break ;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }
}

最大优先队列测试：

// 创建最大优先队列maxPriorityQueue实例
var maxPriorityQueue = new MaxPriorityQueue();

console.log(maxPriorityQueue.isEmpty());     // true
maxPriorityQueue.enqueue("John", 1);         // undefined
maxPriorityQueue.enqueue("Jack", 3);         // undefined
maxPriorityQueue.enqueue("Camila", 2);       // undefined
maxPriorityQueue.enqueue("Tom", 3);          // undefined
maxPriorityQueue.print();                    // "Jack->3,Tom->3,Camila->2,John->1"
console.log(maxPriorityQueue.size());        // 4
console.log(maxPriorityQueue.isEmpty());     // false
maxPriorityQueue.dequeue();                  // {element: "Jack", priority: 3}
maxPriorityQueue.dequeue();                  // {element: "Tom", priority: 3}
maxPriorityQueue.print();                    // "Camila->2,John->1"
maxPriorityQueue.clear();                    // undefined
console.log(maxPriorityQueue.size());        // 0

循环队列

定义

循环队列，顾名思义，它长得像一个环。把它想像成一个圆的钟就对了。

关键是：确定好队空和队满的判定条件。

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

下面我们在普通队列的基础上，实现一个模拟的击鼓传花游戏，下面只写击鼓传花的代码片段：

// 实现击鼓传花
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 = ["John", "Jack", "Camila", "Ingrid", "Carl"];
var winner = hotPotato(nameList, 10);
console.log(`最后的胜利者是：${winner}`);

执行结果为：

// John 在击鼓传花中被淘汰！
// Ingrid 在击鼓传花中被淘汰！ 
// Jack 在击鼓传花中被淘汰！
// Camila 在击鼓传花中被淘汰！
// 最后的胜利者是：Carl

队列小结

一些具有某些额外特性的队列，比如：循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。

以上队列的代码要感谢 leocoder351。

5. 链表

定义

简单的链接结构图：

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

特点

三种最常见的链表结构，它们分别是：

单链表

定义

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

经过改造，链表就成了如下的样子：

针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以插入与删除的时间复杂度为 O(1)。

在 d2 节点后面插入 d4 节点：

删除 d4 节点：

实现

单向链表的八种常用操作：

具体代码：

// 单链表
function SinglyLinkedList() {
	// 节点
	function Node(element) {
		this.element = element; // 当前节点的元素
		this.next = null; // 下一个节点指针
	}

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

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

		// 判断是否为空链表
		if (head === null) {
			// 是空链表，就把当前节点作为头部节点
			head = node;
		} else {
			// 从 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 {
			var node = new Node(element);
			var index = 0;
			var currentNode = head;
			var 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 {
			var currentNode = head;
			var index = 0;
			var 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) {
		var index = this.indexOf(element);
		return this.removeAt(index);
	};

	// 返回元素在链表的索引，如果链表中没有该元素则返回 -1
	this.indexOf = function(element) {
		var currentNode = head;
		var 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() {
		var currentNode = head;
		var 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;
	};
}

测试：

// 创建单向链表实例
var singlyLinked = new SinglyLinkedList();
console.log(singlyLinked.removeAt(0)); // false
console.log(singlyLinked.isEmpty()); // true
singlyLinked.append('Tom');
singlyLinked.append('Peter');
singlyLinked.append('Paul');
singlyLinked.print(); // "Tom,Peter,Paul"
singlyLinked.insert(0, 'Susan');
singlyLinked.print(); // "Susan,Tom,Peter,Paul"
singlyLinked.insert(1, 'Jack');
singlyLinked.print(); // "Susan,Jack,Tom,Peter,Paul"
console.log(singlyLinked.getHead()); // "Susan"
console.log(singlyLinked.isEmpty()); // false
console.log(singlyLinked.indexOf('Peter')); // 3
console.log(singlyLinked.indexOf('Cris')); // -1
singlyLinked.remove('Tom');
singlyLinked.removeAt(2);
singlyLinked.print(); // "Susan,Jack,Paul"
singlyLinked.list(); // 具体控制台

整个链表数据在 JavaScript 里是怎样的呢？

为了看这个数据，特意写了个 list 函数：

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

重点上上面的最后一行代码： singlyLinked.list() ，打印的数据如下：

所以，在 JavaScript 中，单链表的真实数据有点类似于对象，实际上是 Node 类生成的实例。

双向链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

单向链表与又向链表比较

实现

具体代码：

// 创建双向链表 DoublyLinkedList 类
function DoublyLinkedList() {
  function Node(element) {
    this.element = element; //当前节点的元素
    this.next = null; //下一个节点指针
    this.previous = null; //上一个节点指针
  }

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

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

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

    length++;
  };

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

      if (position === 0) {
        if (!head) {
          head = node;
          tail = node;
        } else {
          node.next = currentNode;
          currentNode.prev = node;
          head = node;
        }
      } else if (position === length) {
        this.append(element);
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }

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

        node.prev = previousNode;
        currentNode.prev = node;
      }

      length++;

      return true;
    }
  };

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

      if (position === 0) {
        // 移除第一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          head = currentNode.next;
          head.prev = null;
        }
      } else if (position === length - 1) {
        // 移除最后一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          currentNode = tail;
          tail = currentNode.prev;
          tail.next = null;
        }
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
        previousNode = currentNode.next.prev;
      }

      length--;

      return true;
    }
  };

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

  // 返回元素在链表的索引，如果链表中没有该元素则返回 -1
  this.indexOf = function(element) {
    var currentNode = head;
    var 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() {
    var currentNode = head;
    var 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;
  };
}

测试：

// 创建双向链表
var doublyLinked = new DoublyLinkedList();
console.log(doublyLinked.isEmpty()); // true
doublyLinked.append('Tom');
doublyLinked.append('Peter');
doublyLinked.append('Paul');
doublyLinked.print(); // "Tom,Peter,Paul"
doublyLinked.insert(0, 'Susan');
doublyLinked.print(); // "Susan,Tom,Peter,Paul"
doublyLinked.insert(1, 'Jack');
doublyLinked.print(); // "Susan,Jack,Tom,Peter,Paul"
console.log(doublyLinked.getHead()); // "Susan"
console.log(doublyLinked.isEmpty()); // false
console.log(doublyLinked.indexOf('Peter')); // 3
console.log(doublyLinked.indexOf('Cris')); // -1
doublyLinked.remove('Tom');
doublyLinked.removeAt(2);
doublyLinked.print(); // "Susan,Jack,Paul"
doublyLinked.list(); // 请看控制台输出

整个链表数据在 JavaScript 里是怎样的呢？

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

调用 doublyLinked.list(); .

控制台输出如下：

链表代码实现的关键是弄清楚：前节点与后节点与边界。

循环链表

循环链表是一种特殊的单链表。循环链表和单链表相似，节点类型都是一样。唯一的区别是，在创建循环链表的时候，让其头节点的 next 属性指向它本身。即：

head.next = head;

这种行为会导致链表中每个节点的 next 属性都指向链表的头节点，换句话说，也就是链表的尾节点指向了头节点，形成了一个循环链表。如下图所示：

循环链表：在单链表的基础上，将尾节点的指针指向头结点，就构成了一个循环链表。环形链表从任意一个节点开始，都可以遍历整个链表。

代码：

// 循环链表
function CircularLinkedList() {
	// 节点
	function Node(element) {
		this.element = element; // 当前节点的元素
		this.next = null; // 下一个节点指针
	}

	var length = 0,
		head = null;

	this.append = function(element) {
		var node = new Node(element),
			current;

		if (!head) {
			head = node;
			// 头的指针指向自己
			node.next = head;
		} else {
			current = head;

			while (current.next !== head) {
				current = current.next;
			}

			current.next = node;
			// 最后一个节点指向头节点
			node.next = head;
		}

		length++;
		return true;
	};

	this.insert = function(position, element) {
		if (position > -1 && position < length) {
			var node = new Node(element),
				index = 0,
				current = head,
				previous;

			if (position === 0) {
				// 头节点指向自己
				node.next = head;
				head = node;
			} else {
				while (index++ < position) {
					previous = current;
					current = current.next;
				}
				previous.next = node;
				node.next = current;
			}
			length++;
			return true;
		} else {
			return false;
		}
	};
	this.removeAt = function(position) {
		if (position > -1 && position < length) {
			var current = head,
				previous,
				index = 0;
			if (position === 0) {
				head = current.next;
			} else {
				while (index++ < position) {
					previous = current;
					current = current.next;
				}
				previous.next = current.next;
			}
			length--;
			return current.element;
		} else {
			return false;
		}
	};
	this.remove = function(element) {
		var current = head,
			previous,
			indexCheck = 0;
		while (current && indexCheck < length) {
			if (current.element === element) {
				if (indexCheck == 0) {
					head = current.next;
					length--;
					return true;
				} else {
					previous.next = current.next;
					length--;
					return true;
				}
			} else {
				previous = current;
				current = current.next;
				indexCheck++;
			}
		}
		return false;
	};
	this.remove = function() {
		if (length === 0) {
			return false;
		}
		var current = head,
			previous,
			indexCheck = 0;
		if (length === 1) {
			head = null;
			length--;
			return current.element;
		}
		while (indexCheck++ < length) {
			previous = current;
			current = current.next;
		}
		previous.next = head;
		length--;
		return current.element;
	};
	this.indexOf = function(element) {
		var current = head,
			index = 0;
		while (current && index < length) {
			if (current.element === element) {
				return index;
			} else {
				index++;
				current = current.next;
			}
		}
		return -1;
	};
	this.isEmpty = function() {
		return length === 0;
	};
	this.size = function() {
		return length;
	};

	// 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值
	this.toString = function() {
		var current = head,
			string = '',
			indexCheck = 0;
		while (current && indexCheck < length) {
			string += ',' + current.element;
			current = current.next;
			indexCheck++;
		}
		return string.slice(1);
	};

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

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

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

测试：

// 创建单向链表实例
var circularLinked = new CircularLinkedList();
console.log(circularLinked.removeAt(0)); // false
console.log(circularLinked.isEmpty()); // true
circularLinked.append('Tom');
circularLinked.append('Peter');
circularLinked.append('Paul');
circularLinked.print(); // "Tom,Peter,Paul"
circularLinked.insert(0, 'Susan');
circularLinked.print(); // "Susan,Tom,Peter,Paul"
circularLinked.insert(1, 'Jack');
circularLinked.print(); // "Susan,Jack,Tom,Peter,Paul"
console.log(circularLinked.getHead()); // "Susan"
console.log(circularLinked.isEmpty()); // false
console.log(circularLinked.indexOf('Peter')); // 3
console.log(circularLinked.indexOf('Cris')); // -1
circularLinked.remove('Tom');
circularLinked.removeAt(2);
circularLinked.print(); // "Susan,Jack,Paul"
circularLinked.list(); // 具体控制台

整个链表数据在 JavaScript 里是怎样的呢？

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

调用 circularLinked.list() 。

控制台输出如下：

你知道大家发现没有，为什么从 1 - 4 - 1 了，还有 next 节点，而且是还可以一直点 next ，重复的展开下去，这正是循环的原因。

链表总结

6. 文章输出计划

JavaScript 数据结构与算法之美 的系列文章，坚持 3 - 7 天左右更新一篇，暂定计划如下表。

标题链接时间和空间复杂度 https://github.com/biaochenxuying/blog/issues/29

线性表（数组、链表、栈、队列） https://github.com/biaochenxuying/blog/issues/34

实现一个前端路由，如何实现浏览器的前进与后退？ https://github.com/biaochenxuying/blog/issues/30

栈内存与堆内存、浅拷贝与深拷贝 https://github.com/biaochenxuying/blog/issues/35

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。

7. 最后

关注我的公众号，第一时间接收最新的精彩博文。

文章可以转载，但须注明作者及出处，需要转载到公众号的，喊我加下白名单就行了。

如果喜欢或者有所启发，欢迎 star，对作者也是一种鼓励。

参考文章：

数组：为什么很多编程语言中数组都从 0 开始编号？

JS中的算法与数据结构——链表(Linked-list)

JavaScript数据结构 03 - 队列 链表（上）：如何实现 LRU 缓存淘汰算法?

JavaScript数据结构——队列

编辑于 2019-08-04 09:24

JavaScript

算法与数据结构

栈（数据结构）

文章被以下专栏收录

全栈修炼

大前端的成长之路。

web前端开发

万丈红尘千行码，千秋大业一console.log