顺序表

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

顺序表和链表区别：
顺序表：元素和元素之间，处在连续的内存空间上。

链表：元素和元素之间，可以处在不连续的内存空间上。

一、 ArrayList 的使用

1.1 创建 ArrayList 实例

 List<String> arrayList = new ArrayList<>();  // 向上转型
System.out.println(arrayList.size());
System.out.println(arrayList.isEmpty());  

1.2 添加元素

 //   add(一个参数)：添加到顺序表末尾
arrayList.add("c");
arrayList.add("c++");
arrayList.add("java");
arrayList.add("python");
System.out.println(arrayList.size());
System.out.println("尾插四次：" + arrayList);
//   add(两个参数)：添加到顺序表末尾
arrayList.add(2,"javascript");
System.out.println(arrayList.size());
System.out.println("中间插入一次：" + arrayList);  

1.3 删除

 //   按下标删除
arrayList.remove(1);
System.out.println("按位置删除" + arrayList);
//   按内容删除
arrayList.remove("c++");
System.out.println("按值删除：" + arrayList);  

1.4 查找

 // 按照内容进行查找
boolean ret = arrayList.contains("java");
System.out.println("查找java 的结果为：" + ret);
// 按照下标进行查找
int index = arrayList.indexOf("java");
System.out.println("查找java 的位置为：" + index);  

1.5 获取修改元素

 String elem = arrayList.get(0);
System.out.println("0 号元素为：" + elem);
arrayList.set(0, "PHP");
System.out.println("修改后的顺序表：" + arrayList);  

1.6 遍历

 //   （1）通过下标来进行遍历
System.out.println("通过下标来遍历：");
for (int i = 0; i < arrayList.size(); i++) {
    System.out.println(arrayList.get(i));
}
//   （2）通过 迭代器 来进行遍历
System.out.println("通过迭代器来遍历：" );
//        先通过  iterator  方法获取到迭代器对象
Iterator<String> iterator = arrayList.iterator();
//        再通过 while 循环来进行遍历
while (iterator.hasNext()) {
    String e = iterator.next();
    System.out.println(e);
}
//   （3）for-each 来进行遍历(本质上是基于迭代器)
System.out.println("通过 for-each 进行遍历：");
for (String e : arrayList) {
    System.out.println(e);
}  

二、 实现自己的 MyArrayList

 public class MyArrayList {
    private String[] data = null;
    // 当前顺序表中有效的元素个数
    private int size = 0;
    // 当前顺序表中的最大容纳元素个数，如果 size 超过了capacity 就需要扩容
    private int capacity = 100;

    public MyArrayList() {
        data = new String[capacity];
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(data[i]);
            if (i < (size - 1)) {
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    // 扩容
    private void  realloc () {
        capacity = 2 * capacity;
        String[] newData = new String[capacity];
        for (int i = 0; i < data.length; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    // 1.把元素插到顺序表末尾
    public void add(String elem) {
        if (size >= capacity) {
            realloc();
        }
        data[size] = elem;
        size ++;
    }
    // 时间复杂度：O（N）

    // 2.把元素插入到任意中间位置
    public void add (int index,String elem) {
        if (index < 0 || index > size) {
            return;
        }
        if (size >= capacity) {
            realloc();
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = elem;
        size ++;
    }

    // 3.按照下标位置删除元素
    public String remove (int index) {
        if (index < 0 || index > size) {
            return null;
        }
        String result = data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        return result;
    }

    // 4.按照元素的值删除
    public boolean remove (String elem) {
	int index = 0;
	for (; index < size; index++) {
	    if (data[index].equals(elem)) {
	        break;
	    }
	}
	if (index >= size) {
	    return false;
	}
	for (int i = index; i < size; i++) {
	    data[i] = data[i + 1];
	}
	size --;
	return true;
    }
        // 5 根据下标获取元素
    public String get (int index) {
        if (index < 0 || index > size) {
//            return null;
            // 也可以抛出一个异常
            throw new MyArrayListIndexOutOfRangeException("下标越界了！ index = " + index);
        }
        return data[index];
    }

    // 6 根据下标修改元素
    public void set (int index,String elem) {
        if (index < 0 || index > size) {
            return;
        }
        data[index] = elem;
    }

    // 7 判断元素是否存在
    public boolean contains (String elem) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(elem)) {
                return true;
            }
        }
        return false;
    }

    // 8 查找元素位置
    public int location (String elem) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }

    // 9 查找元素位置，从后往前找
    public int locationFromTail (String elem) {
        for (int i = size - 1; i > 0; i--) {
            if (data[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }

    public void clear(){
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

// 测试 
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add("c");
        myArrayList.add("c++");
        myArrayList.add("python");
        myArrayList.add("java");
        System.out.println(myArrayList);

//        myArrayList.add(2,"Go");
//        System.out.println(myArrayList);

//        String result = myArrayList.remove(0);
//        System.out.println(result);
//        System.out.println(myArrayList);

//        System.out.println(myArrayList.get(1));
//        myArrayList.set(0,"VB");
//        System.out.println(myArrayList);
//        // 验证下标越界
//        System.out.println(myArrayList.get(100));
    }