一、线性表

• 概念：是n个具有相同特性的数据元素的有限序列，是一种数据结构
• 常见的线性表：顺序表、链表、栈、队列…
• 特点：
  • 线性表在逻辑上是线性结构，也就说是连续的一条直线。
  • 在物理结构上（内存上）并不一定是连续的
  • 线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

逻辑上是连续的，物理上也是连续的，从底层来讲，顺序表就是数组，而代码上的核心操作，就是通过方法去操作数组

接口的实现

public class SqlList {private int[] elem = new int[DEFAULT_CAPACITY];private int useSize;private static final int DEFAULT_CAPACITY = 5;// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display(){for (int i = 0; i < this.useSize; i++) {System.out.print(this.elem[i] + " ");}System.out.println();}// 新增元素,默认在数据最后新增public void add(int data){if (isFull()){elem = Arrays.copyOf(elem, 2 * elem.length);}else{elem[useSize] = data;useSize++;}}public boolean isFull(){if (this.useSize == elem.length){return true;}else{return false;}}// 判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < this.useSize; i++) {if (this.elem[i] == toFind){return true;}}return false;}// 查找某个元素对应的下标public int indexOf(int toFind) {for (int i = 0; i < this.useSize; i++) {if (this.elem[i] == toFind){return i;}}return -1;}// 获取 pos 位置的元素public int get(int pos) {if (!checkPos(pos)){throw new PosException("pos不在合法范围中");}return this.elem[pos];}private boolean checkPos(int pos){if (pos <= useSize && pos > 0){return true;}else{return false;}}// 获取顺序表长度public int size() {return useSize;}// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {if (!checkPos(pos)){throw new PosException("pos不在合法范围中");}elem[pos] = value;}// 给 pos 位置的元素设为 valuepublic void add(int pos, int value) {if (pos < 0 || pos > useSize){throw new PosException("add 中下标的位置不对");}if(isFull()) {elem = Arrays.copyOf(elem,2*elem.length);}for (int i = useSize; i > pos ; i--) {elem[i + 1] = elem[i];}this.elem[pos] = value;this.useSize++;}//删除第一次出现的关键字keypublic void remove(int toRemove) {if (isEmpty()){return;}int index = indexOf(toRemove);if(index == -1) {return;//没有你要删除的数字}for (int i = index; i < useSize-1; i++) {this.elem[i] = this.elem[i+1];}this.useSize--;//elem[us] = null;     如果是引用类型，需要手动置空}public boolean isEmpty() {return useSize == 0;}// 清空顺序表public void clear() {//这是引用类型的做法/*for (int i = 0; i < useSize; i++) {this.elem[i] = null;}*/useSize = 0;}}

2.1 ArrayList

（1）概念

在集合框架中，ArrayList是一个普通的类，实现了List接口

• ArrayList是以泛型方式实现的，使用时必须要先实例化

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {ArrayList<Integer> arrayList1 = new ArrayList<>();List<Integer> arrayList2 = new ArrayList<>();//顺序表//不能调用子类自己的方法}
}

• 接口功能
  • ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
  • ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
  • ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
• 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
• ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

（2）ArrayList 的构造

• ArrayList()
  
  

• ArrayList(int initialCapacity)
  

• ArrayList(Collection<? extends E> c)
  

（3）ArrayList 的方法

（4） ArrayList的遍历

四种方法：直接打印、for循环+下标、foreach、使用迭代器

public static void main3(String[] args) {ArrayList<String> arrayList = new ArrayList<>();arrayList.add("abc");arrayList.add("def");arrayList.add("ghtb");arrayList.add("ppppppp");arrayList.add("000000000000");System.out.println(arrayList);   //因为父类中重写了toString方法，所以可以直接打印System.out.println("=====");for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i)+" ");}System.out.println();System.out.println("=====");for(String x : arrayList) {System.out.print(x+" ");}System.out.println();System.out.println("=====");Iterator<String> it = arrayList.listIterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();
}

（5）ArrayList的优缺点

• 优点

  • 根据指定下标去查找元素，效率非常高，时间复杂度为O(1)
  • 更新元素也很快：可以更新指定下标的元素

• 缺点

  • 每次插入数据，都需要移动元素，极端情况下，如果插入到0下标，那么元素复杂度为O(n)
  • 每次删除数据，都需要移动元素，极端情况下，如果插入到0下标，那么元素复杂度为O(n)
  • 当满了之后，进行1.5倍扩容，然后只放了一个元素，可能会浪费空间

  总结
  ArrayList 适用于经常进行查找元素或者更新元素的场景下

2.2 链表