Skip to main content
 首页 » 编程设计

java算法之自定义线性结构-数组方式

2022年07月18日48jirigala
/** 
* @desc   : 线性接口定义,继承Iterable接口,目的是要foreach 
* @author : 毛会懂 
* @create: 2020/12/25 14:22:00 
**/ 
public interface MyList<T> extends Iterable<T> { 
    //增加元素 
    void add(T t); 
 
    //在指定位置增加元素 
    void add(Integer i,T t); 
 
    //删除指定位置的元素,并返回此元素 
    T remove(Integer i); 
 
    //修改元素 
    void update(int i, T t); 
 
    //查询指定位置的元素 
    T get(int i); 
 
    //查找元素第一次出现的位置 
    Integer indexOf(T t); 
 
    //是否为空 
    Boolean isEmpty(); 
 
    //元素个数 
    Integer length(); 
 
    //清空表 
    void clean(); 
} 
 
/** 
 * @desc: 自定义线性结构-数组实现 
 * @author: 毛会懂 
 * @create: 2020-12-25 13:25:00 
 **/ 
public class MyArrayList<T> implements MyList<T>{ 
    private T[] arr; 
    private Integer N; 
 
    public MyArrayList(Integer capacity){ 
        arr = (T[])new Object[capacity]; 
        N = 0; 
    } 
 
    //增加元素 
    @Override 
    public void add(T t){ 
        //扩容 
        if(N == arr.length){ 
            resize(N * 2); 
        } 
        arr[N++] = t; 
    } 
 
    //在指定位置增加元素 
    @Override 
    public void add(Integer i,T t){ 
        //扩容 
        if(N == arr.length){ 
            resize(N * 2); 
        } 
 
        if(i < 0 || i > N){ 
            throw new RuntimeException("当前元素不存在"); 
        } 
        for(int index = N;index > i;index--){ 
            arr[index] = arr[index -1]; 
        } 
        arr[i] = t; 
        N++; 
    } 
 
    //删除指定位置的元素,并返回此元素 
    @Override 
    public T remove(Integer i){ 
        //缩容 
        if(N > 0 && N < arr.length / 4){ 
            resize(arr.length / 4); 
        } 
 
        if(i < 0 || i >= N){ 
            throw new RuntimeException("当前位置不存在"); 
        } 
        T t = arr[i]; 
        for(int index = i;index<N-1;index++){ 
            arr[index] = arr[index+1]; 
        } 
        N--; 
        return t; 
    } 
 
    //修改元素 
    @Override 
    public void update(int i, T t){ 
        if(i < 0 || i >= N){ 
            throw new RuntimeException("当前元素不存在"); 
        } 
        arr[i] = t; 
    } 
 
    //查询指定位置的元素 
    @Override 
    public T get(int i){ 
        if(i < 0 || i >= N){ 
            throw new RuntimeException("当前元素不存在"); 
        } 
        return arr[i]; 
    } 
 
    //查找元素第一次出现的位置 
    @Override 
    public Integer indexOf(T t){ 
        if(t == null){ 
            throw new RuntimeException("元素不能为空"); 
        } 
        for(int i = 0;i < N;i++){ 
            if(arr[i].equals(t)){ 
                return i; 
            } 
        } 
        return -1; 
    } 
 
    //是否为空 
    @Override 
    public Boolean isEmpty(){ 
        return N == 0; 
    } 
 
    //元素个数 
    @Override 
    public Integer length(){ 
        return N; 
    } 
 
    //清空表 
    @Override 
    public void clean(){ 
        N = 0; 
    } 
 
    //扩容与缩容 
    public void resize(Integer newSize){ 
        T[] newArr = (T[])new Object[newSize]; 
        System.arraycopy(arr,0,newArr,0,N); 
        arr = newArr; 
    } 
 
 
    //遍历集合的方式一般都是用的是foreach循环,如果想让我们的MyArrayList也能支持foreach循环,则 
    //需要做如下操作(为了更方便,MyList接口继承Iterable接口): 
    // 1.让MyArrayList实现Iterable接口,重写iterator方法; 
    // 2.在MyArrayList内部提供一个内部类myIterator,实现Iterator接口,重写hasNext方法和next方法; 
    @Override 
    public Iterator<T> iterator() { 
        return new myIterator(); 
    } 
 
    private class myIterator implements Iterator{ 
        private int current; 
        @Override 
        public boolean hasNext() { 
            return current < N; 
        } 
 
        @Override 
        public Object next() { 
            return arr[current++]; 
        } 
    } 
} 
 
 
public class Main { 
    public static void main(String[] args) { 
        MyList<Integer> list = new MyArrayList(3); 
        list.add(1); 
        list.add(2); 
        list.add(3); 
        list.add(4); 
        list.add(5); 
        list.add(6); 
        list.add(7); 
        list.add(8); 
        System.out.println(list.indexOf(2)); 
        list.remove(1); 
        list.add(0,-1); 
        list.update(0,-2); 
        System.out.println(list.isEmpty()); 
        System.out.println(list.length()); 
        System.out.println(list.get(0)); 
        //list.clean(); 
        System.out.println(list.length()); 
        System.out.println("----------------"); 
        for (Integer i : list){ 
            System.out.println(i); 
        } 
        System.out.println("-------------"); 
        list.forEach(System.out::println); 
        System.out.println("--------"); 
        Iterator<Integer> iterator = list.iterator(); 
        while (iterator.hasNext()) { 
            System.out.println(iterator.next()); 
        } 
    } 
}

本文参考链接:https://www.cnblogs.com/maohuidong/p/14189011.html