JavaScript数据结构与算法之链表_基础知识_脚本之家

链表简介

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

单向链表

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

JavaScipt中单向链表的实现

首先,创建一个构造函数。

/** * 单向链表构造函数 */function LinkedList() { /** * 单向链表中节点的构造函数 * @param {Any} element 要传入链表的节点 */ var Node = function { this.element = element; //下个节点的地址 this.next = null; } //单向链表的长度 var length = 0; //单向链表的头结点,初始化为NULL var head = null;}

不难看出,单向链表构造函数比栈与队列要复杂许多。单向链表需要有如下的方法:

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

append方法:

说明: 向单向链表尾部添加元素。实现:

/** * 向单向链表尾部添加元素 * @param {Any} element 要加入链表的节点 */this.append = function { var node = new Node; var current; if  { head = node; } else { // 当前项等于链表头部元素. // while循环到最后一个,从而将该节点加入链表尾部。 current = head; // 当next为null时,判定为false。退出循环。 while  { current = current.next; } current.next = node; } length++;};

insert方法:

说明: 向单向链表中某个位置插入元素。实现:

/** * 向单向链表中插入某个元素 * @param {Number} position 要插入的位置 * @param {Any} element 要插入的元素 * @return {Boolean} 插入成功返回true,失败返回false */this.insert = function { if (position >= 0 && position <= length) { var node = new Node; var current = head; var previous; var index = 0; if  { node.next = current; head = node; } else { while  { previous = current; current = current.next; } previous.next = node; node.next = current; } length++; return true; } else { return false; }};

indexOf方法:

说明:寻找某个元素在单向链表中的位置。实现:

/** * 寻找某个元素在单向链表中的位置 * @param {Any} element 要寻找的元素 * @return {Number} 返回值>=0则代表找到相应位置 */this.indexOf = function { var current = head; var index = -1; while  { if (element === current.element) { return index; } index++; current = current.next; } return -1;};

remove方法:

说明: 移除给定的元素。实现:

/** * 移除给定的元素 * @param {Any} element 要移除的元素 * @return {Number} 返回值>=0表示移除成功 */this.remove = function { var index = this.indexOf; return this.removeAt;};

removeAt方法:

说明:移除单向链表中某个位置的元素。实现:

/** * 移除单向链表中某一个元素 * @param {Number} position 要移除元素的位置 * @return {Any} 移除成功返回被移除的元素,不成功则返回NULL */this.removeAt = function { if (position > -1 && position < length) { var current = head; var previous; var index = 0; if  { // 因为之前head指向第一个元素,现在把head修改为指向第二个元素。 // 核心概念在于链表前后全靠指针链接,而非数组一般。 // 所以只需要改变head的元素。 head = current.next; } else { while  { // previous指要操作元素位置之前的那个元素,current表示之后的那个元素。 previous = current; current = current.next; } previous.next = current.next; } length--; return current.element; } else { return null; }};

getHead方法:

说明:获取单向链表的头部。实现:

/** * 获取单向链表的头部 * @return {Any} 单向链表的头部 */this.getHead = function() { return head;}

isAmpty、toString、size方法

/** * 判断单向链表是否为空 * @return {Boolean} 为空则返回true,不为空则返回false */this.isAmpty = function() { return length === 0};/** * 将链表所有内容以字符串输出 * @return {String} 要输出的字符串 */this.toString = function() { var current = head; var string = ''; while  { string += current.element; current = current.next; } return string;};/** * 返回单向链表长度 * @return {Number} 单向链表的长度 */this.size = function() { return length;};

双向链表

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

JavaScipt中双向链表的实现

首先,依然是构造函数:

/** * 双向链表的构造函数 */function DoublyLinkedList() { /** * 双向链表中节点的构造函数 * @param {Any} element 要传入链表的元素 */ var Node = function { this.element = element; this.prev = null; this.next = null; } //双向链表的长度 var length = 0; //双向链表的头结点,初始化为NULL var head = null; //双向链表的尾结点,初始化为NULL var tail = null;}

双向链表需要有如下的方法:

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

append方法:

说明: 添加元素到双向链表尾部实现:

/** * 向链表尾部添加元素 * @param {Any} element 要加入链表的节点 * @return {Any} 加入链表的节点 */this.append = function { var node = new Node; if  { head = node; tail = node; } else { var previous; var current = head; while  { current = current.next; } current.next = node; node.prev = current; tail = node; } length++; return node;};

insert方法:

说明: 向双向链表中某个位置插入元素。实现:

/** * 向链表中插入某个元素 * @param {Number} position 要插入的位置 * @return {Boolean} 插入成功返回true,失败返回false */this.insert = function { if (position >= 0 && position <= length) { var node = new Node; var index = 0; var previous; var current = head; if  { if  { head = node; tail = node; } else { current.prev = node; node.next = current; head = node; } } else if  { current = tail; current.next = node; node.prev = current; tail = node; } else { while  { previous = current; current = current.next; } previous.next = node; node.prev = previous; current.prev = node; node.next = current; } length++; return true; } else { return false; }};

removeAt方法:

说明:移除双向链表中某个位置的元素。实现:

/** * 移除链表中某一个元素 * @param {Number} position 要移除元素的位置 * @return {Any} 移除成功返回被移除的元素,不成功则返回false */this.removeAt = function { if (position > -1 && position < length) { var current = head; var index = 0; var previous; if  { head = current.next; if  { tail = null; head.prev = null; } } else if (position === length - 1) { current = tail; tail = current.prev; tail.next = null; } else { while  { previous = current.prev; current = current.next; } previous.next = current.next; current.next.prev = previous; } length--; return current.element; } else { return false; }};

showHead、showLength、showTail方法

/** * 获取链表的头部 * @return {Any} 链表的头部 */this.showHead = function() { return head;};/** * 获取链表长度 * @return {Number} 链表长度 */this.showLength = function() { return length;};/** * 获取链表尾部 * @return {Any} 链表尾部 */this.showTail = function() { return tail;};

感想

链表这一节,基本全部都是先按需求写代码,写完后再和书上对比。发现简直被瞬间秒成渣。自己写的很多暗坑,逻辑也很混乱。看来还是太年轻了。

相关文章

发表评论