链表总结

链表总结：
   链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
  1.链表的组成：
       链表由一系列的节点组成，节点可以再运行时动态生成。而每个节点又包括两部分：一是存储数据元素的数据域，
     另外一个是存储下一个节点地址的指针域。相比较于线性表顺序结构，链表比较方便插入和删除操作。

  2.链表的分类：
     a.单向链表：
       单向链表的每一个节点又存储数据元素的数据域和指向下一个节点的指针域组成。(如下面的代码)
*/
public class LinkList {
//声明一个LinkNode根节点对象
    private LinkNode root;
/**
* 主函数
* @param args
*/
public static void main(String[] args) {
LinkList list=new LinkList();
//创建一个链表
LinkNode root=list.creatLink();
//遍历链表
list.printLinKList(list.root);
}
/**
* 手工创建单向链表
* @return  返回一个LinkNode类型的root根节点
*/
public LinkNode creatLink(){
String s="根节点";
root=new LinkNode(s);
LinkNode n1=new LinkNode("一节点");
LinkNode n2=new LinkNode("二节点");
LinkNode n3=new LinkNode("三节点");
LinkNode n4=new LinkNode("四节点");
root.setNext(n1);
        n1.setNext(n2);
        n2.setNext(n3);
        n3.setNext(n4);


        return root;
}
public void printLinKList(LinkNode root){

if(null!=root){
Object data=root.getobj();

System.out.println(data);
LinkNode temp=root.getnext();
printLinKList(temp);
}
}
}（这只是一个链表类，节点类就不写出来了）
     b.双向链表：
      双向链表其实是单链表的改进
      当我们队单链表进行操作时，有时你要对某一个节点前面的一个节点进行操作时，又必须从表头开始查找。
      但如果你使用了双向链表，你就可以直接对某个节点前的节点进行操作，就不必要从头开始查找，大大提高了
       查找的效率。（下面是一个双向链表的代码）
/**
* 双向链表节点类
* @author
*/
class DoubleNode{
private Object obj;
private DoubleNode child;
private DoubleNode parent;
/**
* 构造方法
*/
public DoubleNode(Object obj){
this.obj=obj;
}
/**
* 设置当前节点
*/
public void setObj(Object obj){
this.obj=obj;
}
/**
* 得到当前节点
*/
public Object getObj(){
return obj;
}
/**
* 设置父节点
*/
public void setParent(DoubleNode parent){
this.parent=parent;
}
/**
* 得到父节点
*/
public DoubleNode getParent(){
return parent;
}
/**
* 设置子节点
*/
public void setChild(DoubleNode child){
this.child=child;
}
/**
* 得到子节点
*/
public DoubleNode getChild(){
return child;
}
}
/**
* 向链表中增加元素
*/
public void add(Object obj){
//创建新节点
DoubleNode node=new DoubleNode(obj);
if(front==null){ //链表为空
front=node;
last=node;
}else {
last.setChild(node);
node.setParent(last);
last=node;
}
}
/**
* 向链表中插入元素
*/
public void insert(int index,Object obj){
if(index<0||index>this.getlength()){
throw new java.lang.RuntimeException("下标越界！");
}else {
//创建新节点
DoubleNode newnode=new DoubleNode(obj);
//得到当前节点
DoubleNode node=this.getList(index);
if(index==0){
front=newnode;
}else{
//得到当前节点的父节点
DoubleNode pnode=node.getParent();
pnode.setChild(newnode);
newnode.setParent(pnode);
}
newnode.setChild(node);
node.setParent(newnode);
}
}

     c.循环链表：循环链表和单向链表十分相似，只是把单向链表的末尾节点指向头结点，这样就得到了循环链表。