本文共 3616 字，大约阅读时间需要 12 分钟。

                                                                                                                                                  Java自定义链表

一:写在前面

             我们知道在数据结构中,就学习了链表,链式存储结构的线性表也称之为链表，链表的基础知识就不在这里啰嗦啦,毕竟网上的资源太多了.jdk的实现ArrayList(顺序存储)和LikedList(链式存储)

             对于单链表的常见的操作:

                  1:节点的数据查找.

                  2:节点的插入

                  3:节点的删除

             创建新的节点的三种方法：

                    头插法（表头插入）

                    尾插法（表尾插入）

                   一般的插法（按照给定的索引顺序插入节点） 

              重要的有:概念了

                    头节点

                    尾节点

 二:分析实现单链表

    先分析我们需要的数据结构,采用非静态内部类来实现.

    下面是源代码,每一步都注释的比较清楚,一看就明白啦.

public class LinkList
   
     {//定义一个内部类Node，Node就表示链表的节点private class Node{//表示链表的数据域private T data;//表示链表的指针域private Node next;//定义一个空的构造器public Node(){};//初始化链表的各个属性public Node(T data,Node next){this.data=data;this.next=next;}}//保存链表的头结点private Node header;//保存链表的尾节点private Node tail;//保存链表中的节点的数目private int size;//创建一个空链表public LinkList(){//由于是空链表,头结点和尾节点都为空header=null;tail=null;size=0;}//以指定的元素创建一个链表,这个链表就只有一个元素的public LinkList(T element){header=new Node(element,null);//只有一个节点,头尾相同tail=header;size++;}//返回链表的长度public int length(){return size;}//根据索引index来获取指定位置的节点,索引从0开始public Node getNodeByIndex(int index){    if(index<0||index>size-1){    throw new IndexOutOfBoundsException("链表索引越界啦!");    }else{    //单链表从header节点    Node current=header;    for(int i=0;i
    
     size){throw new IndexOutOfBoundsException("链表的索引越界!");}//如果是空链表if(header==null){add(element);}else{//当index=0时,就在链表的头结点插入if(index==0){addAtHeader(element);}else{//获取插入节点的前一个节点Node prev=getNodeByIndex(index-1);//让prev的next指向新增的节点,让新节点的next引用原来prev的下一个节点-就是在要在当前插入的节点.prev.next=new Node(element,prev.next);size++;} }}//采用尾插法为链表添加新节点public void add(T element){//如果该链表是空链表if(header==null){header=new Node(element,null);//只有一个节点tail=header;}else{//创建新的节点Node newNode=new Node(element,null);//让尾节点的next指向新的节点tail.next=newNode;//让新增的节点作为新的尾节点tail=newNode;}size++;}//采用头插法为链表添加新的节点public void addAtHeader(T element){//创建新的节点,让新的节点的next指向原来的header//让新增的节点作为新的headerheader=new Node(element,header);//如果是空链表if(tail==null){tail=header;}size++;}//删除链表中指定索引处的元素public T delete(int index){if(index<0 || index>size-1){throw new IndexOutOfBoundsException("线性表索引越界!");}//要删除的元素对应的节点Node del=null;//如果被删除的是header节点if(index==0){del=header;//让头结点的下一个节点作为头结点header=header.next;}else{//获取删除点前的一个节点Node prev=getNodeByIndex(index-1);//获取将要被删除的节点del=prev.next;//让被删除节点的next指向被删除节点的下一个节点prev.next=del.next;//释放被删除节点的引用del.next=null;}size--;return del.data;}   //删除链表的最后一个元素   public T remove(){       return delete(size-1);   }   //返回链表的尾节点的数据   public T elementLast(){      if(empty()){       return null;      }else{       return tail.data;      }   }   //返回链表的第一个节点的数据   public T elementFirst(){      if(empty()){       return null;      }else{       return header.data;      }   }   //判断链表是否为空   public boolean empty(){   return size==0;   }   //清空链表   public void clear(){   header=null;   tail=null;   size=0;   }   //返回   public String toString(){   //如果链表是空的   if(empty()){   return "[]";   }else{   StringBuilder sbBuilder=new StringBuilder("[");   for(Node current=header;current!=null;current=current.next){   sbBuilder.append(current.data.toString()+",");      }   int len=sbBuilder.length();   return sbBuilder.delete(len-1, len).append("]").toString();   }      }   public static void main(String[] args) {      LinkList
     
       list=new LinkList
      
       ();      list.insert("aaaa", 0);      list.add("bbbb");      list.add("cccc");      list.add("dddd");      //list.remove();      //list.clear();      //list.delete(2);      System.out.println(list.elementLast());      System.out.println(list.elementFirst());      System.out.println(list.empty());      System.out.println(list.length());      System.out.println(list);}}  
      
     
    
   

    运行结果如下:

    至于循环链表就是无头无尾.首尾相顾,从一端开始就可以回到起点的.tail.next=header;

    如果说,单链表是100米或200米跑道.那木循环链表就是400米跑道嘛.大概就是这个意思.