顺序表（ArrayList）

1、简介

        顺序表是用一段物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下 采用数组存储 。在 数组 上完成数据的增删查改。（ 顺序表的底层结构是一个数组 ）

2、顺序表的实现

       下面是顺序表的一些基本成员和方法，能够让大家更好的认识和了解顺序表：

1、组成成员和构造方法

    private int[] elem;//用来存放数据元素private int usedSized;//用来计算有效数据元素的个数public final static int DEFUALT_SIZE = 10;//无参构造方法，初始化默认长度的顺序表public MyArrayList() {this.elem = new int[DEFUALT_SIZE];}// 将顺序表的底层容量设置为initcapacitypublic MyArrayList(int initcapacity ) {this.elem = new int[initcapacity];}

2、新增元素（默认在数组最后新增）

//新增元素  默认在最后添加public boolean isFull(){if(this.elem.length==this.usedSized){return true;}return false;}public void add(int data) {//如果满了，则要进行扩容if(isFull()){//扩容this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[this.usedSized] = data;this.usedSized++;}

 3、在pos位置新增元素

//在pos位置新增元素public void add(int pos, int data) {if(pos < 0||pos > usedSized){throw new PosOutOfBoundsException(pos+"下标位置不合法");}//如果满了，则要进行扩容if(isFull()){//扩容this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}for (int i = this.usedSized - 1; i >= pos ; i--) {//这里pos位置的数据也需要往后挪this.elem[i+1] = this.elem[i];}this.elem[pos] = data;this.usedSized++;}

自定义异常的代码 ：

public class PosOutOfBoundsException extends RuntimeException {public PosOutOfBoundsException(String message) {super(message);}
}

4、判定是否包含某个元素

//判定是否包含某个元素
public boolean contains(int toFind) {for (int i = 0; i < this.usedSized; i++) {if(this.elem[i] == toFind){return true;}}return false;}

5、查找某个元素对应的位置

//查找某个元素对应的位置 
public int indexOf(int toFind) {for (int i = 0; i < this.usedSized; i++) {if(this.elem[i] == toFind){return i;}}return -1;}

6、获取pos位置的元素

//判断pos位置是否合法private void checkPos(int pos){if(pos < 0 ||pos >= this.usedSized){throw new PosOutOfBoundsException(pos+"下标位置不合法");}}
//获取pos位置的元素
public int get(int pos) {checkPos(pos);return this.elem[pos];}

 7、给 pos 位置的元素设为 value(更新)

//给 pos 位置的元素设为 value(更新) 
public void set(int pos, int value) {checkPos(pos);this.elem[pos] = value;}

8、删除第一次出现的关键字key

    //删除第一次出现的关键字keypublic void remove(int toRemove) {//获取被删除元素的下标int index = indexOf(toRemove);if(index == -1){System.out.println("没有这个数据");return;}for (int i = index; i < this.usedSized - 1; i++) {this.elem[i] = this.elem[i+1];}//引用类型//elem[usedSized-1] = null;this.usedSized--;}

9、获取顺序表长度 

// 获取顺序表长度public int size() {return this.usedSized;}

10、打印顺序表 

   // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的//实际上是遍历数组public void display() {for (int i = 0; i < this.usedSized; i++) {System.out.print(this.elem[i] + " ");}

 3、顺序表的使用

   1、创建顺序表

//创建了一个存放整数类型的顺序表并初始化了15个空间 
ArrayList<Integer> list = new ArrayList<>(15);

       ArrayList<Integer> list3 = new ArrayList<>();list3.add(10);//在第一次add分配大小为10的内存空间，扩容按照1.5倍的方式进行扩容,扩容的最大容量是int的最大值

2、顺序表中的常用方法

ArrayList<Integer> list3 = new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);list3.remove(2);//删除的是下标list3.remove(new Integer(2));//删除的是元素，且只删除第一个等于2的元素System.out.println(list3.get(0));//获取0下标的值list3.set(0,99);//修改0下标的值为99System.out.println(list3);list3.clear();//清空顺序表

3、截取顺序表及注意事项

        顺序表的截取后的对象指向的是原引用，也就是说能够通过两个对象（截取前、截取后）都能对引用中的值进行修改。

        理解了上述内容后，大家可以想想看下面代码的输出结果：

 ArrayList<Integer> list3 = new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);List<Integer> list = list3.subList(0,2);//[0,2)//在原List上截取，也就是说指向的是原List的引用，因此修改List的值同时也会修改List3的值list.set(0,188);System.out.println(list);//一般能够直接sout输出内容时，说明里面一定重写了toString方法System.out.println(list3);

        代码输出结果：[188,2]

                                 [188,2,3] 

4、Arraylist的遍历

1、

for (int i = 0; i < list3.size(); i++) {System.out.print(list3.get(i) +" ");}

2、

 for (Integer x:list3){System.out.print(x + " ");}

        以上两种方法与之前讲过的数组遍历大同小异，这里就不做过多赘述，下面是使用迭代器进行Arraylist的遍历。

3、

 Iterator<Integer> iterator = list3.iterator();while (iterator.hasNext()){System.out.print(iterator.next() + " ");}

4、

  ListIterator listIterator = list3.listIterator();while (listIterator.hasNext()){System.out.print(listIterator.next() + " ");}

        考虑到大家记忆困难，循环内的内容可以与之前提到的循环输入类比记忆，大家只需创建迭代器对象的过程即可。

5、从后往前遍历

 ListIterator listIterator2 = list3.listIterator(list3.size());while (listIterator2.hasPrevious()){System.out.print(listIterator2.previous() + " ");}System.out.println();