JavaScript数据结构之双向链表和双向循环链表的实现
网络 2017-12-19 1369
双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。
双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代。这是双向链表的一个优点。
双向链表：单向链表只能向着一个方向遍历链表节点，而在节点指针域中增加了前向指针的双向链表，则可以向着两个方向遍历节点。这使得双向链表也可以在任何一个节点遍历整个链表。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | 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; }; } |
双向循环链表：将双向链表的头尾指针相连，就构成了双向循环链表。这种链表从任意一个节点都可以同时向两个方向进行节点遍历，查询节点的速度也是最快的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 | /*双向循环链表*/ 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; }; } |
下一篇：JS实现的找零张数最小问题示例
