1 链表

链表和数组的特性

数组；

优点：数组的创建通常需要申请一段连续的内存空间。每个元素都是连续紧邻分配，查找的时间复杂度是O(1)，效率很高。

缺点：在使用数组时，在开始或特定索引处添加/删除元素这样的操作可能是一项性能较低的任务，因为我们必须移动所有其他元素的索引。

链表：

优点：链表中的元素在内存中不必是连续的空间。可以充分利用计算机的内存，实现灵活的内存动态管理.链表在插入和删除数据时，时间复杂度可以达到O(1)。

缺点：链表访问任何一个位置的元素时，都需要从头开始访问(无法跳过第一个元素访问任何一个元素)。并且无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的问题。

数据以查为主，很少涉及到增和删，选择数组。
如果数据涉及到频繁的插入和删除，或元素所需分配空间过大，倾向于选择链表。

对链表的理解

单向链表中每个节点都有两个属性：数据和指向。节点内的指针指向列表中的下一个节点。链表中的第一个节点称为head。最后的节点指向null。
就像火车一样：火车头是head，每一节车厢是节点，车厢中乘客（数据），上一节车厢通过车钩（指向）连接下一节车厢（节点）

2 单向链表封装

封装了一个单向链表，实现的方法代码中有注释。

//创建Node类
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
    //1.向链表尾部添加一个新的项
    append(data) {
        let node = new Node(data);
        if (this.head) {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = node;
        } else {
            this.head = node;
        }
        this.length += 1;
    }
    //2.toString方法
    toString() {
        let current = this.head;
        let resString = '';
        while (current) {
            resString += current.data + ' ';
            current = current.next;
        }
        return resString;
    }
    //3.向链表特定位置插入一个新的项
    insert(position, data) {
        if (position < 0 || position > this.length) return false;
        let node = new Node(data);
        if (position == 0) {
            node.next = this.head;
            this.head = node;
        } else {
            let current = this.head;
            let previous = null;
            let index = 0;
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            previous.next = node;
            node.next = current;
        }
        this.length += 1;
        return true;
    }
    //4.获取对应位置的元素
    get(position) {
        if (position < 0 || position >= this.length) return null;
        let current = this.head;
        let index = 0;
        while (index++ < position) {
            current = current.next;
        }
        return current.data;
    }
    //5.返回元素在列表中的索引，如果没有则返回-1
    indexOf(data) {
        let current = this.head;
        let index = 0;

        while (current) {
            if (current.data == data) {
                return index;
            }
            current = current.next;
            index += 1;
        }
        return -1;
    }
    //6.修改某个位置的元素
    update(position, newData) {
        if (position < 0 || position >= this.length) return false;
        let current = this.head;
        let index = 0;
        while (index++ < position) {
            current = current.next;
        }
        current.data = newData;
        return true;
    }
    //7.从列表的特定位置移除一项
    removeAt(position) {
        if (position < 0 || position >= this.length) return null;
        let current = this.head;
        let previous = null;
        let index = 0;
        if (position == 0) {
            this.head = this.head.next;
        } else {
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        this.length -= 1;
        return current.data;
    }
    //8.从列表中移除一项
    remove(data) {
        let position = this.indexOf(data);
        return this.removeAt(position);
    }
    //9.size方法
    size() {
        return this.length;
    }
}

//测试代码
let list = new LinkedList();
list.append('aaa');
list.append('bbb');
console.log(list.toString());
// console.log(list);
list.insert(0, 'ccc');
// console.log(list);
list.insert(1, 'ddd');
console.log(list);
console.log(list.get(3));
console.log(list.indexOf('aaa'));
console.log(list.indexOf('d'));
console.log(list);
list.update(3, '111');
console.log(list);
list.removeAt(2);
console.log(list.removeAt(2));
console.log(list);
// console.log(list.remove('aaa'));
list.remove('ccc');

console.log(list);
list.append('eee');
console.log(list.size());
复制代码