链表的使用

链表主要分为单向链表、双向链表、循环链表
双向链表、循环链表都可以认为是单向链表的扩展，单向链表最基础，笔者的介绍也将基于单向列表
单向链表是一个在物理存储上不相邻的序列（与数组不同），它由结点组成，每个结点分为指针域和值域，值域发挥与数组元素类似的存储数值的作用，而指针域存储下一个结点的地址，结点与结点之间通过指针相连。
下图是单向链表的逻辑结构

可见只要得到第一个元素（通常称为头结点）即可通过指针获取整个链表的元素。
定义一个结点类
public class Node {
         //值域，定义为Object，能够存储任意类型的值
Object obj;
//指针域
         Node next;
public  Node(Object obj){
this.obj=obj;
}
}
定义一个链表类
public class LinkedList{
       //指向第一个元素的头结点
      Node head=null;
       //指向最后一个元素的尾结点
      Node last=head;
}
以下代码均为LinkedList类中的方法
添加元素
public void add(Object obj){
Node node=new Node(obj);
                 //将每个结点添加到尾结点后面，如果链表尚未添加任何元素
                    //则将要添加的结点赋给头结点，之后让last指向最后一个结点
if(head!=null){
last.next=node;
}else{
head=node;
}
last=node;


}
获取链表的元素个数
public int size(){
int count=0;
Node node=head;
while(node!=null){
count++;
node=node.next;
}

return count;
}
获取指定位置的元素
public Node get(int index){
int count=0;
Node node=head;
while(node!=null){
if(index==count){
return node;
}else{
node=node.next;
count++;
}
}
return null;
}
给链表排序的方法
public void sort(int sequence){
Node p,q,r;
//sequence判断按升序还是降序排列，此处为升序
if(sequence==0){
for(int i=size();i>1;i--){

for(int j=0;j<i-1;j++){
if(Integer.parseInt(get(j).obj.toString())>Integer.parseInt(get(j+1).obj.toString())){
//如果相邻的两个结点，前一个结点（赋给q）的值大于后一个结点（赋给r），则将他们的结点交换
q=get(j);r=get(j+1);
//让q的指针指向r的下一个元素
q.next=r.next;
//让r的指针指向q
r.next=q;
//让指向q的元素指向r
if(j!=0){
get(j-1).next=r;
}
//如果q为第一个元素，则交换后的r为第一个元素，将其赋给头结点
if(j==0){
head=r;
}
if(q.next==null){
last=q;
           }
}
}
}
}
//此方法仅考虑了按升序排列的情况,如果按降序排列，仅需将判断语句if()中的>改为<
}
让链表转置的方法
public void reverse(){
Node node_temp;
//让后一个结点的指针指向前一个结点
for(int i=size()-2;i>=0;i--){
get(i+1).next=get(i);
}
//原本的头结点此时为最后一个元素，即尾结点
head.next=null;
node_temp=head;
//原本的尾结点此时为头结点
head=last;
last=node_temp;
}
}
判断链表是否有环的方法
/**如果链表中的尾结点的指针并不为空，而是指向某个结点（包括它本身），则认为此链表有环*/
public static boolean isCircle(Node head){
Node n1,n2;
n1=n2=head;
/**两个元素n1、n2从头结点开始读取整个链表
  * 一个按顺序读，另一个间隔一个元素读，如果链表有环
  * 则一定会有n1=n2的情况
  */
while(n1!=null&&n2!=null){
try{
n1=n1.next;
n2=n2.next.next;
if(n1.equals(n2)){
return true;
}
}catch(NullPointerException e){
//如果n1 n2某次读到了空值，则该链表一定无环
return false;
}
}
return false;

}
以上代码存在一定缺陷
譬如调用get(int index)须每次从头结点开始读取，在排序方法中多次使用get（int index）方法可能造成时间的浪费。