1+ package com .sanmubird .basicDataStructure ;
2+
3+ import java .util .Arrays ;
4+
5+ public class ArrayList implements List {
6+
7+ /** ArrayList 是一个类，一个类就会有对象，属性，构造方法，方法
8+ * ArrayList 是基于数组来实现List接口； 那么它的元素就会有 存储在数组中的元素， 和ArrayList的长度
9+ * 这个地方需要区分size= ArrayList.size() 和 length = Array.length ；
10+ * size 是 已经占用的长度；
11+ * length 是数组的长度； length 》= size 当，size > length 时，数组要动态扩容；
12+ * */
13+
14+ // 数组默认的长度
15+ private static final int DEFAULT_SIZE = 10 ;
16+
17+ // ArrayList的大小
18+ private int size ;
19+
20+ // 数组中存储的元素
21+ private Object [] elementData = null ;
22+
23+ private int count ;
24+
25+ // ArrayList 的构造方法 通过构造方法 可以得到这个类的对象
26+ // 有参构造方法
27+ public ArrayList (int i ){
28+ if (i <= 0 ){
29+ throw new RuntimeException ("数组的长度不能小于等于0" );
30+ }else {
31+ this .elementData = new Object [i ];
32+ this .size = 0 ; // 集合ArrayList的大小；
33+ }
34+ }
35+ // 无参构造方法
36+ public ArrayList (){
37+ this (DEFAULT_SIZE ); // this 会调用本类中 相同参数（相同的参数个数和参数类型）的构造方法；
38+ }
39+
40+ /** ArrayList 其他方法分析
41+ * 目标方法：
42+ * size(); Array的length就是ArrayList的大小
43+ * get(int index); Array的【index-1】就是 ArrayList的第index位元素
44+ * add(Object o) ; 这个方法是在数组的末尾顺序添加一个元素； 找到数组的长度size，将array【size-1】= Object
45+ * add(int index , Object o); 这个方法是在数组的指定位置添加一个元素；找到index位，将index位起往后挪一位，并将array【index】=Object
46+ * remove(int index); 这个方法是 删除指定位上的元素，直接将这个位至最后的元素往前挪移一位。
47+ *
48+ * 工具方法：
49+ * argumentCheck(int index); 判断输入的参数是否合法;比如传入的参数不能比数组长度大，或者不能为负数等
50+ * ensureCapacity(); 判断当前数组的长度是否足够大，能再容纳下一个元素。
51+ *
52+ * */
53+
54+
55+ // 对传入的参数进行验证是否合法 如果输入的参数不合法 就抛出异常
56+ public void argumentCheck (int index ){
57+ if (index >= size || index < 0 ){ // 此处我觉得需要 ‘=’ 因为 index 我觉得是下标
58+ throw new IndexOutOfBoundsException ("插入的下标是:" +index +"，但ArrayLsit的长度是：" +size );
59+ }
60+ }
61+
62+ // 判断是否数组是否溢出的方法 如果数组现在的长度小于所需的最小长度，就需要对数组进行扩容
63+ public void ensureCapacity (int minCapacity ){
64+ int length = elementData .length ; // 得出当前数组的长度
65+ if (minCapacity > length ){
66+ int newCapacity = length * 3 / 2 + 1 ; //你是否对此有疑问？得出的结果会不会是小数？ 答案是不会的，java中算术运算符“/”；两个int类型相除，结果一定是int类型
67+ if (minCapacity > newCapacity ){
68+ newCapacity = minCapacity ;
69+ }
70+ count ++;
71+ System .out .println ("扩容" +count +"次" );
72+ elementData = Arrays .copyOf (elementData , newCapacity );//此处为什么用Arrays.copyOf()而不用System.arraycopy()?
73+ // Arrays.copyOf(): 不仅仅copy数组中的元素，还会创建一个新的数组来存放copy的对象
74+ // System.arraycopy():仅仅是copy数组中的元素，不会新建一个数组对象,也不会改变原有的数组长度。
75+ // 在原有数组长度不够的情况下，只能选择新建一个数组，并将原有的数组复制到新数组的办法来解决。
76+ }
77+ }
78+
79+ // 得到ArrayList 大小的方法 ； 此处的size 不是Array的length,而是ArrayList中元素的个数
80+ public int size (){
81+ return size ;
82+ }
83+
84+ // 传入下标得到元素
85+ public Object get (int index ){
86+ argumentCheck (index ); //需要判断传入的参数是否合法；
87+ return elementData [index ];
88+ }
89+
90+ // 按顺序在数字尾部添加元素
91+ public void add (Object o ){
92+ ensureCapacity (size +1 ); // 判断是否会溢出
93+ elementData [size ++] = o ; //此处使用 size++ 的好处：elementData[size+1];size++;
94+ }
95+
96+ public void add (int index , Object o ){ //这个地方需要搞清楚index的含义：index在此处是下标的意思
97+ argumentCheck (index ); //判断输入的下标是否合法 --->
98+ // 刚开始的时候 ； 我觉得这个地方不需要加这个判断，因为ArrayList是动态增长的；
99+ // 我还需要想明白这个问题；
100+ ensureCapacity (size +1 ); // 判断是否会溢出
101+ int moveLength = size - (index + 1 ) + 1 ; // 此处index是下标；下标是从0开始计算的；所以第n位的下标就是（n-1）；所以，n = index + 1
102+ // 此处的 +1 刚开始没想明白，后来组长给举了个例子，1-3 有三个数，但不是通过3-1=2 算出来的
103+ System .arraycopy (elementData , index , elementData , index +1 , moveLength );
104+ elementData [index ] = o ;
105+ size ++;
106+ }
107+
108+ public Object remove (int index ){
109+ argumentCheck (index ); //判断输入的下标是否合法
110+ Object o = elementData [index ];
111+ System .arraycopy (elementData , index , elementData , index -1 , size -index );
112+ elementData [size ] = null ;
113+ size --;
114+ return o ;
115+ }
116+
117+ public Iterator iterator (){
118+ return new Iterator (){
119+ private int index = 0 ;
120+
121+ @ Override
122+ public Object next (){
123+ return elementData [index ++];
124+ }
125+ @ Override
126+ public boolean hasNext () {
127+ return index < size ;
128+ }
129+ };
130+ }
131+
132+ public static void main (String [] args ){
133+ ArrayList al = new ArrayList ();
134+ al .add (1 );
135+ al .add (2 );
136+ al .add (4 );
137+ al .add (5 );
138+ al .add (6 );
139+ al .add (7 );
140+ al .add (2 ,3 );
141+ al .add (8 );
142+ al .add (9 );
143+ al .add (10 );
144+ al .add (11 );
145+ al .add (13 );
146+ al .add (9 ,12 );
147+ al .add (14 );
148+ al .add (15 );
149+ al .remove (9 );
150+ for (int i = 0 ; i < al .size () ; i ++ ){
151+ System .out .println (al .get (i ));
152+ }
153+ System .out .println ("al的size是" +al .size ());
154+ System .out .println (al .get (15 ));
155+ }
156+ }
0 commit comments