一.几种常见的线性数据结构比较
数组的最大优点：支持快速查询
缺点：需要使用resize解决固定容量问题
链表的最大优点：真正的动态，不需要处理固定容量问题
缺点：随机接入能力丧失
二.链表的重要性
a .最简单的动态数据结构
b .能更深入地理解引用
c .更深入地理解递归
d .其他数据结构可以辅助配置
三.链表（Linked List）的组成
数据存在于“”节点中，节点之间通过next进行连接
class Node{ (
e；
节点下一个；
}
四.链表的操作
a .在链表头添加元素
在、
在数组中有size咋尾部，我们在数组尾部添加元素很容易，在链表头部添加元素很容易，因为我们在链表中有head引用
b .在链表中间添加元素
在索引(链表中实际上没有索引，为了图像描述而与数组一样被称为索引)为2的地方添加要素666
重要信息：找到要添加节点之前的节点
特殊处理：插入在链表的头部，没有前一个节点
为了解决这种特别的处理，我们为链表设置虚拟头节点。 此虚拟头节点对用户来说是屏蔽的，但设计为易于使用。)
c .删除链表元素
删除索引为2的元素
为便于java垃圾回收，请将要删除的节点的next设置为null
四.链表的时间复杂分析
a .添加操作o(n )
addlast(e ) o ) n )是
addfirst(e ) o )1) )。
add(index，e ) o ) n/2 )=o(n ) ) ) ) ) ) ) ) ) ) )。
b .删除操作o(n ) )
removelast(e ) o ) n )是
removefirst(e ) o )1) )。
remove(index，e ) o ) n/2 )=o(n ) ) ) ) ) ) ) ) ) ) ) )。
c .修改操作o(n )
set(index，e ) o ) ) n )
d .搜索操作o(n ) )。
get(index ) o ) n )是
contains(e ) o ) n )
find(e ) o ) n )是
对于 链表来说，find其实是没有用的。 在数组中是返回数组的下标，但是用find得到索引也没有用。
五.使用链表去实现一个队列
我们使用链表实现堆栈时，把链表的头放在堆栈的最上面。 添加tail指针，使链表的最后一个元素也成为o )1)，因为只有在链表的开头删除了附加元素才是o(1)
虽然在两端插入元素非常有用，但在tail中删除元素时，必须找到要删除的节点之前的节点。 我们
无法使用O(1)的复杂度找到tail 的前一个节点的，这就涉及到双向链表了。从tail 中删除元素不易
我们这里的链表，方便对队列的操作，我们这里就不加入虚拟头节点，我们当然可以加入dummyHead的思路去实现。
代码实现：
public class LinkedList<E> {
// Node为private还是public，根据不同的设计来定义
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
@Override
public String toString(){
return e.toString();
}
}
private Node dummyHead;
private int size;
//这里还可以设计成其它的构造函数，比如传入一个数组等等
public LinkedList(){
//head = null;
dummyHead = new Node(null,null);
size = 0;
}
//获取链表中的元数个数
public int getSize(){
return size;
}
//返回链表是否为空
public boolean isEmpty(){
return size == 0;
}
// 在链表头添加元素e，复用add方法
public void addFirst(E e){
add(0,e);
}
// 在链表的index(0-based) 位置添加新的元素e，在链表中不是一个常用的操作，用来练习: )
public void add(int index,E e){
if(index < 0 || index >size)
// 注意这里能取到size，可以在最后插入元素
throw new IllegalArgumentException("add failed. Illegal index");
Node prev = dummyHead;
//这里是从dummyHead 的开始的
for(int i=0 ; i<index; i++){
prev = prev.next;
}
prev.next = new Node(e, prev.next);
size++;
}
// 在链表的末尾添加新的元素e，复用add方法
public void addLast(E e)
{
add(size, e);
}
//获得链表的第index(0-based)个位置的元素，在链表中不是一个常用的操作，用来练习: )
public E get(int index){
if(index < 0 || index >= size)
// 注意这里能取到size，可以在最后插入元素
throw new IllegalArgumentException("get failed. Illegal index");
Node cur = dummyHead.next;
for(int i=0; i<index; i++)
cur = cur.next;
return cur.e;
}
//获得链表的第一个元素
public E getFirst(){
return get(0);
}
public E getLast(){
return get(size-1);
}
// 修改链表的第index(0-based)个位置的元素e，在链表中不是一个常用的操作，用来练习: )
public void set(int index,E e){
if(index < 0 || index >= size)
// 注意这里能取到size，可以在最后插入元素
throw new IllegalArgumentException("set failed. Illegal index");
Node cur = dummyHead.next;
for(int i=0; i<index; i++)
cur = cur.next;
cur.e = e;
}
// 查找链表中是否存在元素e
public boolean contains(E e){
Node cur = dummyHead.next;
while(cur !=null){
if(cur.e.equals(e))
return true;
cur = cur.next;
}
return false;
}
// 删除链表中的元素,返回删除的元素
public E remove(int index){
if(index < 0 || index >= size)
// 注意这里能取到size，可以在最后插入元素
throw new IllegalArgumentException("remove failed. Illegal index");
// 找到待删除的前一个节点
Node prev = dummyHead;
for(int i=0; i<index; i++)
prev=prev.next;
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size --;
return retNode.e;
}
// 从链表中删除第一个元素,返回删除的元素
public E removeFirst(){
return remove(0);
}
//从链表中删除最后一个元素，返回删除的元素
public E removeLast(){
return remove(size-1);
}
@Override
public String toString(){
StringBuffer res = new StringBuffer();
res.append("[size:"+getSize()+"] ");
for(Node cur = dummyHead.next;cur !=null;cur=cur.next)
res.append(cur+"->");
res.append("Null");
return res.toString();
}
}