下面整理数据结构中的链表（主要是用java写的代码）

一、什么是链表

　　1、首先理解链表的节点概念

　　个人理解：链表节点，包含一个数据和一个内存地址，内存地址指向下一个同样类型的链表节点，这样说有种绕起来了像递归的感觉（不过链表和递归还是有点类似的：自己指向自己，不断积累），具体可以看下图：

 

ok,上图也差不多表现了链表节点的一个抽象结构了，而具体的代码表示也很简单：数据+引用即可:下面以int为说明例子

public class LinkSingleIntNode {    public int data = 0;    public LinkSingleIntNode next = null;    public LinkSingleIntNode(){            }    public LinkSingleIntNode(int data){        this.data = data;    }}

 

2、链表

　　上面的图也说明了链表的具体结构了，这里不累赘；其实链表就是各个节点连接起来的结果集，通常会存储一个手节点的内存地址作为链表的具体引用，所以，链表的构造可以参考一下代码：

public class LinkSingleInt {    public static void main(String[] args) throws SecurityException, IllegalArgumentException, InstantiationException, IllegalAccessException, NoSuchMethodException, InvocationTargetException {        // TODO Auto-generated method stub        //随机生成十个数进行测试        LinkSingleInt link = new LinkSingleInt();        LinkSingleIntNode node = null;        int length = 10;        for(int i = 0;i
     
       list = link.findAll();        int test;    }    //链表长度    public int size = 0;    public LinkSingleIntNode linkHead = null;    public LinkSingleIntNode linkTail = null;        //构造函数    public LinkSingleInt(){        linkHead = new LinkSingleIntNode();        linkTail = linkHead;    }    //增加节点    public  boolean addNode(LinkSingleIntNode node){        boolean rtn = false;        linkTail.next = node;        linkTail = node;        size++;        rtn = true;        return rtn;    }}
     

这个是简单版的链表实现，通常来说，为了提高每个方法操作链表的平均运行时间（即用内存换区时间），会将一些必要数据存储在链表类中：例如本例中的size变量存储了链表的长度。具体的设计其实还需要参考业务需求。

3、链表的删除操作示意图

 

具体实现方式看代码：

//删除节点（这里是针对双向链表的来实现）	public  boolean deleteNode(LinkSingleIntNode node){		//判断是否为null		if(node==null){			//可以在检测到null的时候抛出异常			throw new RuntimeException("失败，node参数为null");		}		if(node.equals(linkHead)){			//首节点，直接删除			linkHead = node.next;			node.next=null;			size--;//改变链表长度			return true;		}		//判断是否是最后一个节点，如果是，相应的改变tail的值（这里我的实现类存储了tail的值，所以要改变尾端的值）		if(node.equals(linkTail)){			linkTail = node.prev;			node = null;			size--;//改变链表长度			return true;		}		//其他情形直接删除		LinkSingleIntNode nodePrev = node.prev;//同理，存储删除节点的上一个节点		nodePrev.next = node.next;		node=null;		size--;		return true;	}

　4、链表的增加操作

　　链表的增加操作从直观上来说也挺简单的，和删除操作类似，具体就不上图啦，看代码吧

//增加节点（直接链表末增加，默认）	public  boolean addNode(LinkSingleIntNode node){		boolean rtn = false;		linkTail.next = node;		linkTail = node;		size++;		rtn = true;		return rtn;	}	//在中间某个元素之后增加	public boolean addNodeAfterAnyNode(LinkSingleIntNode nodeAdd,LinkSingleIntNode nodeAny){		//先存储标记节点的后一个节点以及前一个节点		if(nodeAny==null){			throw new RuntimeException("错误，nodeAdd为null");		}		if(nodeAny.next==null){			return addNode(nodeAdd);//如果是最后一个元素直接调用默认的add方法		}		LinkSingleIntNode nodeBetw = nodeAny.next;		nodeAny.next = nodeAdd;		nodeAdd.next = nodeBetw;		return true;	}

　　

下面贴上完整版的链表类（扩展其他方法，代码太长不想看直接跳过啦，毕竟，这种没什么技术含量的代码贴上来只是为了博客文章的完整性 而已，其实对理解链表并没有什么卵用处）

public class LinkSingleInt {    public static void main(String[] args) throws SecurityException, IllegalArgumentException, InstantiationException, IllegalAccessException, NoSuchMethodException, InvocationTargetException {        // TODO Auto-generated method stub        //随机生成十个数进行测试        LinkSingleInt link = new LinkSingleInt();        LinkSingleIntNode node = null;        int length = 10;        for(int i = 0;i
      
