JS实现数据结构与算法系列:功能完整的线性链表

  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         else 
155           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 });