JavaScript数据结构与算法Item4--链表

xiaoxiao2023-03-24 4

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

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

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

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

1 创建一个链表

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

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; };

总的结构代码：

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。

双向链表总程序

转载请注明原文地址: https://ju.6miu.com/read-1201603.html

最新回复(0)