/** * 判断单向链表是否为空 * @return {Boolean} 为空则返回true，不为空则返回false */ this.isAmpty = function() { return length === 0 }; /** * 将链表所有内容以字符串输出 * @return {String} 要输出的字符串 */ this.toString = function() { var current = head; var string = ''; while (current) { string += current.element; current = current.next; } return string; }; /** * 返回单向链表长度 * @return {Number} 单向链表的长度 */ this.size = function() { return length; };
双向链表
双向链表与单向链表很是相像。在单向链表中，只有指向下一个节点的链接。但在双向链表中，还有指向上一个节点的链接，是双向的。
JavaScipt中双向链表的实现
首先，依然是构造函数:
/** * 双向链表的构造函数 */ function DoublyLinkedList() { /** * 双向链表中节点的构造函数 * @param {Any} element 要传入链表的元素 */ var Node = function(element) { this.element = element; this.prev = null; this.next = null; } //双向链表的长度 var length = 0; //双向链表的头结点，初始化为NULL var head = null; //双向链表的尾结点，初始化为NULL var tail = null; }
双向链表需要有如下的方法:
append(element): 添加元素到双向链表尾部
insert(position,element): 向双向链表中某个位置插入元素
removeAt(position): 移除双向链表中某个位置的元素
showHead(): 获取双向链表的头部
showLength(): 获取双向链表长度
showTail(): 获取双向链表尾部
append方法:
说明: 添加元素到双向链表尾部
实现:
/** * 向链表尾部添加元素 * @param {Any} element 要加入链表的节点 * @return {Any} 加入链表的节点 */ this.append = function(element) { var node = new Node(element); if (head === null) { head = node; tail = node; } else { var previous; var current = head; while (current.next) { 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(position, element) { if (position >= 0 && position <= length) { var node = new Node(element); var index = 0; var previous; var current = head; if (position === 0) { if (head === null) { head = node; tail = node; } else { current.prev = node; node.next = current; head = node; } } else if (position === length) { current = tail; current.next = node; node.prev = current; tail = node; } else { while (index++ < position) { 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(position) { if (position > -1 && position < length) { var current = head; var index = 0; var previous; if (position === 0) { head = current.next; if (length === 1) { tail = null; head.prev = null; } } else if (position === length - 1) { current = tail; tail = current.prev; tail.next = null; } else { while (index++ < position) { 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; };
感想