数据结构 - 2（顺序表10000字详解）

List<String> arrayList = new ArrayList<>(); // 使用ArrayList实现
List<Integer> linkedList = new LinkedList<>(); // 使用LinkedList实现
//添加元素
arrayList.add("Apple");
arrayList.add("Banana");
arrayList.add("Orange");
//添加元素
linkedList.add(10);
linkedList.add(20);
linkedList.add(30);

ArrayList<String> arrayList = new ArrayList<>(list);

public static void main(String[] args) {
  List<String> list = new ArrayList<>();
  list.add("JavaSE");
  list.add("JavaWeb");
  list.add("JavaEE");
  list.add("JVM");
  list.add("测试课程");
  System.out.println(list);
  // 获取list中有效元素个数
  System.out.println(list.size());
  // 获取和设置index位置上的元素，注意index必须介于[0, size)间
  System.out.println(list.get(1));
  list.set(1, "JavaWEB");
  System.out.println(list.get(1));
  // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
  list.add(1, "Java数据结构");
  System.out.println(list);
  // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
  list.remove("JVM");
  System.out.println(list);
  // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
  list.remove(list.size()-1);
  System.out.println(list);
  // 检测list中是否包含指定元素，包含返回true，否则返回false
  if(list.contains("测试课程")){
    list.add("测试课程");
 }
  // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
  list.add("JavaSE");
  System.out.println(list.indexOf("JavaSE"));
  System.out.println(list.lastIndexOf("JavaSE"));
  // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
  List<String> ret = list.subList(0, 4);
  System.out.println(ret);
  list.clear();
  System.out.println(list.size());
}

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();
  // 借助foreach遍历
  for (Integer integer : list) {
    System.out.print(integer + " ");
 }
  System.out.println();
  //迭代器遍历
  Iterator<Integer> it = list.listIterator();
  while(it.hasNext()){
    System.out.print(it.next() + " ");
 }
  System.out.println();
}

while(it.hasNext()){
    System.out.print(it.next() + " ");
 }

public class SeqList {
  private int[] array;
  private int size;
  // 默认构造方法
  SeqList(){  }
  // 将顺序表的底层容量设置为initcapacity
  SeqList(int initcapacity){  }
  // 新增元素,默认在数组最后新增
  public void add(int data) { }
  // 在 pos 位置新增元素
  public void add(int pos, int data) { }
  // 判定是否包含某个元素
  public boolean contains(int toFind) { return true; }
  // 查找某个元素对应的位置
  public int indexOf(int toFind) { return -1; }
  // 获取 pos 位置的元素
  public int get(int pos) { return -1; }
  // 给 pos 位置的元素设为 value
  public void set(int pos, int value) {  }
  //删除第一次出现的关键字key
  public void remove(int toRemove) {  }
  // 获取顺序表长度
  public int size() { return 0; }
  // 清空顺序表
  public void clear() {  }
  // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
  public void display() {  }
}

