一：线性表
1:线性表的概念：
线性表是n个具有相同特性的数据元素的有限序列。
常见的线性表有：顺序表，链表，栈，队列…
线性表在逻辑上是连续的（线性结构），在空间上（内存存储）不一定是连续的。线性表在空间上存储时，一般以数组或链式结构的形式存储。
二：顺序表：
1:顺序表的概念：
顺序表是一段用一段空间地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数组的增删改查。
2. 实现 ArrayList 类
public class MyArraylist { public int[] elem; public int usedSize;//0 //默认容量 private static final int DEFAULT_SIZE = 10; public MyArraylist() { this.elem = new int[DEFAULT_SIZE]; } /** * 打印顺序表: * 根据usedSize判断即可 */ public void display() { } // 新增元素,默认在数组最后新增 public void add(int data) { } /** * 判断当前的顺序表是不是满的！ * @return true:满 false代表空 */ public boolean isFull() { } private boolean checkPosInAdd(int pos) { return true;//合法 } // 在 pos 位置新增元素 public void add(int pos, int data) { } // 判定是否包含某个元素 public boolean contains(int toFind) { return false; } // 查找某个元素对应的位置 public int indexOf(int toFind) { return -1; } // 获取 pos 位置的元素 public int get(int pos) { } private boolean isEmpty() { } // 给 pos 位置的元素设为【更新为】 value public void set(int pos, int value) { } /** * 删除第一次出现的关键字key * @param key */ public void remove(int key) { } // 获取顺序表长度 public int size() { } // 清空顺序表 public void clear() { }
import java.util.Arrays; class MyArraylist { public int[] elem; public int usedSize;//0 //默认容量 private static final int DEFAULT_SIZE = 10;//初始化顺序表usedSize=0; public MyArraylist() { this.elem = new int[DEFAULT_SIZE]; } /** * 打印顺序表: * 根据usedSize判断即可 */ 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, elem.length * 2); } elem[usedSize] = data; usedSize++; } /** * 判断当前的顺序表是不是满的！ * * @return true:满 false代表空 */ public boolean isFull() { //如果数组满了，返回true return usedSize == elem.length; } private boolean checkPosInAdd(int pos) { if (pos > 0 || pos <= usedSize) { return true; } else { return false; } } // 在 pos 位置新增元素 public void add(int pos, int data) { if (checkPosInAdd(pos)) {//判断pos位置是否合法 for (int i = usedSize - 1; i <= pos; i++) { elem[i + 1] = elem[i]; } elem[pos] = data; usedSize++; } else { throw new PosException("pos越界:pos=" + pos); } } // 判定是否包含某个元素 public boolean contains(int toFind) { for (int i = 0; i < usedSize; i++) { if (elem[i] == toFind) { return true; } } return false; } // 查找某个元素对应的位置 public int indexOf(int toFind) { for (int i = 0; i < usedSize; i++) { if (elem[i] == toFind) { return i; } } return -1; } // 获取 pos 位置的元素 public int get(int pos) { //pos位置是否合法 if (pos < 0 || pos >= usedSize) { throw new PosException("pos越界:pos=" + pos); } if(isEmpty()){//顺序表是否为空 throw new IsEmptyExcepptiom("顺序表为空"); } return elem[pos]; } private boolean isEmpty() { if (usedSize == 0) { return true; } return false; } // 给 pos 位置的元素设为【更新为】 value public void set(int pos, int value) { if (pos < 0 || pos >= usedSize) {//pos位置是否合法 throw new PosException("pos越界:pos=" + pos); } elem[pos] = value; } /** * 删除第一次出现的关键字key * * @param key */ public void remove(int key) { if(isEmpty()){ throw new IsEmptyExcepptiom("顺序表为空"); } int index=indexOf(key); for (int i = index; i < usedSize - 1; i++) { elem[i] = elem[i + 1]; } usedSize--; } // 获取顺序表长度 public int size() { return usedSize; } // 清空顺序表 public void clear() { usedSize = 0; } } **顺序表模拟实现** public class Test { public static void main(String[] args) { MyArraylist myArraylist=new MyArraylist(); myArraylist.add(1); myArraylist.add(2); myArraylist.add(3); myArraylist.add(4); myArraylist.add(5); myArraylist.display(); myArraylist.set(0,100); myArraylist.display(); myArraylist.remove(2); myArraylist.display(); } }
3：顺序表的缺点：
1：ArrayList底层使用连续的空间，任意位置插入或者删除元素时，需要将后面的数据整体往前移动或者往后移动，故时间复杂度为O（n)；
2：扩容需要申请新的空间，拷贝数据，释放旧的空间，会有不小的消耗。
3:扩容：空间一般扩大为原来的2倍，会造成空间的浪费。比如原来空间为1000，而扩容变成2000，但只增加1个数据，造成空间极大的浪费。
