线性表-顺序结构

对于一个非空的线性表,逻辑结构特征如下

• 有且仅有一个开始节点a1,没有直接前趋节点,有且仅有一个直接后继节点a2
• 有且仅有一个结束节点an,没有直接后继节点,有且仅有一个直接前趋节点a(n-1)
• 其余节点均都有一个前趋节点和一个后继节点
• 数据元素的类型都必须相同

线性表-顺序表的结构

• 顺序表就是按照顺序存储方式存储的线性表,该线性表的节点按照逻辑次序依次存放在计算机的一组连续的存储单元中(Array):java中实现为ArrayList
• 下面实现,下标依旧是从0开始的,下面的实现并没有加入额外的非法输入控制,只是实现了一个大概的逻辑

public class MyArrayList<T> {
    //默认大小
    private static final int DEFAULT_SIZE = 20;
    //存放元素的数组对象
    private Object[] elements ;
    private int length;
    public MyArrayList() {
        elements = new Object[DEFAULT_SIZE];
    }
    public MyArrayList(int initSize) {
        elements = new Object[initSize];
    }
    //追加节点
    public void staticAdd(T element){
        if (! judgeLength()){
            throw new RuntimeException("元素已满:" + length);
        }
        elements[length] = element;
        length++;
    }
    //追加节点
    public void dynamicAdd(T element){
        if (! judgeLength()){
            dilatation();
        }
        staticAdd(element);
    }
    //插入节点
    public void staticInsert(T element, int index){
        if (! judgeLength()){
            throw new RuntimeException("元素已满:" + length);
        }
        Object[] tmp = new Object[length - index];
        System.arraycopy(elements,index,tmp,0,length-index);
        elements[index] = element;
        System.arraycopy(tmp,0,elements,index+1,length-index);
        length++;
    }
    //获取节点
    public T get(int index){
        return (T) elements[index];
    }
    //动态插入
    public void dynamicInsert(T element, int index){
        if (! judgeLength()){
            dilatation();
        }
        staticInsert(element,index);
    }
    //删除节点
    public void delete(T element){
        int i = findFirst(element);
        delete(i);
    }
    //删除节点
    public void delete(int index){
        Object[] tmp = this.elements;
        System.arraycopy(tmp,index + 1,elements,index,length - index + 1);
        length -- ;
    }
    //删除集合中全部与element相同的元素
    public void deleteAll(T element){
        int i = 0;
        while (i >= 0){
            i = findFirst(element);
            if (i >= 0){
                delete(i);
            }
        }
    }
    //修改节点
    public void update(T element , int index ){
        elements[index] = element;
    }
    //查询节点
    private int findFirst(T element){
        for (int i = 0; i < length; i++) {
            if (element.equals(elements[i])){
                return i;
            }
        }
        return -1;
    }
    //判断空间是否够用
    private boolean judgeLength(){
        if (length < elements.length){
            return true;
        }
        return false;
    }
    //扩容
    private void dilatation(){
        Object[] tmp = elements;
        elements = new Object[length * 2];
        System.arraycopy(tmp,0,elements,0,length);
    }
    //返回列表长度
    public int getLength() {
        return length;
    }
    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer(length * 2 + 5);
        buffer.append("[");
        for (int i = 0; i < length; i++) {
            if (i == length - 1) {
                buffer.append(elements[i] + "]");
                break;
            }
            buffer.append(elements[i] + ",");
        }
        return buffer.toString();
//        return Arrays.toString(elements);
    }
}

在实现的过程中,我遇到了一个问题.那就是System.arraycopy快,还是说我们仿照的ArrayList中使用的Arrays.copy快,所以我做了一个测试

int nano = Instant.now().getNano();
MyArrayList<Integer> a  = new MyArrayList<>();
for (int i = 0; i < 10000000; i++) {
    a.dynamicAdd(i);
}
System.out.println(a.getLength());
System.out.println(Instant.now().getNano() - nano);

结果

一千万add时候
  MyArrayList
    10000000
    532000000
  ArrayList
    10000000
    427000000
五千万add的时候  
  MyArrayList
      50000000
      609000000
  ArrayList
      50000000
      计算不出来的负数

算是一个结果吧,当数据很大的时候System.copy比Arrays.copy要快点,网上很多求证帖子得出了如下的结论

当数组元素个数不是很大时，for>clone>System.arraycopy>Arrays.copyof。
当数组元素个数很大时，System.arraycopy>clone>Arrays.copyof>for。

并且新收获了一个知识点System.arraycopy是浅复制的,只是复制了对象的引用而已,所以以后使用这个方法的时候就必须注意了

public class Test {
    int i ;
    public Test(int i) {
        this.i = i;
    }
    public static void main(String[] args) {
        Test[] t = new Test[10];
        t[0] = new Test(0);
        t[1] = new Test(1);
        t[2] = new Test(2);
        Test[] t2 = new Test[10];
        System.arraycopy(t,0,t2,0,t.length);
        print(t);
        print(t2);
        t2[0].i = 222;
        print(t);
        print(t2);
    }

    private static void print(Test[] t) {
      ...
    }
    /**
     *  如下打印的是Test的对象,也能看出来是同一个对象
     * [Test@1b6d3586, Test@4554617c, Test@74a14482, null, null, null, null, null, null, null]
     * [Test@1b6d3586, Test@4554617c, Test@74a14482, null, null, null, null, null, null, null]
     * [Test@1b6d3586, Test@4554617c, Test@74a14482, null, null, null, null, null, null, null]
     * [Test@1b6d3586, Test@4554617c, Test@74a14482, null, null, null, null, null, null, null]
     */
}

结果为

0,1,2
0,1,2
222,1,2
222,1,2