【数据结构】——顺序表

一、认识线性表和顺序表

1. 线性表是n个具有相同特性的数据元素的有限序列,常见的线性表有:顺序表、链表、栈、队列。
2. 线性表在逻辑上是线性结构，也就说是连续的一条直线。但在物理结构上并不一定是连续的，线性表在物理上存储时，通常是以数组和链式结构的形式存储的。
3. 顺序表是用一段物理地址连续的存储单元一次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。

二、顺序表的接口实现

• 打印顺序表 

 public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }

• 新增元素,默认在数组最后新增

 public void add(int data) {
        if (isFull()){
            elem = Arrays.copyOf(elem,2* elem.length);
        }
        elem[usedSize++] = data;
    }
 public boolean isFull(){
        return usedSize == elem.length;
    }

• 在 pos 位置新增元素

private void checkAddPos(int pos){
        if (pos < 0 || pos > usedSize){
            throw new PosIndexNotLegalException("pos位置不合法");
        }
    }
    public void add(int pos, int data) {
        try {
            checkAddPos(pos);
            if (isFull()){
                elem = Arrays.copyOf(elem,2* elem.length);
            }
            for (int i = usedSize-1; i >= pos; i++) {
                elem[i+1] = elem[i];
            }
            elem[pos] = data;
            usedSize++;
        }catch (PosIndexNotLegalException e){
            e.printStackTrace();
        }
 
    }

•   判定是否包含某个元素

public boolean contains(int toFind) {
         for (int i = 0; i < usedSize; i++) {
             if (elem[i] == toFind){
                 return true;
             }
         }
        return true;
    }

• 查找某个元素对应的位置

public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }

•  获取 pos 位置的元素

private void checkGetPos(int pos){
        if (pos < 0 || pos > usedSize){
            throw new PosIndexNotLegalException("pos位置不合法");
        }
    }
    public int get(int pos) {
        int retVal = -1;
        try {
            checkGetPos(pos);
            retVal = elem[pos];
        }catch (PosIndexNotLegalException e){
            e.printStackTrace();
        }
        return retVal;
    }
// 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        checkGetPos(pos);
        elem[pos] = value;
    }

•  删除第一次出现的关键字key

public void remove(int key) {
        int index = indexOf(key);
        if (index == -1){
            System.out.println("没有你要删除的数字!");
            return;
        }
        for (int i = index; i < usedSize-1; i++) {
            elem[i] = elem[i+1];
        }
        usedSize--;
    }
// 获取顺序表长度
    public int size() {
        return usedSize;
    }
    // 清空顺序表
    public void clear() {
 
        usedSize = 0;
    }

三、ArrayList的使用

3.1 ArrayList的构造

1. 无参构造 ：ArrayList（）
2. 利用其他Collection构建ArrayList：ArrayList（Collection c）
3. 指定顺序表初始容量: ArrayList(int intialCapacity)

public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();
        aList.add(1);
        list1.add(2);
        list1.add(3);
        System.out.println(list1);
 
 
        List<Integer> list2 = new ArrayList<>(10);//扩容是1.5倍
 
        // list3构造好之后，与list中的元素一致
        ArrayList<Integer> list3 = new ArrayList<>(list2);
    }

3.2 ArrayList常见操作

 3.3 ArrayList的遍历

1、for循环加下标

 public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
// 使用下标+for遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
}

 2、foreach遍历

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
// 借助foreach遍历
        for (Integer integer : list) {
            System.out.print(integer + " ");
        }
        System.out.println();
}

 3、迭代器遍历

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        Iterator<Integer> it = list.listIterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();
 
    }

注：ArrayList扩容是按照1.5倍大小扩容，乳沟多用户的所需大小超过预估的1.5倍大小，则按照用户所需大小进行扩容，在真正扩容之前检查是否能扩容扩容成功，防止太大导致扩容失败。