![JavaScript数据结构之双向链表和双向循环链表的实现 JavaScript数据结构之双向链表和双向循环链表的实现](/rjstyle/noimg/12.webp)
双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素。
双向链表提供了两种迭代列表的方法:从头到尾,或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新开始迭代。这是双向链表的一个优点。
双向链表:单向链表只能向着一个方向遍历链表节点,而在节点指针域中增加了前向指针的双向链表,则可以向着两个方向遍历节点。这使得双向链表也可以在任何一个节点遍历整个链表。
function DoublyLinkedList() { var Node = function(element) { this.element = element; this.next = null; this.prev = null; }; var length = 0, head = null, tail = null; this.append = function(element){ var node = Node(element), current, previous; if(!head){ head = node; tail = node; }else{ current = head; while(current){ previous = current; current = current.next; } node.next = current; current.prev = node; previous.next = node; node.prev = previous; } length++; return true; } this.insert = function(position,element){ if(position > -1 && position < length){ var node = new Node(element), current = head, previous, index = 0; if(position === 0){ if(!head){ head = node; tail = node; }else{ node.next = current; current.prev = node; head = node; } }else if (position === length -1){ current = tail; current.next = node; node.prev = current; }else { while(index++ < position){ previous = current; current = current.next; } node.next = current; previous.next = node; current.prev = node; node.prev = previous; } length++; return true; }else{ return false; } }; this.removeAt = function(position){ if(position > -1 && position < length){ var current = head, index = 0, previous; if (position === 0) { head = current.next; if(length === 1){ tail = null; }else{ head.prev = null; } }else if(position === length - 1){ current = tail; tail = current.prev; tail.next = null; } else{ while(index++ < position){ previous = current; current = current.next; } previous.next = current.next; current.next.prev = previous; }; length-- ; return current.element; }else{ return false; } }; this.remove = function(element){ var current = head, previous; if(current.element === element){ head = current.next; } previous = current; current = current.next; while(current){ if (current.element = element) { previous.next = current.next; current.next.prev = previous; }else{ previous = current; current = current.next; } } return false; }; this.remove = function(){ if (length === 0) { return false; }; var current = head, previous; if(length === 1){ head = null; tail = null; length--; return current.element; } while(current){ previous = current; current = current.next; } previous.next = null; length--; return current.element; }; this.indexOf = function(element){ var current = head, index = 0; while(current && index++ < length){ if (current.element === element) { return index; }; current = current.next; } return false; }; this.isEmpty = function(){ return length === 0; }; this.size = function(){ return length; }; this.toString = function(){ var current = head, string = ''; while(current){ string += current.element; current = current.next; } return string; }; this.getHead = function(){ return head; }; this.getTail = function(){ return tail; }; }
双向循环链表:将双向链表的头尾指针相连,就构成了双向循环链表。这种链表从任意一个节点都可以同时向两个方向进行节点遍历,查询节点的速度也是最快的。
/*双向循环链表*/ function DoublyCircularLinkedList(){ var Node = function(element){ this.element = element; this.next = null; this.prev = null; }; var length = 0, head = null, tail = null; this.append = function(element){ var node = new Node(element), current, previous; if (!head) { head = node; tail = node; head.prev = tail; tail.next = head; }else{ current = head; while(current.next !== head){ previous = current; current = current.next; } current.next = node; node.next = head; node.prev = current; }; length++; return true; }; this.insert = function(position, element){ if(position >= 0 && position <= length){ var node = new Node(element), index = 0, current = head, previous; if(position === 0){ if(!head){ node.next = node; node.tail = node; head = node; tail = node; }else{ current.prev = node; node.next = current; head = node; node.prev = tail; } }else if(position === length){ current = tail; current.next = node; node.prev = current; tail = node; node.next = head; }else{ while(index++ < position){ previous = current; current = current.next; } current.prev = node; node.next = current; previous.next = node; node.prev = previous; } length++; return true; }else{ return false; } }; this.removeAt = function(position){ if(position > -1 && position < length){ var current = head, index = 0, previous; if(position === 0){ current.next.previous = tail; head = current.next; }else if(position === length - 1){ current = tail; current.prev.next = head; head.prev = current.prev; tail = current.prev; }else{ while(index++ < position){ previous = current; current = current.next; } previous.next = current.next; current.next.prev = previous; } length--; return true; }else{ return false; } }; this.remove = function(element){ var current = head, previous, indexCheck = 0; while(current && indexCheck < length){ if(current.element === element){ if(indexCheck === 0){ current.next.prev = tail; head = current.next; }else{ current.next.prev = previous; previous.next = current.next; } length--; return true; } previous = current; current = current.next; indexCheck++; } return false; }; this.remove = function(){ if(length === 0){ return false; } var current = head, previous, indexCheck = 0; if(length === 1){ head = null; tail = null; length--; return current.element; } while(indexCheck++ < length){ previous = current; current = current.next; } previous.next = head; tail = previous.next; length--; return current.element; }; this.indexOf = function(element){ var current = head, index = 0; while(current && index++ < length){ if(current.element === element){ return index; } current = current.next; } return false; }; this.toString = function(){ var current = head, indexCheck = 0, string = ''; while(current && indexCheck < length){ string += current.element; indexCheck++; current = current.next; } return string; }; this.isEmpty = function(){ return length === 0; }; this.getHead = function(){ return head; }; this.getTail = function(){ return tail; }; this.size = function(){ return length; }; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。