class MyArrayList {
  private int[] array;
  private int size;
  // 默认构造方法
  public MyArrayList() {
    // 初始化底层数组，初始容量为10
    array = new int[10];
    // 初始大小为0
    size = 0;
  }
  // 将顺序表的底层容量设置为initCapacity
  public MyArrayList(int initCapacity) {
    if (initCapacity < 0) {
      throw new IllegalArgumentException("容量不能小于0");
    }
    // 初始化底层数组，初始容量为initCapacity
    array = new int[initCapacity];
    // 初始大小为0
    size = 0;
  }
  // 在数组最后新增元素
  public void add(int data) {
    // 如果数组已满，则扩容
    if (size == array.length) {
      resize();
    }
    // 在数组末尾新增元素
    array[size] = data;
    // 更新大小
    size++;
  }
  // 在指定位置新增元素
  public void add(int pos, int data) {
    // 检查位置是否合法
    if (pos < 0 || pos > size) {
      throw new IndexOutOfBoundsException("索引超出范围");
    }
    // 如果数组已满，则扩容
    if (size == array.length) {
      resize();
    }
    // 将指定位置及其后面的元素后移一位
    for (int i = size - 1; i >= pos; i--) {
      array[i + 1] = array[i];
    }
    // 在指定位置插入元素
    array[pos] = data;
    // 更新大小
    size++;
  }
  // 判定是否包含某个元素
  public boolean contains(int toFind) {
    // 遍历数组查找元素
    for (int i = 0; i < size; i++) {
      if (array[i] == toFind) {
        return true;
      }
    }
    return false;
  }
  // 查找某个元素对应的位置
  public int indexOf(int toFind) {
    // 遍历数组查找元素
    for (int i = 0; i < size; i++) {
      if (array[i] == toFind) {
        return i;
      }
    }
    // 未找到元素，返回-1
    return -1;
  }
  // 获取指定位置的元素
  public int get(int pos) {
    // 检查位置是否合法
    if (pos < 0 || pos >= size) {
      throw new IndexOutOfBoundsException("索引超出范围");
    }
    // 返回指定位置的元素
    return array[pos];
  }
  // 设置指定位置的元素
  public void set(int pos, int value) {
    // 检查位置是否合法
    if (pos < 0 || pos >= size) {
      throw new IndexOutOfBoundsException("索引超出范围");
    }
    // 更新指定位置的元素
    array[pos] = value;
  }
  // 删除第一次出现的指定元素
  public void remove(int toRemove) {
    // 遍历数组查找要删除的元素
    for (int i = 0; i < size; i++) {
      if (array[i] == toRemove) {
        // 将要删除元素后面的元素前移一位
        for (int j = i + 1; j < size; j++) {
          array[j - 1] = array[j];
        }
        // 更新大小
        size--;
        return;
      }
    }
  }
  // 获取顺序表长度
  public int size() {
    return size;
  }
  // 清空顺序表
  public void clear() {
    // 将数组清空
    for (int i = 0; i < size; i++) {
      array[i] = 0;
    }
    // 大小置为0
    size = 0;
  }
  // 扩容数组
  private void resize() {
    // 创建新的数组，长度为当前容量的两倍
    int[] newArray = new int[array.length * 2];
    // 将原数组中的元素复制到新数组中
    for (int i = 0; i < size; i++) {
      newArray[i] = array[i];
    }
    // 更新底层数组
    array = newArray;
  }
  // 打印顺序表
  public void display() {
    // 遍历数组打印元素
    for (int i = 0; i < size; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println();
  }
}

public class Main {
    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();
        // 测试默认构造方法
        System.out.println("测试默认构造方法：");
        System.out.println("顺序表是否为空：" + (list.size() == 0));
        System.out.println("顺序表的大小：" + list.size());
        list.display();
        // 测试 add 方法
        System.out.println("\n测试 add 方法：");
        list.add(1);
        list.add(2);
        list.add(3);
        list.display();
        // 测试 add(pos, data) 方法
        System.out.println("\n测试 add(pos, data) 方法：");
        list.add(1, 5);
        list.display();
        // 测试 contains 方法
        System.out.println("\n测试 contains 方法：");
        System.out.println("顺序表中是否包含元素 2：" + list.contains(2));
        System.out.println("顺序表中是否包含元素 4：" + list.contains(4));
        // 测试 indexOf 方法
        System.out.println("\n测试 indexOf 方法：");
        System.out.println("元素 2 在顺序表中的位置：" + list.indexOf(2));
        System.out.println("元素 4 在顺序表中的位置：" + list.indexOf(4));
        // 测试 get 方法
        System.out.println("\n测试 get 方法：");
        System.out.println("位置 2 上的元素：" + list.get(2));
        // 测试 set 方法
        System.out.println("\n测试 set 方法：");
        list.set(1, 4);
        list.display();
        // 测试 remove 方法
        System.out.println("\n测试 remove 方法：");
        list.remove(2);
        list.display();
        // 测试 size 方法
        System.out.println("\n测试 size 方法：");
        System.out.println("顺序表的大小：" + list.size());
        // 测试 clear 方法
        System.out.println("\n测试 clear 方法：");
        list.clear();
        list.display();
        System.out.println("顺序表是否为空：" + (list.size() == 0));
    }
}

测试默认构造方法： 顺序表是否为空：true 顺序表的大小：0
测试 add 方法： 1 2 3 
测试 add(pos, data) 方法： 1 5 2 3 
测试 contains 方法： 顺序表中是否包含元素 2：true 顺序表中是否包含元素 4：false
测试 indexOf 方法： 元素 2 在顺序表中的位置：2 元素 4 在顺序表中的位置：-1
测试 get 方法： 位置 2 上的元素：2
测试 set 方法： 1 4 2 3 
测试 remove 方法： 1 4 3 
测试 size 方法： 顺序表的大小：3
测试 clear 方法：
顺序表是否为空：true