链表

[funnycoderstar]

每个元素由存储元素本身的节点和一个指向下一个元素的引用.

优点就是无需移动元素就可以轻松添加和移除元素.因此, 你需要添加和移除很多元素时, 最好的选择时链表, 而非数组.

JS实现链表

function LinkedList() {
    let Node = function(element) {
        this.element = element;
        this.next = null;
    }
    let length = 0;
    let head = null;
    // 向链表尾部追加元素
    this.append = function (element) {
        let node = new Node(element);
        let current;
        if(head === null) {
            head = node;
        } else {
            current = head;
            while(current.next) {
                current = current.next;
            }
            current.next = node;
        }
        length++;
    };
    this.insert = function(position, element) {
        if(position >= 0 && position <= length) {
            let node = new Node(element);
            let current = head;
            let previous;
            let index;
            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;
        }
    };
    // 从链表中移除元素
    this.removeAt = function(position) {
        if(position > -1 && position < length) {
            let current = head;
            let previous;
            let index = 0;
            if(position === 0) {
                head = current.next;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            length--;
            return current.element;
        } else {
            return null;
        }
    };
    this.remove = function(element) {
        let index = this.indexOf(length);
        return this.removeAt(index);
    };
    this.indexOf = function(element) {
        let current = head;
        let index = -1;
        while(current) {
            if(element == current.element) {
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    };
    this.isEmpty = function() {
        return length === 0;
    };
    this.size = function() {
        return length;
    };
    this.getHead = function() {
        return head;
    };
    this.toString = function() {
        let current = head;
        let string = '';
        while(current) {
            string += current.element + (current.next ? 'n': '');
            current = current.next;
        }
        return string;
    };
    this.print = function() {

    };
}
let list = new LinkedList();
list.append(15);
list.append(10);

双向链表

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);
            let current = head;
            let previous;
            let 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;
        }
        return false;
    };
    this.removeAt = function(position) {
        if(position >= 0 && position < length) {
            let current = head;
            let previous;
            let 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;
        }
    }
}

循环链表

循环链表可以像链表一样只有单向引用, 也可以像双向链表一样有双向引用.循环链表与链表之前唯一的区别在于, 最后一个元素指向下一个元素的指针(tail.next)不是引用null, 而是指向第一个元素(head)