一、链表数据结构

要存储多个元素，数组（或列表）可能是最常用的数据结构。然而这种数据结构有一个缺点，数字的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。
链表存储有序的元素集合，但不用于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的饮用（也称指针或链接）组成。下图展示了一个链表的结构

image.png

相对于传统的数组，链表的一个好处在于，添加或移动元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的一个细节是可以直接访问任何位置的元素，而想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。
举几个形象的例子来形容：

• 寻宝游戏：你有一条线索，这条线索是指向寻找下一条线索的地点的指针。你顺着这条链接去下一个地点，得到另一条指向再下一处的线索。得到列表中间的线索的唯一办法，就是从起点（第一条线索）顺着列表寻找
• 火车：一列火车是由一系列车厢组成，每节车厢相互连接，你很容易分离一节车皮，改变它的位置，添加或者移除它，车厢之间的连接就是指针

特点

• 链表是多个元素组成的列表
• 元素存储不连续，用next指针连接到一起
• JS中没有链表，但是可以用Object模拟链表

二、创建链表

下面我们实现一个链表类，并给他加点方法

class Node {  //节点类
    //构造函数
    constructor(item) { 
        this.item = item;
        this.next = null;
    }
}
class LinkedList {  // 链表类
    //构造函数
    constructor() { 
        this.head = null;
        this.length = 0;
    }
    //新增节点
    append(item) { 
        let node = new Node(item);
        let current; //暂存当前位置
        if(this.head === null) { // 如果头结点为空,当前节点作为头结点
            this.head = node;
        } else { 
            current = this.head;
            while(current.next) {     //遍历找到链表尾部
                current = current.next;
            }
            current.next = node;    //在链表尾部加入新节点
        }
        this.length++; //更新链表长度
    }
    //删除节点,并获得删除节点的值
    remove(index) { 
        if(index > -1 && index < this.length) { //预防下标越界
            var current = this.head;//暂存当前位置
            var previous; //暂存当前位置的前一个
            var position = 0;
            if(index === 0) {  //要删除的是第一个位置，就得改变头指针指向
                this.head = current.next;
            } else { 
                while(position++ < index) { //遍历直到current处于index位置
                    previous = current;
                    current = current.next;  //此时current处于index处,previous在index-1处
                }
                previous.next = current.next; //改变链表结构,跳过index处
            }
            this.length--; //更新链表长度
            return current.[图片上传中...(image.png-aecada-1661950439992-0)]
; //返回index处的值
        } else { 
            return null;    //下标越界返回空
        }
    }
    //插入节点
    insert(index, item) {
        if(index > -1 && index <= this.length) { 
            let node = new Node(item);
            let current = this.head;
            let previous;
            let position = 0;
            if(index === 0) { 
                node.next = current;
                this.head = node;
            } else { 
                while(position++ < index) { 
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            length++;
            return true; //插入成功
        } else { 
            return false; //插入失败
        }
    }
    //获取索引
    indexOf(item) { 
        let current = this.head;
        let position = 0;
        while(current) { 
            if(current.item === item) { 
                return position;
            }
            position++;
            current = current.next;
        }
        return -1; //未找到索引
    }
    //将链表转换成字符串
    toString() { 
        let current = this.head;
        let string = '';
        while(current) { 
            string += current.item + ((current.next ? ',': ''));
            current = current.next;
        }
        return string;
    }
    //链表长度
    size() { 
        return this.length;
    }
    //判断链表是否为空
    isEmpty() { 
        return this.length === 0;
    }
}

这样我们就实现了一个链表类，我们也为其添加了很多自定义方法

• 新增节点 append
• 删除节点 remove
• 插入节点 insert
• 获取索引 indexOf
• 链表转字符串 toString
• 获取链表长度 size
• 判断链表是否为空 isEmpty

未完待续......