数据结构与算法之链表

function Node (element){
this.element = element;
this.next = null;
        }

function LinkedList(){
this.length = 0;
this.head = null;
        }

        LinkedList.prototype = {
//向表尾添加一个元素
            append :function(element){        
var node = new Node(element),current;
if(this.head === null){
this.head = node;
                }else {
                    current = this.head;
while(current.next){
                        current = current.next;
                    }
                    current.next = node;
                }
                length++;
            },
//任意位置插入一个元素
            insert :function(position,element){        
if(position >= 0 && position <= length){
var node = new Node(element),
                        current = this.head,
                        previous,
                        index = 0;
if(position === 0 ){
                        node.next = current;
this.head = node;
                    } else {
while(index ++ < position){
                            previous = current;
                            current  = current.next;
                        }
                        node.next = current;
                        previous.next = node;
                    }
                    length++;
return true;
                } else {
return false;
                }
            },
//移除指定项
            removeAt :function(position){                
if(position>-1 && position <length){
var current = this.head,
                        previous,
                        index = 0;
if(position === 0){
this.head = current.next;
                    } else {
while(index++ < position){
                            previous = current;
                            current = current.next;
                        }
                        previous.next = current.next;
                    }
                    length--;
return current.element;
                } else {
return null;
                }
            },
//删除一个元素
            tremove :function(element){            
var index = this.indexOf(element);
return this.removeAt(index);
            },
//查找元素的索引
            indexOf :function(element){        
var current = this.head,
                    index = -1;
while(current){
if(element === current.element){
return index;
                    }
                    index ++;
                    current = current.next;
                }
return -1;
            },
            isEmpty :function(){
return length === 0;
            },
            size :function(){
return length;
            },
//打印链表元素
            toString :function(){            
var current = this.head,
                    string='';
while(current){
                    string += current.element + " ";
                    current = current.next;
                }
return string;
            },
            getHead :function(){
return this.head;
            },
        };

//test
var list = new LinkedList();
        list.append('a');
        list.append('b');
        list.append('c');
        list.append('d');
        console.log(list.toString());
        list.insert('2','test');
        console.log(list.toString());


/////////////////////////////////////////////////////////////////////////双向链表

function DoublyNode(element){
this.element = element;
this.next = null;
this.prev = null;
        };

function DoublyLinkedList(){
this.length = 0;
this.head = null;
this.tail = null;
        };

        DoublyLinkedList.prototype = {
            insert:function(position,element){            //任意位置插入一个元素
if(position >= 0 && position <= this.length){
var node = new DoublyNode(element),
                        current = this.head,
                        previous,
                        index = 0;
if(position === 0){        //第一个位置添加
if(!this.head){
this.head = node;
this.tail = node;
                        } else {
                            node.next = current;
                            current.prev = node;
this.head = node;
                        }
                    } else if(position === this.length){        //最后一项添加
                        current = this.tail;
                        current.next = node;
                        node.prev = current;
this.tail = node;
                    } else {
while(index++ < position){
                            previous = current;
                            current = current.next;
                        }
                        node.prev  = previous;
                        node.next = current;
                        previous.next = node;
                        current.prev = node;
                    }
                    length++;
return true;
                } else {
return false;
                }
            },
            removeAt :function(position){                //任意位置移除元素
if(position > -1 && position < this.length){
var current = this.head,
                        previous,
                        index=0;
if(position === 0){            //移除第一项
this.head = current.next;
if(this.length === 1){
this.tail = null;
                        } else {
this.head.prev = null;
                        }
                    } else if(position === this.length-1){    //移除最后一项
                        current = this.tail;
this.tail = current.prev;
this.tail.next = null;
                    } else {
while(index++ < position){
                            previous = current;
                            current = current.next;
                        }
                        previous.next = current.next;
                        current.next.prev = previous;
                    }
this.length--;
return current.element;
                } else {
return null;
                }
            },
        };