>[success] # 实现一个链表 ~~~ 1.首先链表不是一个连续的内存空间，针对这条我们采取'对象形式'，即有多少个链表 项则对应生成多少个'对象' 2.每个元素由'一个存储元素本身的节点'和'一个指向下一个元素的引用'（也称指针或链接）组成,因此针对 '第一条每个对象来说，需要存储两个东西，一个是本身该结点要存的值，与其相邻的下一个结点对象' 3.如果当前链表为空，它的头部和尾部都为'undefind',有值它的尾部应该为'undefind'，要注意的是链表是 通过'头结点依次向下找到我们需要的元素'，因此头结点的存储很重要 ~~~ * 链表效果图  * 针对第二条解释的效果图  >[info] ## 实现一个链表 ~~~ 1.我们的链表要具备的方法： push(element)：向链表尾部添加一个新元素。 insert(element, position)：向链表的特定位置插入一个新元素。 getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回 undefined。 remove(element)：从链表中移除一个元素。 indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。 removeAt(position)：从链表的特定位置移除一个元素。 isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0则返回 false。 size()：返回链表包含的元素个数，与数组的 length 属性类似。 toString()：返回表示整个链表的字符串。由于列表项使用了 Node 类，就需要重写继 承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。 ~~~ >[danger] ##### 代码实现 ~~~ 1.在上面的分析时候，说过链表是非连续的空间，我们需要给'每个节点创建对象',并且这个节点存储的两个东西 '当前节点的值'，'当前节点对应的下一个节点内存指向'，因此根据这两点创建一个类 // 保存Node 节点 指针 class Node { constructor(element){ this.element = element this.next = undefined } } 比较元素的公共方法 function defaultEquals(a, b) { return a === b; } ~~~ ~~~ class LinkedList{ // 在使用链表初始化的时候，需要参数 // count 记录当前链表有多少元素 // head 当前链表头结点 有头结点才能依次往下找 constructor(equalsFn = defaultEquals){ this.equalsFn = equalsFn this.count = 0 // 链表中的元素数量 this.head = undefined // 保存引用 } // 添加元素 /* 要注意有两点考 1.如果当前头部为undefined说明链表此时无数据，要插入的元素则直接为头结点并且要记录 2.如果头结点有数据要依次循环找到要插入结点的位置 */ push(element){ // 创建每一个结点储存对象 const node = new Node(element) let current if(this.head == null){ this.head = node }else{ current = this.head while(current.next!=null){ current = current.next } current.next = node } this.count ++ // 增加链表数据个数 } // 目标索引位置获取当前元素 /* 有两种情况 1.当前索引为无效索引返回undefined 2.当前索引为有效索引 返回当前结点 */ getElementAt(index){ if(index<=this.count && index>= 0){ let node = this.head for(let i=0;i<index;i++){ node = node.next } return node } return undefined } // 删除指定元素通过坐标 /* 1.首先判断删除的元素是否存在 2.如果删除的是首位应该重新给head 规定新的赋值 3.如果是其他位置需要将删除项前后结点重新连接 */ removeAt(index){ // 判断是否越界 if(index<this.count && index>=0){ // 判断是否是头部元素 let current = this.head if(index === 0){ this.head = current.next }else{ // 获取删除项的前一位 const previous = this.getElementAt(index-1) current = previous.next // 让相邻的相互连接 previous.next = current.next } this.count -- return current.element } return undefined } // 插入和删除 逻辑思维方式类似的 insert(element, index) { if (index >= 0 && index <= this.count) { const node = new Node(element); if (index === 0) { const current = this.head; node.next = current; this.head = node; } else { const previous = this.getElementAt(index - 1); node.next = previous.next; previous.next = node; } this.count++; return true; } return false; } // 查询链表中元素的位置 indexOf(element) { let current = this.head; for (let i = 0; i < this.size() && current != null; i++) { if (this.equalsFn(element, current.element)) { return i; } current = current.next; } return -1; } // 删除链表中删除的元素 remove(element) { const index = this.indexOf(element); return this.removeAt(index); } isEmpty() { return this.size() === 0; } size() { return this.count; } getHead() { return this.head; } clear() { this.head = undefined; this.count = 0; } toString() { if (this.head == null) { return ''; } let objString = `${this.head.element}`; let current = this.head.next; for (let i = 1; i < this.size() && current != null; i++) { objString = `${objString},${current.element}`; current = current.next; } return objString; } } ~~~