JavaScript数据结构与算法——链表

1.链表数据结构

链表存储有序的元素集合，但不同于数组，链表中的元素咋内存中并不是连续放置的每个元素有一个存储元素本身的节点和一个指向下一个元素的引用组成。下图展示了一个链表的结构：

链表的优点：

链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；

添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点：

因为含有大量的指针域，占用空间较大；

查找元素需要遍历链表来查找，非常耗时。

适用场景：

数据量较小，需要频繁增加，删除操作的场景

2.创建链表

function LinkedList() {
    // 创建一个node类，表示将要加入的项 element表示要添加的值，next指向列表中下一个节点项的指针
    let Node = function(element) {
        this.element = element;
        this.next = null;
    }
    let length = 0;
    let head = null;
    // 下面声明链表的方法
    // 1.向列表尾部添加一个新的项
    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++;
    }
    // 2.从列表中移除元素
    this.removeAt = function(position) {
        // 检查position是否超出链表范围
        if(position > -1 && position < length) {
            let current = head,
                previous,
                index = 0;
            // 移除第一个元素
            if(position === 0 ) {
                head = current.next;
            } else {
                // 循环到指定位置，找到该位置的 previous和current
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // 将previous与current的下一项链接起来：跳过current
                previous.next = current.next;
            }    
            // 链表长度减一
            length--;
            // 返回被删除项
            return current.element;
        } else {
            // 不是有效位置，返回null
            return null
        }
    }
     // 3.在任意位置插入元素
    this.insert = function(element, position) {
        //判断是否超过链表范围
        if (position >= 0 && position<= length) {
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            // 在首位插入元素
            if (position === 0 ) {
                node.next = current;
                head = node;
            } else{
                // x循环到position应该添加的位置，取出previous和current
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // 在previous和current间插入
                node.next = current;
                previous.next = node;
            };    
            // 更新链表长度
            length++;
            return true;
        } else{
            return false;
        };
    }
    //4. 把LinkedList对象转化成字符串
    this.toString = function() {
        let current = head,
            string = '';
        while(current) {
            string += current.element + (current.next ? 'n' : '');
            current = current.next;
        }  
        return string;  
    }
    //5.链表中是否存在某个值
    this.indexOf = function(element) {
        let current = head,
            index = 0;
        while(current) {
            if(element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }  
        return -1; 
    } 
    //6.通过element实现remove元素
    this.remove = function(element) {
        let index = this.indexOf(element);
        return this.removeAt(index);
    }
    //7.isEmpty size getHead方法
    this.isEmpty = function() {
        return length === 0; 
    }
    this.size = function() {
        return length;
    }
    this.getHead = function() {
        return head;
    }    
}