js数据结构和算法(三)链表（linked list）

电玩女神 2021-09-15 01:18 258阅读 0赞

链表是一种常见的数据结构，也属于线性表，但不会按线性的顺序来储存数据。而是在每一个节点中，储存了下一个节点的指针。可以看图理解。使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

**链表一般有，单链表、静态链表、循环链表、双向链表**  
1.单链表：就是很单一的向下传递，每一个节点只记录下一个节点的信息，就跟无间道中的梁朝伟一样做卧底都是通过中间人上线与下线联系，一旦中间人断了，那么就无法证明自己的身份了，所以片尾有一句话："我是好人，谁知道呢？”  
2.静态链表：就是用数组描述的链表。也就是数组中每一个下表都是一个“节”包含了数据与指向  
3.循环链表：由于单链表的只会往后方传递，所以到达尾部的时候，要回溯到首部会非常麻烦，所以把尾部节的链与头连接起来形成循环  
4.双向链表：针对单链表的优化，让每一个节都能知道前后是谁，所以除了后指针域还会存在一个前指针域，这样提高了查找的效率，不过带来了一些在设计上的复杂度，总体来说就是空间换时间了  
综合下，其实链表就是线性表中针对顺序存储结构的一种优化手段，但是在javascript语言中由于数组的特殊性（自动更新引用位置），所以我们可以采用对象的方式做链表存储的结构

# 一.单向链表 #

## 1.定义： ##

链表中最简单的形式就是单向链表，链表中的节点都包含两个部分，第一部分储存着自身信息，第二部分则储存有指向下一节点的指针。最后一个节点则指向NULL，如图所示:

![Image 1][]

## 2.方法 ##

append(element): 添加元素到链表尾部  
insert(position,element): 向单向链表中某个位置插入元素  
indexOf(element): 寻找某个元素在单向链表中的位置  
remove(element): 移除给定的元素  
removeAt(position): 移除单向链表中某个位置的元素  
getHead(): 获取单向链表的头部  
isAmpty(): 检查单向链表是否为空，为空则返回true  
toString(): 将链表所有内容以字符串输出  
size(): 返回单向链表长度

## 3.操作 ##

