数据结构——线性表和顺序表

1. 认识线性表和顺序表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

1.顺序表（逻辑上线性，在内存中存储时，也是严格按照逻辑上的次序保存起来）
2.链表（逻辑上线性，在内存中存储时，不保证连续性）
注意： 顺序表中一定要区分两个概念 容量(capacity) vs 元素个数(size)；线性表的所有下标只和元素个数相关，和容量无关。

2.java中的List和ArryList

java中已经提供的顺序表 ——类：java.util.ArrayList
官方文档：https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html
重点掌握的方法：
1.boolean add(e); 向顺序表中进行“尾插”，一定会返回true

2.void add(indx,e); 向顺序表中插入e元素，放到下标为index的位置

ArrayList 是一个泛型类——元素类型用泛型表示
ArrayList a1;元素类型是integr的顺序表
ArrayList a2;元素类型是String的顺序表

1.ArrayList a = new ArrayList<>();//使用默认构造方法

import java.util.ArrayList;

public class Array {
   
    public static void main(String[] args) {
   
    //定义一个元素类型是String的顺序表
        ArrayList<String> list = new ArrayList<>();//空顺序表
        list.add ("我");
        list.add("爱");
        list.add("你");
        System.out.println(list);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

依次进行尾插运行结果：

import java.util.ArrayList;

public class Array {
   
    public static void main(String[] args) {
   
        ArrayList<String> list = new ArrayList<>();
        /*list.add ("我");
        list.add("爱");
        list.add("你");
        System.out.println(list);*/
        //合法下标[0,0]
        list.add(0,"我");
        //合法下标[0,1]
        list.add(0,"爱");
        //合法下标[0,2]
        list.add(0,"你");
        System.out.println(list);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

把 “我”“爱”“你”一次往0号下标出存放因此运行结果为：

因此我们根据这个规律

import java.util.ArrayList;

public class Array {
   
    public static void main(String[] args) {
   
        ArrayList<String> list = new ArrayList<>();
        /*list.add ("我");
        list.add("爱");
        list.add("你");
        System.out.println(list);*/
        //合法下标[0,0]
        list.add("我");
        //合法下标[0,1]
        list.add(0,"爱");
        //合法下标[0,2]
        list.add(1,"你");
        list.add(1,"他");
        list.add(0,"不爱");
        list.add(3,"就爱");
        System.out.println(list);

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

根据规律很容易得运行结果：

注：在顺序表（ArrayList）的使用过程中，不需要考虑容量问题，只需要考虑已有元素个数的问题！

2.remove(index); 删除index位置处的元素

import java.util.ArrayList;

public class Array {
   
    public static void main(String[] args) {
   
        ArrayList<String> list = new ArrayList<>(
1
2
3
4
5
6