java线性表(三)-------链表

之前我们已经使用顺序存储结构实现了线性表，我们会发现虽然顺序表的查询很快，时间复杂度为O(1),但是增删的 效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢？有，我们可以 使用另外一种存储结构实现线性表，链式存储结构。 链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元 素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成， 结点可以在运行时动态生成。

//定义Ilist interface
public interface Ilist {
    public void clear();
    public boolean isEmpty();
    public int length();
    public Object get(int i) throws Exception;
    public void insert(int i,Object x) throws Exception;
    public int remove(int i) throws Exception;
    public int indexOf(Object x);
    public void dispiay();

}

//定义Node结点类
public class Node {
    public Object data; //存结点值
    public Node next;   //后继结点的引用
    //无参时的构造函数
    public Node() {
        this(null,null);
    }
    //单参时的构造函数
    public Node(Object data) {
        this(data,null);
    }
    //两个参时的构造函数
    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}

import java.util.Scanner;
public class linkList implements Ilist {
   public Node head;//头指针

    public linkList() {
        head=new Node();//初始化头结点
    }
    public linkList(int n,boolean Order)throws Exception {
      this();//初始化头结点
        if (Order)
            create1(n);
        else
            create2(n);

    }

    private void create2(int n) throws Exception {
   //头插法
        Scanner sc=new Scanner(System.in);
        for (int j=0;ji||p==null){
            throw new Exception("第"+i+"个元素不存在");
        }
        return p.data;
    }

    @Override
    //带头结点的单链表上的插入操作

    public void insert(int i, Object x)throws Exception {
        Node p=head;
        int j=-1;
        while (p!=null&&ji-1||p==null)
            throw new Exception("插入位置不合法");
            Node s=new Node(x);
            s.next=p.next;
            p.next=s;


    }
    //删除操作
    @Override
    public int remove(int i) throws Exception {
        Node p = head;
        int j = -1;
        while (p.next!= null && j < i - 1) {//寻思第i个结点的前驱
            p = p.next;
            ++j;
        }
        if (j>i-1||p.next==null)
            throw  new Exception("删除位置不合法");
            p.next=p.next.next;  //修改链指针,使待删除结点从链表中脱离
        return j;
    }
    @Override
    public int indexOf(Object x) {
        Node p=head.next;
        int j=0;
        while (p!=null&&p.data.equals(x)){
            p=p.next;
            ++j;
        }
        if (p!=null)
            return j;
        else
            return -1;
    }

    @Override
    //输出单链表中的所有节点
    public void dispiay() {
        Node node=head.next;//取出头结点
        while (node!=null){
            System.out.println(node.data+"");//输出结点的值
            node=node.next;
        }
        System.out.println(); //换行

    }
}

import java.util.Scanner;
public class EXample1 {
    public static void main(String[] args) throws Exception {
        int n=10;
        linkList L=new linkList();//创建空表
        for (int i=0;i 
测试类结果
 
 
 因为表从0开始所以索引2是3