        list = link.findAll();        int test;    }    //链表长度    public int size = 0;    public LinkSingleIntNode linkHead = null;    public LinkSingleIntNode linkTail = null;        //构造函数    public LinkSingleInt(){        linkHead = new LinkSingleIntNode();        linkTail = linkHead;    }    //增加节点    public  boolean addNode(LinkSingleIntNode node){        boolean rtn = false;        linkTail.next = node;        linkTail = node;        size++;        rtn = true;        return rtn;    }    //删除节点（待定）    public  boolean deleteNode(LinkSingleIntNode node){        boolean rtn = false;        LinkSingleIntNode nodeBetw = linkHead.next;        LinkSingleIntNode nodePrev = linkHead;        while(nodeBetw!=null){            if(nodeBetw.equals(node)){                //判断是否是最后一个节点，如果是，相应的改变tail的值                if(nodeBetw.equals(linkTail)){                    linkTail = nodePrev;                }else{                    nodeBetw = nodeBetw.next;                }                size--;                rtn =  true;                break;            }else{                nodePrev = nodeBetw;                nodeBetw = nodeBetw.next;            }        }                return rtn;    }    //判断某个节点是否在链表中    public  boolean judgeNode(LinkSingleIntNode node){        boolean rtn = false;        LinkSingleIntNode nodeJudge = linkHead;        while(nodeJudge!=null){            if(nodeJudge.equals(linkHead.next)){                rtn =  true;                break;            }else{                linkHead = linkHead.next;            }        }        return rtn;    }    //遍历    public  ArrayList
       
         findAll(){        ArrayList
        
          rtn = new ArrayList
         
          ();        LinkSingleIntNode nodeJudge = linkHead.next;        while(nodeJudge!=null){            rtn.add(nodeJudge.data);            nodeJudge = nodeJudge.next;        }        return rtn;            }}
         
        
       
      

二、链表的种类

　　1、单向链表：字面就可以理解：链表的操作只能沿一个方向进行。不多解释

　　2、双向量表。可前可后遍历，其实就是在链表节点中新增多一个指针变量，将该指针指向上一个元素，可以方便链表操作，但是空间存储变大，典型的空间换时间类型扩展。还是上个丑图

 

 好吧，可能你会说图有点丑（别在意这些细节好吧），双向指针只是多了个回指引用，指向了上一个对象。

恩，还是废话不多说，上坨代码直接点吧

//好吧，我承认这个类名取得有点歧义，其实double不是double类型，他表示双个的意思（英语不好怪我咯）public class LinkDoubleIntNode {		public int data = 0;	public LinkDoubleIntNode next = null;	public LinkDoubleIntNode prev = null;//双向链表和单项链表并没有什么卵本质区别，不过多了一个指向上一个节点的引用罢了	public LinkDoubleIntNode(){			}	public LinkDoubleIntNode(int data){		this.data = data;	}}

3、还有种链表，叫做环装链表，其实就是最后节点的引用指针指向首位而已，不过这种链表，感觉好像挺少用的，毕竟环状和非环装也没什么本质区别。具体代代码什么的就不上了，上个小丑图吧　

 

　

4、好像貌似还有什么三指向的链表，omg,太难了，其实在我看来过于复杂的链表结构一般不会常用（可能这个时候已经不叫链表了，已经是类似于树或者图了，好吧，话有点多了）

 

三、链表特点

　　1、链表VS数组：链表其实是一种非常基本的数据结构，它具有的特点是：插入删除快，而且，他的长度是可变的，但是要找某个元素的时候就必须遍历整个链表了。数组其实是反过来，长度定死，找数据块， 额，好像插数据和删数据也挺快的（看从哪个角度看待吧，如果说每次数据改变都要调整数组使得它紧凑的话其实是很低效的）

　　2、作用范围。有上面的链表特点，我们估计也能猜到链表一般会用到哪了吧：插入修改删除的操作远远大于查询操作的时候考虑该使用数据结构。