线性数据结构-链表

链表：线性数据结构（一维数组结构）
线性的数据结构强调存储和顺序

单向链表（也称为单链表）是一种简单的数据结构，其中每个节点包含两个部分：一个是数据元素（或称为值），另一个是指向下一个节点的指针。最后一个节点则指向一个空值来表示链表的结束。

function node(data, nextPtr){
	this.data = data
	this.next = nextPtr
}

链表的添加
每一个节点都是认为自己是根节点

node1 -> node3 -> node5 -> node2
在node3 之后插入 newNode
newNode.next = node3.next
node3.next = newNode
node1 -> node3 -> newNode -> node5 -> node2

链表的删除

node1 -> node3 -> newNode -> node5 -> node2

移除newNode节点
node3 .next = newNode .next
node1 -> node3 -> node5 -> node2
newNode.next 还存在依然指向node5

传递一个链表必须传递链表的根节点

链表的特点
1、空间不是连续的
2、每存放一个值，都要多开销一个引用空间

链表的优点：
1、只要内存足够大，就能存的下，不用担心内存碎片问题。
2、链表的添加和删除非常容易

链表的缺点：
1、查询速度慢，（指的查询某个位置）
2、链表的每一个节点都需要创建一个指向next的引用，浪费一些空间
双链表所有的东西都可以用单链表表示，双链表还存在来个引用空间，极其浪费时间