【Java数据结构】初识线性表之一：次序表

利用Java简质朴现一个次序表

次序表是用一段物理地点连续的存储单元依次存储数据元素的线性结构，一样寻常环境下采取数组存储。在数组上完成数据的增删查改。
线性表大抵包罗如下的一些方法：
   public class MyArrayList {
    private int[] array;
    private int size;
    // 默认构造方法默认分配空间
    SeqList(){   }
    // 将次序表的底层容量设置指定容量
    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() {   }
}
   接下来根据上面的方法实现一个 int 范例的次序表：

1. import java.util.Arrays;
2. public class MyArrayList {
3.     private int[] elem;
4.     private int usedSize;
5.     private static final int DEFAULT_SIZE = 10;
6.     public MyArrayList(){
7.         elem = new int[DEFAULT_SIZE];
8.     }
9.     public MyArrayList(int initCapacity){
10.         elem = new int[initCapacity];
11.     }
13.     private boolean checkCapacity(){
14.         if(this.usedSize == elem.length){
15.             return true;
16.         }
17.         return false;
18.     }
20.     public void display(){
21.         for (int i = 0; i < this.usedSize; i++) {
22.             System.out.print(this.elem[i] + " ");
23.         }
24.     }
25.     public void add(int data){
26.         if(checkCapacity()){
27.             this.elem = Arrays.copyOf(this.elem,2*elem.length);
28.         }
29.         this.elem[this.usedSize] = data;
30.         this.usedSize++;
31.         return;
32.     }
33.     public void add(int pos,int data){
34.         if(pos > this.usedSize || pos < 0){
35.             throw new PosOutOfBoundsException("插入位置错误！");
36.         }
37.         if(checkCapacity()){
38.             this.elem = Arrays.copyOf(this.elem,2*elem.length);
39.         }
40.         for (int i = this.usedSize - 1; i >=pos ; i--) {
41.             elem[i+1] = elem[i];
42.         }
43.         this.elem[pos] = data;
44.         this.usedSize++;
45.         return;
46.     }
48.     public boolean contains(int data){
49.         for (int i = 0; i < this.usedSize; i++) {
50.             if(this.elem[i] == data){
51.                 return true;
52.             }
53.         }
54.         return false;
55.     }
57.     public int indexof(int data){
58.         for (int i = 0; i < this.usedSize; i++) {
59.             if(this.elem[i] == data){
60.                 return i;
61.             }
62.         }
63.         return -1;
64.     }
65.     public int get(int pos){
66.         if(pos >= this.usedSize || pos < 0){
67.             throw new PosOutOfBoundsException("输入的位置错误！");
68.         }
69.         return this.elem[pos];
70.     }
71.     public void set(int pos,int data){
72.         if(pos >= this.usedSize || pos < 0){
73.             throw new PosOutOfBoundsException("输入的位置错误！");
74.         }
75.         this.elem[pos] = data;
76.     }
77.     public int size(){
78.         return this.usedSize;
79.     }
80.     public void remove(int data){
81.         if(this.contains(data)){
82.             int pos = this.indexof(data);
83.             for (int i = pos; i < this.usedSize - 1; i++) {
84.                 this.elem[pos] = this.elem[pos+1];
85.             }
86.             this.usedSize--;
87.         }else{
88.             throw new PosOutOfBoundsException("没有该元素");
89.         }
90.     }
91.     public void clear(){
92.         this.usedSize = 0;
93.         return;
94.     }
95. }

复制代码

ArrayList简介

在聚集框架中，ArrayList是一个平凡的类，实现了List接口，具体框架图如下：

• ArrayList是以泛型方式实现的，利用时必须要先实例化
  
• ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
  
• ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
  
• ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
  
• 和Vector差别，ArrayList不是线程安全的，在单线程下可以利用，在多线程中可以选择Vector大概
  
• CopyOnWriteArrayList
  
• ArrayList底层是一段连续的空间，而且可以动态扩容，是一个动态范例的次序表
  

ArrayList怎样利用

ArrayList的构造方法

