javaScript数据结构--链表

实现一个链表还需要一个辅助的类：Node，Node对象有2个属性，element :当前元素；next:指向下一个对象的指针。

Node对象结构 链表结构

链表的实现：

function LinkedList() {

    var Node = function(element) {

        this.element = element;

        this.next = null;

    }

    var length = 0;

    var head = null;

    this.append = function(element) {

        const 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) {

            const node = new Node(element);

            let current = head,

                previous,

                index = 0;

            if(position === 0) {

                head.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.remove = function(element) {

        const index = this.indexOf(element);

        return this.removeAt(index);

    }

    this.removeAt = function(position) {

        if(position >= 0 && position <= length) {

            var current = head,

                previous,

                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.isEmpty = function() {

        return length === 0

    }

    this.size = function() {

        return length;

    }

    this.toString = function() {

        var current = head,

            string = '';

        while(current) {

            string += String(current.element);

            current = current.next;

        }

        return string;

    }

    this.indexOf = function(element) {

        var current = head,

            index = -1;

        while(current) {

            index++;

            if(current.element === element) {

                return index;

            }

            current = current.next;

        }

        return -1;

    }

    this.getHead = function() {

        return head;

    }

}

var l = new LinkedList();

l.append("a");

l.append("b");

l.append("c");

console.log(l.size()); // 3

console.log(l.toString()); // abc

l.insert(1, "d")

console.log(l.size()); // 4

console.log(l.toString()); // adbc

console.log(l.indexOf("e")); // -1

console.log(l.indexOf("b")); // 2

l.removeAt(2);

console.log(l.toString()); // adc

l.remove("a"); // dc

console.log(l.toString());

l.remove("dd");

console.log(l.toString()); // dc