1.什么是单向链表结构？

1.1.简介

链表和数组一样, 可以用于存储一系列的元素, 但是链表和数组的实现机制完全不同，链表中的元素在内存不是连续的空间，链表的每个元素由一个存储元素本身（数据）的节点和一个指向下一个元素的引用（指针或者链接）组成。
通俗来说链表类似于火车: 有一个火车头, 火车头会连接一个节点, 节点上有乘客（数据）, 并且这个节点会（通过指针）连接下一个节点, 以此类推...

• 链表的火车结构：
  

  
  



• 给火车加上数据结构后的结构：
  

  
  



• 链表的数据结构：
  

  
  

1.2.链表和数组的对比

数组存在的缺点：

• 数组的创建需要申请一段连续并且大小固定的内存空间，当数组不能满足容量的需求是，需要扩容（申请一个更大的数组，将原数组复制过去，反复创建数组会降低性能）


• 在数组开头或者中间位置插入数据的成本很高，需要进行大量元素的位移

链表的优点：

• 链表中的元素在内存中不必是连续的空间,所有可以充分利用计算机的内存，实现灵活的内存动态管理


• 链表不不必在创建时确定大小，并且大小可以无限的延伸下去


• 链表在插入和删除数据时，因为不需要进行大量的位移，相对数据效率高很多

链表的缺点：

• 因为其指针访问机制，当需要访问任何一个位置元素都需要从头开始访问，当链表数据量过大时性能低


• 无法像数组那样通过下标直接访问元素，访问机制都是从头开始查找

1.3.链表常见操作

• append(element)：向列表尾部添加一个新的项


• insert(position, element)：向列表的特定位置插入一个新的项。


• remove(element)：从列表中移除一项。


• indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。


• removeAt(position)：从列表的特定位置移除一项。


• isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。


• size()：返回链表包含的元素个数。与数组的length属性类似。


• toString()：由于列表项使用了Node类，就需要重写继承自Javascript对象默认的toString方法，让其只输出元素的值。

3.封装单向链表类

3.1.创建单向链表类

// 封装单向链表类
function LinkedList() {
// 内部的类：节点类
function Node(data) {
this.data = data
this.next = null // 指向下一节点的引用默认为null
}
// 属性
this.head = null // 链表头部
this.length = 0 // 记录链表的长度
}


3.2.append(element)

代码实现

// 1.append 追加方法
LinkedList.prototype.append = function (data) {
// 1.创建新的节点
var newNode = new Node(data)
// 2.判断是否添加的是第一个节点
if (this.length === 0) {
// 2.1是第一个节点
this.head = newNode
} else {
// 2.2不是第一个节点
// 找到最后一个节点
// 判断current是否为空，为空即为链表最后一个节点，停止循环
var current = this.head // 此时this.head指向最后一个节点
while (current.next) {
current = current.next
}
// 让最后节点的next指向新添加的节点
current.next = newNode
}
// 3.length+1
this.length += 1
}


过程讲解

情况1:当添加的节点是第一个节点，直接在head后插入

情况2：当链表中已经有节点了，需要向最后的next中添加节点

• 添加一个变量current让其指向head，循环判断其next属性是否为空？
  

  
  



• 当current.next为空时current就是最后一个节点，此时让current.next指向添加的节点
  

  
  

代码测试

var list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)
console.log(list)


3.3.toString()

// 2.toString
LinkedList.prototype.toString = function () {
// 1.定义变量
var current = this.head
var listString = ‘‘
// 2.循环获取一个个的节点
while (current) {
listString += current.data + ‘ ‘
current = current.next
}
return listString
}


代码测试

var list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)
console.log(list.toString())


3.4.insert(positon,element)

代码实现

// 3.insert 插入 参数：传入位置和数据
LinkedList.prototype.insert = function (position, data) {
// 1.对 position 进行越界判断 不能为负数且不能超过链表长度
if (position <0 || position > this.length) return fasle
// 2.根据data创建newNode
var newNode = new Node(data)
// 3.判断插入的位置是否是第一个
if (position === 0) {
newNode.next = this.head // 先让newNode指向原第一个
this.head = newNode // 再让this.head指向插入的
} else {
var index = 0
var current = this.head
var previous = null
// 当index小于position就一直往后找
while (index++ previous = current
current = current.next
}
newNode.next = current
previous.next = newNode
}
// 4.链表长度增加1
this.length += 1
return true
}


过程解释

情况1：position=0

• 这个时候表示新添加的节点是头，需要将原来的头节点，作为新节点的next


• 另外这个时候的head应该指向新节点
  

情况2：positon>0

我们需要定义两个变量previous和current分别指向需要插入位置的前一个节点和后一个节点

代码测试

var list = new LinkedList()
list.append(‘a‘)
list.append(‘b‘)
list.append(‘c‘)
list.insert(0, ‘我是头部插入的‘)
list.insert(2, ‘我是插入第二个的‘)
list.insert(5, ‘我是末尾插入的‘)