JavaScript数据结构04 - 链表
一、定义
1.1 概念
前面我们学习了数组这种数据结构。数组（或者也可以称为列表）是一种非常简单的存储数据序列的数据结构。在这一节，我们要学习如何实现和使用链表这种动态的数据结构，这意味着我们可以从中任意添加或移除项，它会按需进行扩容。
要存储多个元素，数组（或列表）可能是最常用的数据结构，它提供了一个便利的[]语法来访问它的元素。然而，这种数据结构有一个缺点：（在大多数强类型语言中）数组的大小是固定的，需要预先分配，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。
（注意：在JavaScript中数组的大小随时可变，不需要预先定义长度）
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
相对于传统的数组，链表的一个好处在于，添加或删除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的元素，而想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。
火车可以当做生活中一个典型的链表的例子。一列火车是由一系列车厢组成的。每节车厢都相互连接。你很容易分离一节车厢，改变它的位置，添加或移除它。
1.2 分类
链表最常用的有三类：
- 单向链表
- 双向链表
- 循环链表
二、链表的实现
2.1 单向链表
创建单向链表类：
// SinglyLinkedList
function SinglyLinkedList () {
function Node (element) {
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
this.append = function (element) {};
this.insert = function (position, element) {};
this.removeAt = function (position) {};
this.remove = function (element) {};
this.indexOf = function (element) {};
this.isEmpty = function () {};
this.size = function () {};
this.getHead = function () {};
this.toString = function () {};
this.print = function () {};
}SinglyLinkedList需要一个辅助类Node。Node类表示要加入链表的项。它包含一个element属性，即要添加到链表的值，以及一个next属性，即指向链表中下一个节点项的指针。
链表里面有一些声明的辅助方法：
- append(element)：向链表尾部添加新项
- insert(position, element)：向链表的特定位置插入一个新的项
- removeAt(position)：从链表的特定位置移除一项
- remove(element)：从链表中移除一项
- indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1
- isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0，返回false
- size()：返回链表包含的元素个数，与数组的length属性类似
- getHead()：返回链表的第一个元素
- toString()：由于链表使用了Node类，就需要重写继承自JavaScript对象默认的toString()方法，让其只输出元素的值
- print()：打印链表的所有元素
下面我们来一一实现这些辅助方法：
// 向链表尾部添加一个新的项
this.append = function (element) {
var node = new Node(element);
var currentNode = head;
// 判断是否为空链表
if (currentNode === null) {
// 空链表
head = node;
} else {
// 从head开始一直找到最后一个node
while (currentNode.next) {
// 后面还有node
currentNode = currentNode.next;
}
currentNode.next = 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) {
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;
}
previousNode.next = currentNode.next;
}
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;
}
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());
};创建单向链表实例进行测试：
// 创建单向链表实例
var singlyLinked = new SinglyLinkedList();
console.log(singlyLinked.removeAt(0)); // true
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"2.2 双向链表
双向链表和普通链表的区别在于，在普通链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。
创建双向链表类：
// 创建双向链表DoublyLinkedList类
function DoublyLinkedList () {
function Node (element) {
this.element = element;
this.next = null;
this.prev = null; // 新增
}
var length = 0;
var head = null;
var tail = null; // 新增
}可以看到，双向链表在Node类里有prev属性（一个新指针），在DoublyLinkedList类里也有用来保存对列表最后一项的引用的tail属性。
双向链表提供了两种迭代列表的方法：从头到尾，或者从尾到头。我们可以访问一个特定节点的下一个或前一个元素。
在单向链表中，如果迭代链表时错过了要找的元素，就需要回到链表起点，重新开始迭代。在双向链表中，可以从任一节点，向前或向后迭代，这是双向链表的一个优点。
实现双向链表的辅助方法：
// 向链表尾部添加一个新的项
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());
};创建双向链表实例进行测试：
// 创建双向链表
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"2.3 循环链表
循环链表可以像单向链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和普通链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（next）不是引用null，而是指向第一个元素（head）。这里就不进行代码实现了，大家可以结合上面的单向链表和双向链表自己实现一个循环链表。
三、结束
本文会同步到我的个人博客，完整代码可以到我的github仓库查看，如果对你有帮助的话欢迎点一个Star~~
欢迎关注我的公众号
相关推荐
koushr 2020-11-12
范范 2020-10-28
qiangde 2020-09-13
范范 2020-07-30
mingyunxiaohai 2020-07-19
LauraRan 2020-09-28
mingyunxiaohai 2020-07-28
zhangxiafll 2020-11-13
kikaylee 2020-10-31
MILemon 2020-10-22
hugebawu 2020-10-12
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02