Java实现线性表的顺序存储结构(ArrayList)

发布于 2021-07-16  72 次阅读


要用迭代器需要实现Iterable接口,Iterable()返回值是一个是重写了hasNext()和next()的对象;

自动扩容:新建一个数组拷贝过去;

顺序表代码:

package com.apesblog.Sequence;

import java.util.Iterator;

import org.omg.CORBA.PUBLIC_MEMBER;

public class SequenceList<T> implements Iterable<T> {

    private T[] eles;

    private int N;

    public SequenceList(int capacity) {
        eles = (T[]) new Object[capacity];
        N = 0;
    }

    public void clean() {
        N = 0;
    }

    public int getLength() {
        return N;
    }

    public T get(int i) {
        if (i < 0 || i >= N) {
            throw new RuntimeException("当前元素不存在!");
        }
        return eles[i];
    }

    public void insert(int i, T t) {
//		if (N == eles.length) {
//			throw new RuntimeException("已满");
//		}
        if (N == eles.length) {
            resize(2 * eles.length);
        }
        if (i < 0 || i > eles.length) {
            throw new RuntimeException("插入位置不合法");
        }
        for (int k = N; k > i; k--) {
            eles[k] = eles[k - 1];
        }
        eles[i] = t;
        N++;
    }

    public void add(T t) {
//		if (N == eles.length) {
//			throw new RuntimeException("已满");
//		}
        if (N == eles.length) {
            resize(2 * eles.length);
        }
        eles[N++] = t;
    }

    public void remove(int i) {
        if (i < 0 || i > N - 1) {
            throw new RuntimeException("删除位置不合法");
        }
        // eles[i - 1] = null;
        for (int k = i; k < N - 1; k++) {
            eles[k] = eles[k + 1];
        }
        N--;
        if (N < eles.length / 4) {
            resize(eles.length / 2);
        }
    }

    public int indexOf(T t) {
        for (int i = 0; i <= eles.length; i++) {
            if (eles[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public Iterator<T> iterator() {

        return new SIterator();
    }

    private class SIterator implements Iterator {
        private int cusor;

        public SIterator() {
            this.cusor = 0;
        }

        @Override
        public boolean hasNext() {
            return cusor < N;
        }

        @Override
        public Object next() {
            return eles[cusor++];
        }
    }

    public void resize(int newSize) {
        // 定义一个临时数组,指向原数组
        T[] temp = eles;
        // 创建新数组
        eles = (T[]) new Object[newSize];
        // 把原数组的数据拷贝到新数组
        for (int i = 0; i < N; i++) {
            eles[i] = temp[i];
        }
    }

}

测试类:

package com.apesblog.Sequence;

public class Test {

    public static void main(String[] args) {
        SequenceList<String> s = new SequenceList<String>(2);
        s.add("0");
        s.add("1");
        s.add("2");
        s.add("3");
        s.add("5");
        s.add("6");
        System.out.println("获取:" + s.get(2));
        StringBuilder str = new StringBuilder(300);
        str.append("遍历:");
        for (String i : s) {
            str.append("[" + i + "] ");
        }
        System.out.println(str);

        s.insert(4, "4");
        str.delete(0, str.length());
        str.append("插入:");
        for (String i : s) {
            str.append("[" + i + "] ");
        }
        System.out.println(str);

        str.delete(0, str.length());
        s.remove(0);
        str.append("删除:");
        for (String i : s) {
            str.append("[" + i + "] ");
        }
        System.out.println(str);

    }

}

结果: