|
阅读：5469回复：0
【数据结构】链表
链表(Linked-list)
在很多编程语言中，数组的长度都是固定的，如果数组已被数据填满，再要加入新的元素是非常困难的。而且，对于数组的删除和添加操作，通常需要将数组中的其他元素向前或者向后平移，这些操作也是十分繁琐的。 然而，JS中数组却不存在上述问题，主要是因为他们被实现了成了对象，但是与其他语言相比（比如C或Java），那么它的效率会低很多。 这时候，我们可以考虑使用链表(Linked-list) 来替代它，除了对数据的随机访问，链表几乎可以在任何可以使用一维数组的情况中。如果你正巧在使用C或者Java等高级语言，你会发现链表的表现要优于数组很多。 链表其实有许多的种类：单向链表、双向链表、单向循环链表和双向循环链表，接下来，我们基于对象来实现一个单向链表，因为它的使用最为广泛。 链表的定义 首先，要实现链表，我们先搞懂一些链表的基本东西，因为这很重要！ 链表是一组节点组成的集合，每个节点都使用一个对象的引用来指向它的后一个节点。指向另一节点的引用讲做链。下面我画了一个简单的链接结构图，方便大家理解。 图片：link1.png  链表结构图 由于链表的起始点的确定比较麻烦，因此很多链表的实现都会在链表的最前面添加一个特殊的节点，称为 头节点，表示链表的头部。进过改造，链表就成了如下的样子： 图片：link2.png 有头节点的链表 图片：link3.png 插入节点 图片：link4.png 删除节点
链表的设计 首先我们要创建一个链表类： function LinkedList(){
//各种属性和方法的声明
}
然后我们需要一种数据结构来保存链表里面的数据： var Node=function(element){
this.element=element;
this.next=null;
}
Node类表示要添加的元素，他有两个属性， 一个是element，表示添加到链表中的具体的值； 另一个是next,表示要指向链表中下一个元素的指针。 接下来，我们需要给链表声明一些方法：
ES6版本: let LinkedList2 = (function () {
class Node {
constructor(element){
this.element = element;
this.next = null;
}
}
//这里我们使用WeakMap对象来记录长度状态
const length = new WeakMap();
const head = new WeakMap();
class LinkedList2 {
constructor () {
length.set(this, 0);
head.set(this, null);
}
append(element) {
let node = new Node(element),
current;
if (this.getHead() === null) {
head.set(this, node);
} else {
current = this.getHead();
while (current.next) {
current = current.next;
}
current.next = node;
}
let l = this.size();
l++;
length.set(this, l);
}
insert(position, element) {
if (position >= 0 && position <= this.size()) {
let node = new Node(element),
current = this.getHead(),
previous,
index = 0;
if (position === 0) {
node.next = current;
head.set(this, node);
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
let l = this.size();
l++;
length.set(this, l);
return true;
} else {
return false;
}
}
removeAt(position) {
if (position > -1 && position < this.size()) {
let current = this.getHead(),
previous,
index = 0;
if (position === 0) {
head.set(this, current.next);
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
let l = this.size();
l--;
length.set(this, l);
return current.element;
} else {
return null;
}
}
remove(element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
indexOf(element) {
let current = this.getHead(),
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
}
isEmpty() {
return this.size() === 0;
}
size() {
return length.get(this);
}
getHead() {
return head.get(this);
}
toString() {
let current = this.getHead(),
string = '';
while (current) {
string += current.element + (current.next ? ', ' : '');
current = current.next;
}
return string;
}
print() {
console.log(this.toString());
}
}
return LinkedList2;
})();
双向链表 尽管从链表的头节点遍历链表很简单，但是反过来，从后向前遍历却不容易。我们可以通过给Node类增加一个previous属性，让其指向前驱节点的链接，这样就形成了双向链表，如下图： 图片：link5.png 双向链表 双向链表的实现 要实现双向链表，首先需要给 Node 类增加一个 previous 属性： //节点类 function Node(element) {
this.element = element; //当前节点的元素
this.next = null; //下一个节点链接
this.previous = null; //上一个节点链接
}
完整实现如下： function DoublyLinkedList() {
let Node = function(element){
this.element = element;
this.next = null;
this.prev = null; //NEW
};
let length = 0;
let head = null;
let tail = null; //NEW
this.append = function(element){
let node = new Node(element),
current;
if (head === null){
head = node;
tail = node; //NEW
} else {
//NEW
tail.next = node;
node.prev = tail;
tail = node;
}
length++;
};
this.insert = function(position, element){
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){
if (!head){ //NEW
head = node;
tail = node;
} else {
node.next = current;
current.prev = node; //NEW
head = node;
}
} else if (position === length) { ////NEW
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node; //NEW
node.prev = previous; //NEW
}
length++;
return true;
} else {
return false;
}
};
this.removeAt = function(position){
if (position > -1 && position < length){
let current = head,
previous,
index = 0;
if (position === 0){ //NEW
if (length === 1){ //
tail = null;
} else {
head.prev = null;
}
} else if (position === length-1){ //NEW
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous; //NEW
}
length--;
return current.element;
} else {
return null;
}
};
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
this.indexOf = function(element){
let current = head,
index = -1;
if (element == current.element){
return 0;
}
index++;
while(current.next){
if (element == current.element){
return index;
}
current = current.next;
index++;
}
//check last item
if (element == current.element){
return index;
}
return -1;
};
this.isEmpty = function() {
return length === 0;
};
this. size = function() {
return length;
};
this.toString = function(){
let current = head,
s = current ? current.element : '';
while(current && current.next){
current = current.next;
s += ', ' + current.element;
}
return s;
};
this.inverseToString = function() {
let current = tail,
s = current ? current.element : '';
while(current && current.prev){
current = current.prev;
s += ', ' + current.element;
}
return s;
};
this.print = function(){
console.log(this.toString());
};
this.printInverse = function(){
console.log(this.inverseToString());
};
this.getHead = function(){
return head;
};
this.getTail = function(){
return tail;
}
}
循环链表 循环链表和单链表相似，节点类型都是一样，唯一的区别是，在创建循环链表的时候，让其头节点的 next 属性执行它本身，即 head.next = head; 这种行为会导致链表中每个节点的 next 属性都指向链表的头节点，换句话说，也就是链表的尾节点指向了头节点，形成了一个循环链表，如下图所示： 图片：link6.png 循环链表
原理相信你已经懂了，循环链表这里就不贴代码了，相信你自己能独立完成！ 参考： https://juejin.im/entry/59cb70995188256aa423b680 https://juejin.im/post/58287452570c3500587642b6 |
|
|
公众号
