Java实现顺序表、链表结构

Java实现顺序表、链表结构
顺序表
 
定义:
 
用一段物理地址连续的存储单元依次存储数据元素的线性结构(逻辑上连续,物理上也连续)
 
(1)静态顺序表:使用定长数组存储。
 
(2)动态顺序表:使用动态开辟的数组存储
 
【注意】静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用,所以相比之下,动态数组更为灵活,可根据需要动态分配空间大小
 
实现方法:
 
增、删、改、查
 
增加操作:从头部插入、从尾部插入、在任意索引位置处插入
 
删除操作:根据索引删除元素、根据元素值删除第一个出现的该元素、根据元素值删除所有该值元素 
 
查找操作:根据元素值查找是否存在某元素、根据索引下标返回该处元素值、根据元素值返回索引下标 
 
修改操作:根据索引下标修改该处元素 
 
代码实现:
 
public class MyArray {
 
    private int[]data;
 
    private int size;
 
//    无参构造
 
    public MyArray(){
 
        this.data=new int[5];
 
    }
 
//    有参构造
 
    public MyArray(int n){
 
        this.data=new int[n];
 
    }
 
//    grow方法用于扩充内存
 
    private void grow() {
 
        int[] newdata= Arrays.copyOf(data,size*2);
 
        this.data=newdata;
 
    }
 
//    toString方法输出顺序表内容
 
    public String toString(){
 
        String str="[";
 
        for (int i = 0; i <size ; i++) {
 
            str+=data[i];
 
            if(i!=size-1){
 
            str+=",";
 
            }
 
        }
 
        str+="]";
 
        return str;
 
    }
 
//    尾插法:
 
    public void addLast(int value){
 
        if(size== data.length){
 
            grow();
 
        }
 
        data[size]=value;
 
        size++;
 
    }
 
//    头插法:
 
    public void addFirst(int value){
 
        if(size==data.length){
 
            grow();
 
        }
 
        for (int i = size-1; i >=0; i--) {
 
            data[i+1]=data[i];
 
        }
 
        data[0]=value;
 
        size++;
 
    }
 
//    中间任意位置插入:
 
    public void addIndex(int index,int value){
 
        if(size==data.length)
 
            grow();
 
        if(index<0||index>size){
 
            System.err.println("插入位置不合理!");
 
            return;
 
        }
 
        else {
 
            for (int i = size - 1; i >= index; i--) {
 
                data[i + 1] = data[i];
 
            }
 
            data[index] = value;
 
            size++;
 
        }
 
    }
 
//    查看当前数组中是否存在该元素
 
    public boolean contains(int value){
 
        for (int i = 0; i < size; i++) {
 
            if(data[i]==value)
 
                return true;
 
        }
 
        return false;
 
    }
 
//    查找当前数组元素对应的下标
 
    public int getIndex(int value){
 
        for (int i = 0; i < size; i++) {
 
            if(data[i]==value){
 
                return i;
 
            }
 
        }
 
        return -1;
 
    }
 
//    查找数组下标为index的元素
 
    public int getValue(int index) {
 
        if (index < 0 || index > size - 1) {
 
            System.out.println("输入下标不合理");
 
            return -1;
 
        }
 
        return data[index];
 
    }
 
//    根据索引删除元素,注意将最后一个元素置为0
 
    public void removeIndex(int index){
 
        if(index<0||index>=size){
 
            System.err.println("输入不合法!");
 
        }
 
        for (int i = index; i <size-1; i++) {
 
            data[i]=data[i+1];
 
        }
 
        size--;
 
        data[size]=0;
 
    }
 
//    删除第一个元素值为value的元素
 
    public void removeValueOnce(int value){
 
        int a=getIndex(value);
 
      removeIndex(a);
 
        }
 
//        删除所有元素值为value的元素
 
    public void removeValueAll(int value){
 
        for (int i = 0; i < size; i++) {
 
           while(i!=size||data[i]==value)
 
               removeIndex(i);
 
        }
 
    }
 
//    根据索引修改元素
 
    public void recompose(int index,int newValue){
 
        if(index<0||index>=size){
 
            System.err.println("输入不合法!");
 
        }
 
        data[index]=newValue;
 
    }
 
    }

推荐阅读