数据结构系列一之线性数组

一、线性表简介

    线性表结构实际就是数组，对数组进行二次封装。开发人员如果想使用，直接调用接口操作线性数组即可，不需要手动new一个数组对象，再去维护这个对象，让研发人员更专注于业务开发。

线性表结构图如下：

二、java实现线性表

2.1、提供对线性表操作接口定义

package com.sf.bdp.array;

/**
 * Created by swcks on 2018/5/30/030.
 */
public interface MyList {
    /**
     * 新增元素
     * @param obj
     */
    public void add(Object obj);

    /**
     * 在某个位置替换元素
     * @param i
     * @param obj
     */
    public Object set(int i,Object obj);

    /**
     * 移除下标i的元素
     * @param i
     * @return
     */
    public Object remove(int i);

    /**
     * 取得下标i的元素
     * @param i
     * @return
     */
    public Object get(int i);

    /**
     * 返回线性数组数据大小
     * @return
     */
    public int size();

    /**
     * 清除线性表
     */
    public void clear();

    /**
     * 判断线性表是否为空
     * @return
     */
    public boolean isEmpty();

    /**
     * 线性数组是否包含obj元素
     * @param obj
     * @return
     */
    public boolean contain(Object obj);

    /**
     * 数组中obj对象下标
     * @param obj
     * @return
     */
    public int indexOf(Object obj);
}

2.2、线性表操作实现类

package com.sf.bdp.array;

/**
 * Created by swcks on 2018/5/30/030.
 */
public class MyArrayList implements MyList{
    private static int INIT_CAPICITY = 16;
    private Object[] data;
    private int size;

    public MyArrayList(){
        this(INIT_CAPICITY);
    }

    public MyArrayList(int initSize){
        if(initSize<0){
            throw new IllegalArgumentException();
        }
        data = new Object[initSize];
    }

    public void add(Object obj) {
        if(size>data.length-1){
            throw new IndexOutOfBoundsException();
        }
        data[size] = obj;
        size++;
    }

    public Object set(int i, Object obj) {
        if(i<0 || i>size-1){
            throw new IndexOutOfBoundsException();
        }
        Object tempObj = data[i];
        data[i] = obj;
        return obj;
    }

    public Object remove(int i) {
        if(i<0 || i>size-1){
            throw new IndexOutOfBoundsException();
        }
        Object obj = data[i];
        for(int j=i;j<size;j++){
            int temp = j+1;
            data[j] = data[temp];
        }
        size--;
        return obj;
    }

    public Object get(int i) {
        if(i<0 || i>size-1){
            throw new IndexOutOfBoundsException();
        }
        return data[i];
    }

    public int size() {
        return size;
    }

    public void clear() {
        size = 0;
    }

    public boolean isEmpty() {
        return size==0;
    }

    public boolean contain(Object obj) {
        return indexOf(obj)!= -1;
    }

    public int indexOf(Object obj) {
        if(obj == null){
            for(int i=0;i<size;i++){
                if(data[i]==null) return i;
            }
        }else{
            for(int i=0;i<size;i++){
                if(obj.equals(data[i])){
                    return i;
                }
            }
        }
        return -1;
    }
}