//单向链表构造函数
    function LinkedList() {
    	/**
    	 * 单向链表中节点的构造函数
    	 * @param {Any} element 要传入链表的节点
    	 */
    	var Node = function(element) {
    			this.element = element;
    			this.next = null;
    		}
    	var length = 0;//单向链表的长度
    	var head = null;//单向链表的头结点，初始化为NULL
    	/**
    	 * 向单向链表尾部添加元素
    	 * @param  {Any} element 要加入链表的节点
    	 */
    	this.append = function(element) {
    		var node = new Node(element);
    		var current;
    		if (head == null) {
    			head = node;
    		} else {
    			// 当前项等于链表头部元素.
    			// while循环到最后一个，从而将该节点加入链表尾部。
    			current = head;
    			// 当next为null时，判定为false。退出循环。
    			while (current.next) {
    				current = current.next;
    			}
    			current.next = node;
    		}
    		length++;
    	};
    
    	/**
    	 * 移除单向链表中某一个元素
    	 * @param  {Number} position 要移除元素的位置
    	 * @return {Any}          移除成功返回被移除的元素，不成功则返回NULL
    	 */
    	this.removeAt = function(position) {
    		if (position > -1 && position < length) {
    			var current = head;
    			var previous;
    			var index = 0;
    
    			if (position == 0) {
    				// 因为之前head指向第一个元素，现在把head修改为指向第二个元素。
    				// 核心概念在于链表前后全靠指针链接，而非数组一般。
    				// 所以只需要改变head的元素。
    				head = current.next;
    			} else {
    				while (index++ < position) {
    					// previous指要操作元素位置之前的那个元素，current表示之后的那个元素。
    					previous = current;
    					current = current.next;
    				}
    
    				previous.next = current.next;
    			}
    
    			length--;
    
    			return current.element;
    		} else {
    			return null;
    		}
    	};
    
    	/**
    	 * 向单向链表中插入某个元素
    	 * @param  {Number} position 要插入的位置
    	 * @param  {Any} element  要插入的元素
    	 * @return {Boolean}          插入成功返回true，失败返回false
    	 */
    	this.insert = function(position, element) {
    		if (position >= 0 && position <= length) {
    			var node = new Node(element);
    			var current = head;
    			var previous;
    			var index = 0;
    
    			if (position == 0) {
    				node.next = current;
    				head = node;
    			} else {
    				while (index++ < position) {
    					previous = current;
    					current = current.next;
    				}
    
    				previous.next = node;
    				node.next = current;
    			}
    
    			length++;
    			return true;
    		} else {
    			return false;
    		}
    	};
    
    	/**
    	 * 将链表所有内容以字符串输出
    	 * @return {String} 要输出的字符串
    	 * current.element+','  这边可以自行加 逗号或是 空格 
    	 */
    	this.toString = function() {
    		var current = head;
    		var string = '';
    
    		while (current) {
    			string += current.element+',';
    			current = current.next;
    		}
    		return string;
    	};
    
    	/**
    	 * 寻找某个元素在单向链表中的位置
    	 * @param  {Any} element 要寻找的元素
    	 * @return {Number}         返回值>=0则代表找到相应位置
    	 */
    	this.indexOf = function(element) {
    		var current = head;
    		var index = 0;
    		while (current) {
    			if (element === current.element) {
    				return index;
    			}
    			index++;
    			current = current.next;
    		}
    
    		return -1;
    	};
    	/**
    	 * 移除给定的元素
    	 * @param  {Any} element 要移除的元素
    	 * @return {Number}         返回值>=0表示移除成功
    	 */
    	this.remove = function(element) {
    		var index = this.indexOf(element);
    		return this.removeAt(index);
    	};
    
    	/**
    	 * 判断单向链表是否为空
    	 * @return {Boolean} 为空则返回true，不为空则返回false
    	 */
    	this.isAmpty = function() {
    		return length === 0
    	};
    
    	/**
    	 * 返回单向链表长度
    	 * @return {Number} 单向链表的长度
    	 */
    	this.size = function() {
    		return length;
    	};
    
    	/**
    	 * 获取单向链表的头部
    	 * @return {Any} 单向链表的头部
    	 */
    	this.getHead = function() {
    		return head;
    	}
    }
    //测试操作
    var cities = new LinkedList();
    cities.insert(0,'apple1');
    cities.insert(1,'apple2');
    cities.insert(2,'apple3');
    console.log(cities.toString());//apple1,apple2,apple3,
    console.log(cities.indexOf('apple2'));//1

# 二.双向链表 #

## 1.定义 ##

双向链表与单向链表很是相像。在单向链表中，只有指向下一个节点的链接。但在双向链表中，还有指向上一个节点的链接，是双向的。

![Image 1][]

## 2.方法 ##

append(element): 添加元素到双向链表尾部  
insert(position,element): 向双向链表中某个位置插入元素  
removeAt(position): 移除双向链表中某个位置的元素  
showHead(): 获取双向链表的头部  
showLength(): 获取双向链表长度

showTail(): 获取双向链表尾部

属性:  
 \* 使用一个 Node 对象来保存该链表的头节点

\* 头结点是一直不包含数据的,它只起指向下一个节点的作用

比单向链表新增方法:  
 \* findLast() 找出了链表中的最后一个节点  
 \* dispReverse() 反序显示双向链表中的元素

## 3.操作 ##

一般建议使用双向链表,功能性更强

# 三.参考 #

1.[数据结构与算法JavaScript (三) 链表][JavaScript _]

2.[学习JavaScript数据结构与算法（二）：链表][JavaScript]

[Image 1]: 
[JavaScript _]: https://www.cnblogs.com/aaronjs/archive/2015/01/08/4207733.html
[JavaScript]: https://www.imooc.com/article/4593