单链表的基本运用

认识单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
链表中的数据是以节点来表示的，每个节点的构成：data域（数据元素）+next域（下一个结点的存储位置）。
单链表与数组相比的最大差别是：单链表的数据元素存放在内存空间的地址是不连续的，
而数组的数据元素存放的地址在内存空间中是连续的，
这也是为什么根据索引无法像数组那样直接就能查询到数据元素。

基本操作如下

public class LinkList {
    private static final LinkNode NULL = null;
private LinkNode Head = new LinkNode();
//先初始化一个头结点，头结点为空
    LinkList() {
        Init_LinkNode();
}
//内部类节点LinkNode
    class LinkNode {

        int data;

        LinkNode next=null;

        LinkNode(){

        }

        LinkNode(int elem){

            data=elem;
        }
        LinkNode(int elem,LinkNode nextval){

            data=elem;

            next=nextval;
        }

        LinkNode(LinkNode nextval){

            next=nextval;
        }
    }
    
    //1.单链表的初始化
    public void Init_LinkNode() {
        LinkNode head = null;
    }
//2.    判断表是否为空
 public boolean isEmpty() {
//通过判断头结点的下一结点地址是否为空，即可判断单链表是否为空
        if(this.Head.next == null) {  
         return true; 
        }
        return false;
    }
    //3.返回单链表的长度
    public int Length_LinkList() {
        int j=0;
        LinkNode tmp=Head; 
//head节点不能动，需要一个tmp辅助遍历
        while(tmp != null) {
            j++;
            tmp=tmp.next;
        }
        return j;
    }

        //4.返回第i个元素
        public LinkNode Get_LinkList(int i) {
            LinkNode p = Head;
            int a = 0;
            while (p.next != null && a < i) {
                p = p.next;
                a++;
            }
            if (a == i) {
                return p;
            } else {
                return null;
            }
        }

       
//5.删除第i个元素
        public int Delete_LinkList(int i) {
                LinkNode p;
                LinkNode s;
            p=Get_LinkList(i-1);
            if(p==null){
                System.out.println("第i-1个结点不存在");
                return -1;
            }else if (p.next==null){
                System.out.println("第i个结点不存在");
                return 0;
            }else{
                s=p.next;
                p.next=s.next;
                return 1;
            }
        }
 //6.在第i个位置插入元素
        public int  Insert_LinkList(int i,int x) {
        LinkNode p,s;
        p=Get_LinkList(i-1);
            if(p==null){
                System.out.println("参数i错误");
                return 0;
            }else {
                s=new LinkNode();
                s.data=x;
                s.next=p.next;
                p.next=s;
                return 1;
            }
}

        //7.把表中的元素打印出来
            public void display(){
                LinkNode tmp=Head;
                while (tmp!=null) {
                    System.out.println(tmp.data+"  ");
                    tmp=tmp.next;
                }
                System.out.println();
            }

}

顺序表与单链表的比较

顺序表的优点：

其存储结构为随机存取结构，逻辑关系可直接用数组元素下标表示。

顺序表的缺点：

①线性表的长度不确定，难以事先确定数组长度。
②存储空间必须是连续的，易造成存储空间的“碎片”现象。③插入和删除操作需要移动大量元素。

单链表的优点：

①元素的存储单元是任意的，可连续也可不连续。②不需要限定长度。

单链表的缺点

：①其查找时间复杂度为O(n)。②存放元素时需要另外开辟一个指针域的空间。