JavaScript数据结构与算法Item4

数据结构与算法Item4"/>

JavaScript数据结构与算法Item4

要存储多个元素，数组（或列表）可能是最常用的数据结构,，每种语言都实现了数组。这种数据结构非常方便，提供了一个便利的[]语法来访问它的元素。然而，这种数据结构有一个缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素.

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。下图展示了一个链表的结构：

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。

现实中也有一些链表的例子。一列火车是由一系列车厢（也称车皮）组成的。每节车厢或车皮都相互连接。你很容易分离一节车皮，改变它的位置，添加或移除它。

1 创建一个链表

理解了链表是什么之后，现在就要开始实现我们的数据结构了。以下是我们的LinkedList类的骨架：

function LinkedList() {var Node = function(element){ // {1}this.element = element;this.next = null;};var length = 0; // {2}var head = null; // {3}this.append = function(element){};  //向列表尾部添加一个新的项。this.insert = function(position, element){};//向列表的特定位置插入一个新的项this.removeAt = function(position){};//从列表的特定位置移除一项。this.remove = function(element){};//从列表中移除一项。this.indexOf = function(element){};//返回元素在列表中的索引。如果列表中没有该元素则返回-1this.isEmpty = function() {};//如果链表中不包含任何元素，返回true，如果链表长度大于0则返回falsethis.size = function() {};//返回链表包含的元素个数。与数组的length属性类似this.toString = function(){};//this.print = function(){};//
}

LinkedList数据结构还需要一个Node辅助类（行{1}）。Node类表示要加入列表的项。它包含一个element属性，即要添加到列表的值，以及一个next属性，即指向列表中下一个节点项的指针。

向链表尾部追加元素

向LinkedList对象尾部添加一个元素时，可能有两种场景：列表为空，添加的是第一个元素，或者列表不为空，向其追加元素。

this.append = function(element){var node = new Node(element), //{1}current; //{2}if (head === null){ //列表中第一个节点 //{3}head = node;} else {current = head; //{4}//循环列表，直到找到最后一项while(current.next){current = current.next;}//找到最后一项，将其next赋为node，建立链接current.next = node; //{5}}length++; //更新列表的长度 //{6}
};

从链表中移除元素

现在，让我们看看如何从LinkedList对象中移除元素。移除元素也有两种场景：第一种是移除第一个元素，第二种是移除第一个以外的任一元素。我们要实现两种remove方法：第一种是从特定位置移除一个元素，第二种是根据元素的值移除元素（稍后我们会展示第二种remove方法）。

this.removeAt = function(position){//检查越界值if (position > -1 && position < length){ // {1}var current = head, // {2}previous, // {3}index = 0; // {4}//移除第一项if (position === 0){ // {5}head = current.next;} else {while (index++ < position){ // {6}previous = current; // {7}current = current.next; // {8}}//将previous与current的下一项链接起来：跳过current，从而移除它previous.next = current.next; // {9}}length--; // {10}return current.element;} else {return null; // {11}}
};

在任意位置插入一个元素

接下来，我们要实现insert方法。使用这个方法可以在任意位置插入一个元素。我们来看一看它的实现：

this.insert = function(position, element){//检查越界值if (position >= 0 && position <= length){ //{1}var node = new Node(element),current = head,previous,index = 0;if (position === 0){ //在第一个位置添加node.next = current; //{2}head = node;} else {while (index++ < position){ //{3}previous = current;current = current.next;}node.next = current; //{4}previous.next = node; //{5}}length++; //更新列表的长度return true;} else {return false; //{6}}
};

toString方法

toString方法会把LinkedList对象转换成一个字符串。下面是toString方法的实现：

this.toString = function(){var current = head, //{1}string = ''; //{2}while (current) { //{3}string = current.element; //{4}current = current.next; //{5}}return string; //{6}
};

indexOf方法

indexOf是我们下一个要实现的方法。indexOf方法接收一个元素的值，如果在列表中找到它，就返回元素的位置，否则返回-1。来看看它的实现：

this.indexOf = function(element){var current = head, //{1}index = -1;while (current) { //{2}if (element === current.element) {return index; //{3}}index++; //{4}current = current.next; //{5}}return -1;
};

实现了这个方法，我们就可以实现remove等其他的方法：

this.remove = function(element){var index = this.indexOf(element);return this.removeAt(index);
};

isEmpty、size和getHead方法

isEmpty和size方法跟我们在上一章实现的一模一样。但我们还是来看一下：

this.isEmpty = function() {return length === 0;
};

如果列表中没有元素，isEmpty方法就返回true，否则返回false。

this.size = function() {return length;
};

size方法返回列表的length。和我们之前几章实现的类有所不同，列表的length是内部控
制的，因为LinkedList是从头构建的。最后还有getHead方法：

this.getHead = function(){return head;
};

总的结构代码：

function LinkedList(){function Node(element){this.element = element;this.next = null;}this.head = null;this.length = 0;this.append = function(element){var node = new Node(element),current;if(this.head == null){this.head = node;}else{current = this.head;while(current.next){current = current.next;}current.next = node;}this.length ++;}this.removeAt = function(position){var current = this.head,index = 0,prev;if(position > -1 && position < this.length){ //检查越界值if (position == 0){  //删除第一项，将head指向第一个元素即可；this.head = current.next;}else{while(index++ < position){ //将previous与current的下一项链接起来：跳过current，从而移除它,此处找到前一项；prev = current;current = current.next;}prev.next = current.next; //此处跳过current；}this.length --;return true;}else{return null;}}this.insert = function(position, element){var current = this.head,index = 0,prev,node = new Node(element);if(position> -1 && position < this.length){if(position == 0){this.head = node;node.next = current;}else{while(index++ < position){prev = current;current = current.next;}prev.next = node;node.next = current}this.length ++;}else{return false;}}this.indexOf = function(element){var current = this.head;index = -1;while(current){index ++;if(current.element === element){return index;}current = current.next;}return -1;}this.remove = function(element){var index = this.indexOf(element);this.removeAt(index);}this.isEmpty = function(){return this.length === 0;}this.size = function(){return this.length;}this.getHead = function(){return this.head;}this.toString = function(){var current = this.head,string = '';while(current){string += current.element + '-->';current = current.next;}return string;}}var linkedList = new LinkedList();linkedList.append(10);linkedList.append(15);linkedList.append(20);linkedList.append(25);linkedList.append(30);linkedList.append(35);console.log(linkedList.toString());linkedList.removeAt(2);console.log(linkedList.toString());linkedList.insert(2,111);console.log(linkedList.toString());console.log(linkedList.indexOf(10))

2 双向链表

链表有多种不同的类型，这一节介绍双向链表。双向链表和普通链表的区别在于，在链表中，
一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，
另一个链向前一个元素，如下图所示：

先从实现DoublyLinkedList类所需的变动开始：

function DoublyLinkedList() {var Node = function(element){this.element = element;this.next = null;this.prev = null; //新增的};var length = 0;var head = null;var tail = null; //新增的//这里是方法
}

在任意位置插入一个新元素

向双向链表中插入一个新项跟（单向）链表非常类似。区别在于，链表只要控制一个next
指针，而双向链表则要同时控制next和prev（previous，前一个）这两个指针。

this.insert = function(position, element){var current = this.head,index = 0,prev,node = new Node(element);if(position> -1 && position < this.length){if(position == 0){if(!this.head){//插入空的链表中的首位this.head = node;this.tail = node;}else{this.head = node;node.next = current;current.prev = node;}}else if(position == this.length){current = tail;current.next = node;node.prev = current;this.tail = node;}else{while(index++ < position){previous = current;current = current.next;}previous.next = node;node.next = current;node.prev = previous;current.prev = node;}this.length ++;return true;}else{return false;}}

从任意位置移除元素

我们需要处理三种场景：从头部、从中间和从尾部移除一个元素。

this.removeAt = function(position){var current = this.head,index = 0,prev;if(position > -1 && position < this.length){ //检查越界值if (position == 0){  //删除第一项，将head指向第一个元素即可；this.head = current.next;if(this.length == 1){this.tail = null;}else{this.head.prev = null;}}else if(position == this.length -1){current = this.tail;this.tail = current.prev;this.tail.next = null;}else{while(index++ < position){ //将previous与current的下一项链接起来：跳过current，从而移除它,此处找到前一项；previous = current;current = current.next;}previous.next = current.next; //此处跳过current；current.next.prev = previous; }this.length --;return current.element;}else{return null;}}

3 循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链
表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）不是引用null，
而是指向第一个元素（head），如下图所示。

双向循环链表有指向head元素的tail.next，和指向tail元素的head.prev。

双向链表总程序

function DoubleLinkedList(){function Node(element){this.element = element;this.prev = null;this.next = null;}this.head = null;this.tail = null;this.length = 0;this.append = function(element){var node = new Node(element),current;if(this.head == null){this.head = node;this.tail = node;}else{current = this.head;while(current.next){current = current.next;}current.next = node;node.prev = current;this.tail = node;}this.length ++;}this.removeAt = function(position){var current = this.head,index = 0,prev;if(position > -1 && position < this.length){ //检查越界值if (position == 0){  //删除第一项，将head指向第一个元素即可；this.head = current.next;if(this.length == 1){this.tail = null;}else{this.head.prev = null;}}else if(position == this.length -1){current = this.tail;this.tail = current.prev;this.tail.next = null;}else{while(index++ < position){ //将previous与current的下一项链接起来：跳过current，从而移除它,此处找到前一项；previous = current;current = current.next;}previous.next = current.next; //此处跳过current；current.next.prev = previous; }this.length --;return current.element;}else{return null;}}this.insert = function(position, element){var current = this.head,index = 0,prev,node = new Node(element);if(position> -1 && position < this.length){if(position == 0){if(!this.head){//插入空的链表中的首位this.head = node;this.tail = node;}else{this.head = node;node.next = current;current.prev = node;}}else if(position == this.length){current = tail;current.next = node;node.prev = current;this.tail = node;}else{while(index++ < position){previous = current;current = current.next;}previous.next = node;node.next = current;node.prev = previous;current.prev = node;}this.length ++;return true;}else{return false;}}this.indexOf = function(element){var current = this.head;index = -1;while(current){index ++;if(current.element === element){return index;}current = current.next;}return -1;}this.remove = function(element){var index = this.indexOf(element);this.removeAt(index);}this.isEmpty = function(){return this.length === 0;}this.size = function(){return this.length;}this.getHead = function(){return this.head;}this.toString = function(){var current = this.head,string = '';while(current){string += current.element + '-->';current = current.next;}return string;}
}var linkedList = new DoubleLinkedList();linkedList.append(10);linkedList.append(15);linkedList.append(20);linkedList.append(25);linkedList.append(30);linkedList.append(35);console.log(linkedList.toString());linkedList.removeAt(2);console.log(linkedList.toString());linkedList.insert(2,111);console.log(linkedList.toString());console.log(linkedList.indexOf(10))