您的当前位置：首页 JavaScript趣题：有序列表

JavaScript趣题：有序列表

来源：华拓科技网

有序列表区别于无序列表，它里面存储的元素都是一种有序的状态，比如说递增或递减。在很多有序列表的实现中，你肯定找不到类似addAfter的操作，因为它是无序列表的特性之一。

一般的有序列表都会提供几个基本操作：

1.add用于将元素添加到列表中，并维持其有序状态

2.get操作，用于获取指定索引下的元素

3.length属性或方法获取列表长度

这些操作中，add是最重要的一部分，实现它通常是由3部分组成（以递增序列为例）：

1.从左到右遍历列表，直到找到大于或等于插入值的元素，此时这个元素所在的位置，便是要插入的位置

2.将插入位置右边的元素通通向后移动一位

3.将值插入该位置

function SortedList() { 
 this.length = 0; 
 this.elementData = []; 
} 
 
SortedList.prototype.add = function(val) { 
 var array = this.elementData; 
 for(var i=0;i<array.length;i++){ 
 if(val <= array[i]){ 
 break; 
 } 
 } 
 for(var j=array.length-1;j>=i;j--){ 
 array[j+1] = array[j]; 
 } 
 array[i] = val; 
 this.length++; 
} 
 
SortedList.prototype.get = function(i) { 
 return this.elementData[i]; 
}