线性数据结构之链表
一.几种常见的线性数据结构比较
数组的最大优点：支持快速查询
缺点：需要使用resize解决固定容量问题
链表的最大优点：真正的动态，不需要处理固定容量的问题
缺点：丧失了随机访问的能力
二.链表的重要性
a.最简单的动态数据结构
b.能够更加深入的理解引用
c.更加深入的理解递归
d.能够辅助组成其它数据结构
三.链表（Linked List）的组成
数据存在“”节点”（Node）中，节点与节点之间使用next来连接
class Node{
E e;
Node next;
}
四.链表的操作
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中拿到索引也是没有用的。
五.使用链表去实现一个队列
我们在使用链表实现一个栈时，把链表头当做栈顶，由于只有在链表头删除增加元素才是O(1),那么为了让对链表中的最后元素也是O(1)，那么我们做一个改进，我们增加tail指针
此时在两端插入元素都是方便的，但是我们在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();
}
}