线性表

线性表是一个存储相同类型数据元素的有限序列。
这里面需要关注的两个点就是，相同类型的数据、有限序列。

线性表包含两种类型：

顺序表。使用一段地址连续的存储单元依次存储线性表的数据元素。
链表。使用一组任意的存储单元存放线性表的元素。

顺序表

顺序表的特性

顺序表使用的一段连续的存储空间，因此只要知道存储顺序表的起始地址，就可以计算表中任意位置元素的地址。所以，计算任意一个元素的存储地址的时间是相等的
由于上述特性，顺序表具有随机存取的特性。
顺序表存取操作的时间复杂度为O(1)。

顺序表的实现

下面就是一个简单的顺序表的实现：


public class SeqList {
    //长度
    private int length = 0;
    //数据存储
    private Object[] datas;
    //声明线性表最大长度
    private final int MAXSIZE = 100;

    public SeqList(Object[] datas, int len) throws Exception {
        if (len > MAXSIZE) {
            throw new Exception("初始化失败，长度超过允许的最大值");
        }
        //这里使用最大长度去初始化线性表
        this.datas = new Object[MAXSIZE];
        for (int i = 0; i < len; i++) {
            this.datas[i] = datas[i];
            this.length = len;
        }
    }

    //获取坐标为i的元素
    public Object get(int i) throws Exception {
        if (i < 0 || i > length - 1) {
            throw new Exception("查找位置错误");
        } else {
            return this.datas[i];
        }
    }

    //根据值获取index
    public int getIndex(Object data) {
        for (int i = 0; i < length; i++) {
            if (data.equals(datas[i])) {
                return i;
            }
        }
        return -1;
    }

    //插入操作
    public void insert(Object data, int index) throws Exception {
        if (index < 0 || index > length) {
            throw new Exception("插入位置错误");
        } else if (index >= MAXSIZE) {
            throw new Exception("上溢");
        } else {
            for (int i = length - 1; i > index; i--) {
                datas[i + 1] = datas[i];
            }
            datas[index] = data;
            length++;
        }
    }

    //删除操作
    public void delete(int index) throws Exception {
        if (index < 0 || index > length) {
            throw new Exception("删除位置错误");
        } else if (length == 0) {
            throw new Exception("下溢");
        } else {
            System.out.println("删除的元素为：" + datas[index].toString());
            for (int i = index; i < length; i++) {
                datas[i] = datas[i + 1];
            }
            length--;
        }
    }

    //判空
    public boolean isEmpty() {
        if (length == 0) {
            return true;
        } else {
            return false;
        }
    }

    //遍历
    public void printList() {
        for (int i = 0; i < length; i++) {
            System.out.println(datas[i]);
        }
    }

    public int getLength() {
        return length;
    }
}

我们知道，Java中ArrayList类就是一个顺序表，其实现的基本原理也和上述代码差不多，但是ArrayList是包含一个自动增长的机制的，下面我们就简单分析一下这个自增长机制。

ArrayList的自增长

首先说一下ArrayList的初始化：


 private static final int DEFAULT_CAPACITY = 10;
 private static final Object[] EMPTY_ELEMENTDATA = {};
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 transient Object[] elementData; // non-private to simplify nested class access

 public ArrayList(int initialCapacity) {
     if (initialCapacity > 0) {
         this.elementData = new Object[initialCapacity];
     } else if (initialCapacity == 0) {
         this.elementData = EMPTY_ELEMENTDATA;
     } else {
         throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
     }
 }


 public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }


 public ArrayList(Collection<? extends E> c) {
     elementData = c.toArray();
     if ((size = elementData.length) != 0) {
         // c.toArray might (incorrectly) not return Object[] (see 6260652)
         if (elementData.getClass() != Object[].class)
             elementData = Arrays.copyOf(elementData, size, Object[].class);
     } else {
         // replace with empty array.
         this.elementData = EMPTY_ELEMENTDATA;
     }
 }

从构造函数可以看出，默认生成的是一个空的数组，默认的容量是10。


   public boolean add(E e) {
      ensureCapacityInternal(size + 1);  //新增一个元素时，根据当前长度扩容
      elementData[size++] = e;
      return true;
   }

   private void ensureCapacityInternal(int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  //当前数组为空时，根据传入的长度和默认容量确认应该采用哪个值进行容量需求的确认
      }

      ensureExplicitCapacity(minCapacity);
   }

   private void ensureExplicitCapacity(int minCapacity) {
      modCount++;

      if (minCapacity - elementData.length > 0)       //当容量需求大于当前长度时（这个是存储的数组的长度，而非实际存储内容的size），执行增长
          grow(minCapacity);
   }


   private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + (oldCapacity >> 1);     //增长策略为  newCapacity = oldCapacity+(oldCapacity/2)
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;                          //如果增长后仍不满足需求，则使用实际需求容量
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
      // minCapacity is usually close to size, so this is a win:
      elementData = Arrays.copyOf(elementData, newCapacity);
   }

以上就是ArrayList的自动增长的策略了，简单点来说就是先判断当前容量是否满足插入，如果不满足，执行扩容（扩容策略为新容量=原容量 + （原容量/2）），如果仍不满足，就是用当前需要的容量值作为扩容结果。（没有考虑超过MAX_ARRAY_SIZE的情况）

结语

线性表先写到这里吧，后面一篇就是把链表的部分补完，如果有什么问题，请路过的大佬予以补充~如果有人提问请在下方评论区提问，么么哒~

数据结构与算法学习系列(二)

线性表

顺序表

顺序表的特性

顺序表的实现

ArrayList的自增长

结语