ArrayList中的构造方法：
   ArrayList()；//无参构造
  ArrayList(Collection<? extends E> c)；//利用其他 Collection 构建 ArrayList
  ArrayList(int initialCapacity)；//指定次序表初始容量
   代码示例：

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list1 = new ArrayList<>();//无参构造
4.         List<Integer> list2 = new ArrayList<>(10);//指定容量
5.         list2.add(1);
6.         list2.add(2);
7.         list2.add(3);
8.         List<Integer> list3 = new ArrayList<>(list2);//利用其他 Collection 构建 ArrayList
9.     }
10. }

复制代码

ArrayList常见操纵

尾插

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();//无参构造
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         System.out.println(list);
8.     }
9. }

复制代码

将元素插入到指定位置

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         list.add(1,4);
8.         System.out.println(list);
9.     }
10. }

复制代码

尾插另一个次序表中的元素

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer>  list1 = new ArrayList<>();
4.         list1.add(4);
5.         list1.add(5);
6.         list1.add(6);
7.         List<Integer> list = new ArrayList<>();
8.         list.add(1);
9.         list.add(2);
10.         list.add(3);
11.         list.addAll(list1);
12.         System.out.println(list);
13.     }
14. }

复制代码

删除指定位置元素

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         list.remove(1);
8.         System.out.println(list);
9.     }
10. }

复制代码

删除指定命据

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         list.remove(new Integer(2));
8.         System.out.println(list);
9.     }
10. }

复制代码

获取指定位置元素

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         System.out.println(list.get(1));
8.     }
9. }

复制代码

将指定位置元素设置为新数据

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         list.set(1,4);
8.         System.out.println(list);
9.     }
10. }

复制代码

清空次序表

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         list.clear();
8.         System.out.println(list);
9.     }
10. }

复制代码

判定一个元素是否在次序表中

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         System.out.println(list.contains(2));
8.         System.out.println(list.contains(4));
9.     }
10. }

复制代码

返回第一个指定元素地点下标

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         list.add(1);
8.         System.out.println(list.indexOf(1));
9.     }
10. }

复制代码

返回末了一个指定元素地点下标

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         list.add(1);
8.         System.out.println(list.lastIndexOf(1));
9.     }
10. }

复制代码

截取部门list

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         System.out.println(list.subList(0,2));
8.     }
9. }

复制代码

遍历 ArrayList 的三种方法

ArrayList 可以利用三方方式遍历：for循环+下标、foreach增强循环、利用迭代器

1. public class Test {
2.     public static void main(String[] args) {
3.         List<Integer> list = new ArrayList<>();
4.         list.add(1);
5.         list.add(2);
6.         list.add(3);
7.         //使用fori遍历
8.         for (int i = 0; i < list.size(); i++) {
9.             System.out.print(list.get(i));
10.         }
11.         System.out.println();
12.         //使用foreach遍历
13.         for(Integer integer:list){
14.             System.out.print(integer);
15.         }
16.         System.out.println();
17.         //使用迭代器遍历
18.         Iterator<Integer> it = list.listIterator();
19.         while(it.hasNext()){
20.             System.out.print(it.next());
21.         }
22.     }
23. }

复制代码

运行效果：

 ArrayList的场景利用
洗牌算法

将一副扑克牌随机打乱，并分配给三个人，每人五张牌
算法原码地点位置：
shufflecards · 不绝淡水鱼/Java经典例题 - 码云 - 开源中国 (gitee.com)
杨辉三角

标题形貌：

代码实现：

1. public class Test {
2.     public static List<List<Integer>> generate(int numRows) {
3.         List<List<Integer>> list = new LinkedList<>();
4.         for (int i = 0; i < numRows; i++) {
5.             List<Integer> row = new LinkedList<>();
6.             for (int j = 0; j < i + 1; j++) {
7.                 if (j == 0 || i == j) {
8.                     row.add(1);
9.                 } else {
10.                     row.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
11.                 }
12.             }
13.             list.add(row);
14.         }
15.         return list;
16.     }
18.     public static void main(String[] args) {
19.         Scanner scanner = new Scanner(System.in);
20.         int numRows = scanner.nextInt();
21.         List<List<Integer>> list = generate(numRows);
22.         for (int i = 0; i < numRows; i++) {
23.             for (int j = 0; j < i + 1; j++) {
24.                 System.out.print(list.get(i).get(j) + " ");
25.             }
26.             System.out.println();
27.         }
28.     }
29. }

复制代码

 运行效果图：