由于链表在空间的合理利用上和插入，删除时不需要移动等的有点，因此在很多场合下，它是线性表的首选存储结构。然而，它也存在着实现某些基本操作，如求线性表长度时不如顺序存储结构的缺点；另一方面，由于在链表中，结点之间的关系使用指针来表示，则数据元素在线性表中的“位序”的概念已淡化，而被数据元素在线性链表中的“位置”所代替。为此，从实际出发重新定义线性链表及其基本操作
结构图：
1 (function(module){ 2 function List() { 3 this.head = null; 4 this.tail = null; 5 } 6 module.exports = List; 7 8 List.mergeList = function (a, b, compare) { 9 var ha = a.head; 10 var hb = b.head; 11 var pa = ha; 12 var pb = hb; 13 var c = new List(); 14 var q; 15 compare = compare || function (data1, data2) { 16 return data1 <= data2; 17 }; 18 19 while (pa && pb) { 20 var data1 = pa.data; 21 var data2 = pb.data; 22 23 if (!compare(data1, data2)) { 24 // delete head node 25 q = a.delFirst(); 26 // append the node to c linkedList 27 c.append(q); 28 pa = a.head; 29 } else { 30 q = b.delFirst(); 31 c.append(q); 32 pb = b.head; 33 } 34 } 35 36 if (pa) { 37 c.append(pa); 38 } else { 39 c.append(pb); 40 } 41 42 return c; 43 }; 44 45 List.prototype = { 46 makeNode: function(data, next){ 47 return { 48 data: data != null ? data : null, 49 next: next || null 50 }; 51 }, 52 delFirst: function () { 53 var head = this.head; 54 this.head = this.head.next; 55 head.next = null; 56 57 if(this.head === null) this.tail = null; 58 return head; 59 }, 60 append: function (node) { 61 if (this.head !== null) { 62 this.tail.next = node; 63 this.tail = this.tail.next; 64 } else { 65 this.head = node; 66 this.tail = node; 67 } 68 }, 69 add: function (data) { 70 if (this.head === null) { 71 this.head = this.makeNode(data); 72 this.tail = this.head; 73 } else { 74 this.tail.next = this.makeNode(data); 75 this.tail = this.tail.next; 76 } 77 78 this.tail.data = data; 79 }, 80 'delete': function (data) { 81 var current = this.head; 82 var previous = this.head; 83 var elem; 84 85 while (current !== null) { 86 if (data === current.data) { 87 if (current === this.head) { 88 this.head = current.next; 89 elem = current.data; 90 break; 91 } 92 93 if (current === this.tail) this.tail = previous; 94 95 previous.next = current.next; 96 elem = current.data; 97 break; 98 } 99 100 previous = current;101 current = current.next;102 }103 104 if(this.head === null) this.tail = null;105 106 return elem ? elem : false;107 },108 insertAsFirst: function (data) {109 var temp = this.makeNode(data);110 temp.next = this.head;111 this.head = temp;112 },113 insertAfter: function (target, data) {114 var current = this.head;115 while (current !== null) {116 if (current.data === target) {117 var temp = this.makeNode(data);118 temp.next = current.next;119 120 if (current === this.tail) this.tail = temp;121 122 current.next = temp;123 return;124 }125 126 current = current.next;127 }128 },129 item: function (index) {130 var current = this.head;131 132 while (current !== null) {133 if (--index === 0) return current;134 135 current = current.next;136 }137 138 return null;139 },140 each: function (callback) {141 var current = this.head;142 143 while (current !== null) {144 callback(current);145 current = current.next;146 }147 },148 orderInsert: function(data, cmp){149 cmp = typeof cmp === 'function' ? cmp : function (a, b){150 if(a > b)151 return 1;152 else if(a === b)153 return 0;154 else155 return -1;156 };157 var previous = this.head;158 var current = this.head;159 160 if(current === null){161 this.head = this.tail = this.makeNode(data);162 return;163 }164 165 var me = this;166 while(current){167 var ret = cmp(data, current.data);168 // 如果插入元素大于当前元素，准备下次遍历169 if(ret > 0){170 previous = current;171 current = current.next;172 173 // 如果等于，直接插入到后面174 } else if(ret === 0){175 return insertBetween(data, previous, current);176 177 // 如果小于则插入到前节点和当前节点中178 // 因为已经是排序了，所以不需要多余判断了179 } else {180 if(this.head === previous && previous === current){181 return this.insertAsFirst(data);182 } else {183 return insertBetween(data, previous, current);184 }185 }186 }187 188 // 插入到最后一个结点189 previous.next = this.makeNode(data);190 this.tail = previous.next;191 192 function insertBetween(data, a, b){193 var temp = me.makeNode(data);194 temp.next = b;195 a.next = temp;196 return true;197 }198 }199 };200 /*201 var list = new List();202 list.add('b');203 list.insertAsFirst('a');204 list.insertAfter('b', 'c');205 console.log(list.item(2));206 console.log(JSON.stringify(list));207 list.each(function (node) {208 if (node.data === 'b') {209 console.log('get b in each');210 }211 });212 list['delete']('c');213 list['delete']('a');214 console.log(list);215 216 var list2 = new List();217 list2.add('c');218 list2.insertAsFirst('d');219 list2.insertAfter('d', 'b');220 console.log(JSON.stringify(list2));221 222 var list3 = List.mergeList(list, list2);223 console.log(list3);224 */225 /*226 var list = new List();227 228 list.orderInsert('e');229 list.orderInsert('b');230 list.orderInsert('c');231 list.orderInsert('a');232 list.orderInsert('d');233 list.orderInsert('f');234 */235 }(this.module || this));
以下是对应的单元测试代码：
1 describe('linkedList tests', function(){ 2 3 var list = new List(); 4 5 it('should find the second item', function(){ 6 list.add('b'); 7 expect(list.head.data).toBe('b'); 8 expect(list.tail.next).toBe(null); 9 10 list.insertAsFirst('a');11 expect(list.head.data).toBe('a');12 expect(list.head.next.data).toBe('b');13 14 list.insertAfter('b', 'c');15 expect(list.item(2).data).toBe('b');16 expect(list.tail.data).toBe('c');17 });18 19 it('should remove one item', function(){20 expect(list['delete']('c')).toBe(true);21 list['delete']('a');22 expect(list.head.data).toBe('b');23 });24 25 var list2 = new List();26 27 it('should match the json', function(){28 list2.add('c');29 list2.insertAsFirst('d');30 list2.insertAfter('d', 'b');31 expect(JSON.stringify(list2)).toBe('{"head":{"data":"d","next":{"data":"b","next":{"data":"c","next":null}}},"tail":{"data":"c","next":null}}');32 });33 34 it('should merge the lists', function(){35 var list3 = List.mergeList(list, list2);36 expect(list3.head.data).toBe('d');37 expect(list3.head.next.data).toBe('b');38 expect(list3.head.next.next.data).toBe('c');39 expect(list3.tail.data).toBe('b');40 });41 });