链表

链表数据结构

大多数语言中数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和指向下一个元素的引用（也称为指针或链接）组成。链表添加或移除元素不需要移动其他元素，然而链表需要使用指针。数组可以访问任意位置的元素，要访问链表元素需要从起点(表头)开始迭代列表直到找到所需的元素。

创建链表

function LinkedList() {
    //要加入列表的项
    let Node = function(element) {
        this.element = element;
        this.next = null;
    };
    let length = 0;
    let head = null;
    this.append = function(element){};
    this.insert = function(position, element) {};
    this.removeAt = function(position) {};
    this.remove = function(element) {};
    this.indexOf = function(element) {};
    this.isEmpty = function(){};
    this.size = function(){};
    this.getHead = function(){};
    this.toString = function(){};
    this.print = function(){};
}

向链表尾部追加元素

列表为空，添加的是第一个元素，或者列表不为空，向其追加元素。

this.append = function(element){
    let 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++;  //更新链表长度
};

从链表中移除元素

移除第一个元素或移除第一个以外的任一元素。我们要实现两种remove方法：第一种是从特定位置移除一个元素，第二种是根据元素的值移除元素。

this.removeAt = function(position) {
    //检查越界值
    if(position > -1 && position <length) {
        let current = head, previous, index = 0;
        //移除第一项
        if(position === 0) {
            head = current.next;
        } else {
            while(index++ < position) {
                previous = current;
                current = current.next;
            }
            //将previous于current的下一项连接起来：跳过current，从而移除他
            previous.next = current.next;
        }
        length--;
        return current.element;
    } else {
        return null;
    }
};

在任意位置插入元素

this.insert = function(position, element) {
    //检查越界值
    if(position >= 0 && position <= length){
        let 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;
            }
            node.next = current;
            previous.next = node;
        }
        length++;
        return true;
    } else{
        return false;
    }
};

实现其他方法

//toString()
this.toString = function(){
    let current = head, string = '';
    while(current) {
        string += current.element + (current.next ? 'n' : '');
        current = current.next;
    }
    return string;
};
//indexOf()
this.indexOf = function(element) {
    let current = head, index = -1;
    while(current) {
        if(element === current.element) {
            return index;
        }
        index++;
        current = current.next;
    }
    return -1;
};
//remove()
this.remove = function(element) {
    let index = this.indexOf(element);
    return this.removeAt(index)
};
this.isEmpty = function(){
    return length === 0;
};
this.size = function(){
    return length;
};
this.getHead = function(){
    return head;
};

双向链表

在双向链表中，链接是双向的。先从实现DoublyLinkedList类所需的变动开始：

function DoublyLinkedList() {
    let Node = function(element) {
        this.element = element;
        this.next = null;
        this.prev = null;
    };
    let length = 0;
    let head = null;
    let tail = null;
    //方法
}

在任意位置插入新元素

this.insert = function(position, element) {
    //检查越界值
    if(position >= 0 && position <= length) {
        let node = new Node(element),current = head, previous, index = 0;
        if(position === 0) {
            if(!head) {
                head = node;
                tail = node;
            } else {
                node.next = current;
                current.prev = node;
                head = node;
            }
        } else if(position === length) {
            current = tail;
            current.next = node;
            node.prev = 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) {
        let current = head, previous, index = 0;
        //移除第一项
        if(position === 0) {
            head = current.next;
            //如果只有一项，更新tail
            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;
    }
};