我自己的理解

首先每个元素是一个对象 { val, next } ，val存放数据，next指向下一个元素 彼此通过next链式关联 链表的起始元素一般 成为 head

概念

链表存储有序的元素集合
数组对于每个开发来说是非常熟悉的一种数据结构。链表是一种比数组稍微复杂一点的数据结构，掌握起来也比数组稍难一些。
链表是一种与数组类似的线性数据结构，但与数组的元素存储在特定的内存位置或索引中不同，链表的每个元素都是独立的对象，它包含一个指向该列表中下一个对象的指针或链接。
链表的每个元素（我们通常称为节点）包含两项：

  • 存储的数据：数据可以是任何有效的数据类型。
  • 指针：到下一节点的链接

链表的结构可以由很多种，它可以是单链表或双链表，也可以是已排序的或未排序的，环形的或非环形的。如果一个链表是单向的，那么链表中的每个元素没有指向前一个元素的指针。已排序的和未排序的链表较好理解。常见的有：单向链表、双向链表、单向循环链表和双向循环链表。

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

    实现一个链表（普通链表，单向链表）

    ```javascript // 首先是有多个独立的对象 var n1 = { element: ‘’, next: null } var n2 = { element: ‘’, next: null } var n3 = { element: ‘’, next: null } var n4 = { element: ‘’, next: null } var n5 = { element: ‘’, next: null } var n6 = { element: ‘’, next: null } var n7 = { element: ‘’, next: null } var n8 = { element: ‘’, next: null } var n9 = { element: ‘’, next: null }

// 通过next指针将他们链式关联 // 同时向外暴露开始元素（head），和总长度 // 另外还有一些方法 var n1 = { element: ‘’, next: n2 } var n2 = { element: ‘’, next: n4 } var n3 = { element: ‘’, next: n5 } var n4 = { element: ‘’, next: n3 } var n5 = { element: ‘’, next: n7 } var n6 = { element: ‘’, next: n8 } var n7 = { element: ‘’, next: n6 } var n8 = { element: ‘’, next: n9 } var n9 = { element: ‘’, next: null } var head = n1 var length = 9

// ES5 实现链表 function LinkedList() { var Node = function(element) { // {1} this.element = element; this.next = null; }; var length = 0; // {2} var head = null; // {3} this.append = function(element) { var node = new Node(element); if (!head) { head = node } else { var current = head while (current.next) { current = current.next } current.next = node } length += 1 }; this.insert = function(position, element) { if (position > -1 && position < length) { var node = new Node(element) var current = head var previous = null var index = 0 if (position == 0) { node.next = current head = node } else { while (index < position) { previous = current current = current.next index += 1 } previous.next = node node.next = current } length += 1 return true } else { return false } }; this.removeAt = function(position) { if (position > -1 && position < length) { var current = head var previous = null var index = 0 if (position == 0) { head = current.next } else { while (index < position) { previous = current current = current.next index += 1 } previous.next = current.next } length -= 1 return current.element } else { return null } }; this.remove = function(element) { var index = this.indexOf(element) return this.removeAt(index) }; this.indexOf = function(element) { var current = head var index = 0 while (curret.element !== element && index < length) { current = current.next index += 1 } if (current) { return index } else { return -1 } }; this.isEmpty = function() { return length === 0 // return head === null }; this.size = function() { return length }; this.getHead = function() { return head }; this.toString = function() { var current = head var str = current.element.toString() while (current.next) { current = current.next str += current.element.toString() } return str }; this.print = function() { console.log(this.toString()) }; }

```