数据结构-链表

[iuapwuxiaoliang]

链表

说道存储多个元素，数组可能是最常用的数据结构。这种数据结构非常方便，提供了便利店[]语法来访问它的元素。但是数组的缺点就是对元素进行插入或者删除操作的成本很高，需要移动元素。

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。链表的一个好处在于，增加或删除元素的时候不需要移动其它元素。数组的另一个细节是可以直接访问任何位置的任何元素，而要访问链表中间的一个元素，需要从起点开始迭代列表直到找到所需的元素。
创建链表
function LinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
}

链表的方法
append(element) -- 向链表尾部添加一个新的项

insert(position, element) -- 向链表的特定位置插入一个新的项

remove(element) -- 从链表中移除元素

indexOf(element) -- 返回元素在链表中的索引。如果链表中没有该元素则返回-1

removeAt(position) -- 从链表的特定位置移除一项

isEmpty() -- 如果链表中不包含任何元素，返回true，如果链表长度大于0返回false

size() -- 返回链表包含的元素个数
链表的完整代码
function LinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0;
var head = null;

   this.append = function(element){
       var node = new Node(element),current;
       if(head === null){
           head = node;
       } else {
           current = head;
           //循环列表，直到最后一项
           while(current.next){
               current = current.next;
           }
           //找到最后一项，将其next赋值为node
           current.next = node;
       }
       length++;
   };
   
   this.removeAt = function(position){
       if(position > -1 && position < length){
           var current = head,
           previous,
           index = 0;
           
           if(position === 0){
               head = current.next;
           } else {
               while(index++ < pisition){
                   previous = current;
                   current = current.next;
               }
               previous.next = current.next;
           }
           length--;
           
           return current.element;
       } else {
           return null;
       }
   };
   
   this.insert = function(position, element){
       if(position >= 0 && position <= length){
           var node = new Node(element),
           current = head,
           previous,
           index = 0;
           
           if(position === 0){
               node.next = current;
               head = node;
           } else {
               while(index++ < position){
                   previous = current;
                   current = current.next;
               }
               previous.next =node;
               node.next = current;
           }
           
           length++;
           
           return true;
       } else {
           return false;
       }
   };
   
   this.indexOf = function(element){
       var current = head, index = 0;
       while(current){
           if(element === current.element){
               return index;
           }
           index++;
           current = current.next;
       }
       return -1;
   };
   
   this.remove = function(element){
       var index = this.indexOf(element);
       return this.removeAt(index);
   }
   
   this.isEmpty = function(){
       return length === 0;
   }
   
   this.size = function(){
       return length;
   }
   
   this.getHead = function(){
       return head;
   }

}

双向链表
双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的。
function DoublyLinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0;
var head = null;
var tail = null;
this.insert = function(position, element){
if(position >= 0 && 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.previous = node;
head = node;
}
} else if(position === length){
current = tail;
current.next = node;
node.previous = current;
tail = node;
} 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,
        previous,
        index = 0;
        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 null;
    }
}

}