链表分为单向链表和双向链表
1.单向链表
链表1.png
链表2.png
上面两张图都描绘了单项链表的结构：链表头+各元素节点。
单向链表中的元素包含一个存储元素本身的节点（data）和指向下一个元素的引用（next）。
2.链表与数组的优缺点比较
链表和数组一样，都是可以用于存储一系列元素的线性数据结构。
数组的缺点：
创建一个数组，需要申请一段连续的内存空间，并且大小固定（大部分编程语言都是固定的），所以当前数组内存不能满足容量需求的情况，需要进行数组的扩容。而且在数组中插入元素的成本很高，需要进行大量的元素位移。
链表的优势：
链表中的元素在内存中不必是连续的内存空间，可以充分利用计算机的内存，实现灵活的内存动态管理；
链表在创建时可以不用确定大小，其大小可以无限的延伸下去；
链表在插入元素和删除元素时，时间复杂度可以达到O(1)，相对数组效率很高。
链表的缺点：
访问链表中的元素时，需要从头开始访问，也就是不能跳过第一个元素直接去访问其他元素。
3.单向链表的封装
class Node{
constructor(element){
this.element = element
//刚开始创建的第一个节点next是为空的,因为并没有下一个节点
this.next = null
}
}
class linkList{
constructor(){
this.head = null
this.length = 0
}
append(element){ //链表中添加节点
const newNode = new Node(element)
if(!this.head){ //没有链表头，就把链表头指向要添加进来的节点
this.head = newNode
}else{ //有了链表头，从链表头开始，看每个节点的next是否有引用
let current = this.head
while(current.next){ //有引用，则一个个往下查找，直至没有引用
current = current.next
}
current.next = newNode //没有引用，就把要添加的元素作为引用
}
this.length++
}
insert(element,position){ //链表中指定位置前插入节点
const newNode = new Node(element)
if(position <0 || position > this.length -1) return null
// if(position === 0){
if(position === 0){
if(!this.head){ //如果插入前，链表中啥也没有
this.head = newNode
}else{
newNode.next = this.head //插入的节点的next指向下一个节点
this.head = newNode //this.head指向插入的节点
}
}else{
let index = 0
let previous = null
let current = this.head
while(index++ < position){
previous = current
current = current.next
}
previous.next = newNode //前一个节点指向插入的节点
newNode.next = current //插入的节点的next指向在position那个位置的节点
}
this.length++
}
get(position){ //查找链表中的某个节点
if(position <0 || position > this.length -1) return null
let index = 0
let current = this.head
while(index++ < position){
current = current.next
}
return current.element
}
indexOf(element){ //返回某个节点的索引值
let current = this.head
let index = 0
while(current){
if(current.element === element){
return index
}
index++
current = current.next
}
return -1 //没有这个节点的时候返回-1
}
removeAt(position){ //根据position删除某个指定节点
if(position < 0|| position > this.length -1) return null
let current = this.head
let previous = null
let index = 0
if(position === 0){ //删除第一个,直接让表头指向第二个节点,第一个节点没有了引用就会被垃圾回收
this.head = current.next
}
while(index++ < position){
previous = current
current = current.next
}
previous.next = current.next
this.length--
return current.element //返回被移除的节点
}
update(element,position){ //修改某节点,返回被修改的节点
//1.先把指定位置的节点删除
const res = this.removeAt(position)
//2.再把新节点插入进去
this.insert(element,position)
return res
}
remove(element){ //根据节点element删除节点
//1.获取要被删除节点的索引值
let index = this.indexOf(element)
if(index === -1) return null
this.removeAt(index)
}
isEmpty(){
return this.length === 0
}
size(){
return this.length
}
}
//测试封装的方法
const linklist = new linkList()
//append(element)
linklist.append('hh')
linklist.append('gg')
linklist.append('kk')
console.log(linklist)
//insert(element,position)
linklist.insert('pp',1)
console.log(linklist)
//get(position)
console.log(linklist.get(2)) //gg
console.log(linklist.get(4)) //null
//indexOf(element)
console.log(linklist.indexOf('kk'))//3
//removeAt(position)
console.log(linklist.removeAt(3))
console.log(linklist)
//update(element,position)
console.log(linklist.update('io',1))
console.log(linklist)
//remove(element)
linklist.remove('gg')
console.log(linklist)
4.双向链表
单向链表内节点的连接是单向的，也就是只能从头遍历到尾部，实现的原理是前一个节点包含有下一个节点的引用。但是，这种单向的连接很明显的缺点就是不能返回到前一个节点，而实际开发中，又经常需要回到上一节点。
所以，双向链表的一大优势就是在元素中额外添加了向前一节点的引用。
当然，这样的操作，会使得在往双向链表中插入或删除元素的时候，要处理四个引用的指向。而且，占用内存空间增加。不过，这些和使用的方便上来讲，不算什么。
双向链表示意图：
双向链表1.png
双向链表2.png
双向链表的特点：
（1）有一个head和tail分别指向链表的头部和尾部；
（2）每个节点包含三个部分：prev（前一节点的引用）、data（当前节点）、next（下一节点的引用）；
（3）链表第一个节点的prev为null；
（4）链表的最后一个节点的next为null。
5.双向链表的封装
class doubleNode extends Node{
constructor(element){
super(element)
this.prev = null
}
}
class doubleLinkList extends linkList{
constructor(){
super()
this.tail = null //双向链表的尾部
}
append(element){
const newNode = new doubleNode(element)
if(!this.head){ //1.没有节点的情况
this.head = newNode
this.tail = newNode
}
//2.有节点的情况
this.tail.next = newNode //尾部节点的next指向新添加的节点
newNode.prev = this.tail //同时新添加的节点的prev指向尾部的节点
this.tail = newNode //最后，将this.tail指向新添加的节点
//3.链表长度+1
this.length++
}
insert(element,position){
if(position < 0 && position > this.length -1) return null
const newNode = new doubleNode(element)
if(position === 0){
if(!this.head){
this.head = newNode
this.tail = newNode
}else{
newNode.next = this.head
this.head.prev = newNode
this.head = newNode
}
}else{
let index = 0
let current = this.head
let previous = null
while(index++ < position){
previous = current
current = current.next
}
//找到position，交换节点
newNode.next = current
current.prev = newNode
previous.next = newNode
newNode.prev = previous
}
this.length++
}
//get():直接继承父类的get()
//indexOf():直接继承父类的indexOf()
removeAt(position){
if(position < 0 || position > this.length - 1) return null
let current = this.head
if(position === 0){ //删除第一个的情况
if(this.length === 1){ //假如链表当前只有一个节点
this.head = null
this.tail = null
}else{ //链表有多个节点
this.head = current.next
current.next.prev = null
current.next = null
}
}else if(position === this.length -1){ //删除最后一个的情况
current = this.tail
this.tail.prev.next = null
this.tail = this.tail.prev
}else{
let index = 0
let previous = null
while(index++ < position){
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
this.length--
return current.element //返回被删除的元素
}
//update(element,position):直接继承父类的update()
//remove(element):直接继承父类的remove()
//isEmpty():直接继承
//size():直接继承
}
const doublelinklist = new doubleLinkList()
//append()
doublelinklist.append('aa')
doublelinklist.append('bb')
doublelinklist.append('cc')
doublelinklist.append('dd')
console.log(doublelinklist)
//insert()
doublelinklist.insert('ee',0)
//get()
console.log(doublelinklist.get(2))
//indexOf()
console.log(doublelinklist.indexOf('dd'))
//removeAt()
console.log(doublelinklist.removeAt(0))
//update()
console.log(doublelinklist.update('ff',1))
//remove(element)
doublelinklist.remove('ff')
console.log(doublelinklist)
