JS中可以动态的向数组中添加删除元素，所以不需要链表结构。
链表特点：
- 添加、删除元素很快，不需要进行移动。
- 单链表：每个元素都要保存一个指针，指向下一个元素。
- 双链表：每个元素既要保存指向下一个元素的指针，还要保存指向上一个元素的指针。
- 循环链表：最后一个元素中保存指向第一个元素的指针。
1. 链表与数组区别：
1.数组：事先定义固定的长度，不能动态增减，会导致内存浪费。
链表：可以动态分配内存，动态增减，不会造成内存浪费，方便得插入、删除。
2.数组：顺序存储
链表：随机存储
3.数组：从栈中分配空间，方便快速，自由度小。
链表：从堆中分配空间，自由度大，申请管理麻烦。
4.数组：有越界问题。
链表：没有越界问题。
2. 什么时候选择顺序表？什么时候选择链表作为线性表得存储结构？
a.空间上：顺序表静态分配内存，线性表动态分配内存，如果长度变化不大，可以事先确定的用顺序表，长度变化较大，事先无法确定的用链表。
b.时间上：如果在线性表上的操作主要为查找，很少删除插入则用顺序表；反之，则用链表。
3. 如何使用链表头？
Paste_Image.png
头节点的作用：
1.在插入和删除结点时，需要修改前面结点的指针，如果没有头节点，则对开始结点前的插入删除比较麻烦。
2.头指针指向头结点，保证空表与飞空表的处理是一样的。
4. 如何实现单链表的插入、删除？
插入：在ai之前插入一个元素x
1.找到ai-1的存储位置P；
2.生成一个数据域为x的新节点；
3.将P的指针域指向新节点
4.新节点的指针域指向ai
主要的操作耗费在查找P位置，所以时间复杂度为O(n)
删除：删除ai
1.找到ai-1的存储位置P；
2.将P指针域指向ai+1;
3.释放ai结点空间。
function Node(element) {//结点定义
this.element=element;
this.next=null;
}
function LList() { //链表方法
this.head=new Node("head");
this.find=find;
this.insert=insert;
this.remove=remove;
this.findPrevious=findPrevious;
this.display=display;
}
function find(item) { //找到元素item
var currNode=this.head;
while(currNode.element!=item){
currNode=currNode.next;
}
return currNode;
}
function insert(newElement,item) {//向item后面插入newElement
var newNode=new Node(newElement);
var current=this.find(item);
newNode.next=current.next;
current.next=newNode;
}
function findPrevious(item) {//找到item前面的结点
var currNode=this.head;
while ((currNode.next!=null)&&(currNode.next.element!=item)){
currNode=currNode.next;
}
return currNode;
}
function remove(item) { //删除元素值为Item的结点
var prevNode=this.findPrevious(item);
if(prevNode.next!=null) {
prevNode.next = prevNode.next.next;
}
}
function display() { //输出链表
var currNode=this.head;
while (currNode.next!=null){
console.log(currNode);
currNode=currNode.next;
}
console.log(currNode);
}
var cities=new LList();
cities.insert("A","head");
cities.insert("C","A");
cities.remove("C");
cities.display();
