关于ArrayList的梳理_arraylist 顺序

  ArrayList是一个顺序存储的List（表），而List是一种更具体的Collection（集合），所以

• 1 它具有Collection的基础功能，比如增加，删除，返回元素总数，清空等等。
• 2 同时Collection应该可以实现对所有元素的增强的for循环，即for( Type element : collection ) { … }，即有某种方式可以实现对集合内所有元素的迭代。
• 3 List相对于Collection的本质区别在于，表相对于集合，元素具有顺序，即具有位置索引index的概念，因此至少有新的功能：在给定的某位置上，获得、改变、删除、增加元素等。
• 4 ArrayList相对于List的本质区别在于，ArrayList是一种具体的实现方式（顺序存储），是一个 类；而List、Collection等是一种不包含具体实现的概念，是抽象的规范，是规定你有什么、能做什么，但不管你具体怎么实现的 接口。

  上面4点是主要逻辑，后面是细节补充：

• 5 集合的元素可以是任意类型的，所以ArrayList是泛型类ArrayList<WhateverTypeYouWant>，List等接口是泛型接口List<T>等。泛型是啥呢，泛型就是泛指某种类型，即这里有某种AnyType的类型，我要具体用时再指定。后文中定义时统一用<T>（表示Type）来写代码，其他地方常看到<AnyType>表示任意类型、<E>表示element，实际上你统一用<Whatever>也行。因为，写出的泛型接口、泛型类具体应用时自然就会具体化（被称为参数化），如private ArrayList<String> str = new ArrayList<>();中的String。
• 6 增强的for循环是编译器自动对代码进行了改写，要求集合扩展或实现了Iterable接口（因此有一个iterator方法返回一个实现Iterator接口的类，Iterator里面的hasnext()和next()就可以完成迭代，即改写增强for循环），有点绕，得自己去理解然后在回来看这句话。
• 7 从小到大的接口顺序是，Iterator<T> ~（非继承） Iterable<T> → Collection<T> → List<T> （→ArrayList<T>），即最后泛型类ArrayList<T>实现了List接口。
• 8 顺序存储的核心逻辑就是，插入的话依次往后挪，删除依次往前挪，就这么简单。
• 9 ArrayList类的实现用到了内部类。当声明内部类时，编译器会自动添加对外部类对象的一个隐式引用，比如外部类名是Outer，隐式引用就是Outer.this。这个隐式引用就是内部类与嵌套类的差异，内部类应用在每一个内部类对象都恰好与外部类对象的一个实例相关联的情况，在没有外部类对象和其进行关联时，内部类的对象永远不可能存在。而嵌套类是一个放在外部类内部但又独立的类，即虽然不存在可见性问题，但是引用外部类的成员时，需要增加一个外部类类型的成员变量，通过这个成员来引用外部类的成员。
• 10 内部类ArrayListIterator，是Collection接口的父接口Iterable的具体（但不是直接）实现，Collection要求可以用某种方式实现对集合内所有元素的迭代（但不要求是List那样给定序号的形式，即List是更具体的一种抽象），因此Collection要有个抽象的用于说明迭代过程和记录迭代位置的 迭代器，它是一个接口，ArrayListIterator就是这个接口在ArrayList中的具体实现类。Iterable接口就是要求有个函数能返回得到这个迭代器的对象，通过对象的成员变量记录迭代位置，成员函数给出迭代过程。

  下面我将按自己的理解复现上面的流程，不过接口定义远没有官方的完善，只择取了部分方法；同时为和系统库的接口、类相区别，命名前加My。
  首先是接口：

public interface MyIterator<T> {
	boolean hasNext();
	T next();
	void remove();
}
1
2
3
4
5

public interface MyIterable<T> {
	MyIterator<T> myIterator();
}
1
2
3

public interface MyCollection<T> extends MyIterable<T> {	
	int size();
	boolean isEmpty();
	void clear();
	boolean contain();
	boolean add(T x);
	boolean remove(T x);

	MyIterator<T> myIterator();
}
1
2
3
4
5
6
7
8
9
10

public interface MyList<T> extends MyCollection<T> {
	int size();
	boolean isEmpty();
	void clear();
	boolean contain();
	boolean add(T x);
	boolean remove(T x);
	
	T get(int idx);
	T set(int idx, T newVal);
	int indexOf(T x);
	void add(int idx, T x);
	void remove(int idx);

	MyIterator<T> myIterator();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

  注意，在写出上面的 MyList接口 后，我们将做出做出如下顺序调整：

public interface MyList<T> extends MyCollection<T> {
	int size();
	boolean isEmpty();
	void clear();
	boolean contain();
	boolean add(T x);
	void add(int idx, T x); // overload
	boolean remove(T x);
	void remove(int idx); // overload
	
	T get(int idx);
	int indexOf(T x);
	T set(int idx, T newVal);

	MyIterator<T> myIterator();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 
  个人根据逻辑和阅读顺序，初步整理了一份个人的 代码书写习惯，如下：

public class A extends B implements C {
	Static变量
	嵌套类 //即Static内部类
	成员变量
	构造方法
	
	public的接口方法
	接口方法中需要用到的private方法  //放在第一次用到的public方法后
	接口方法中需要用到内部类的方法和相应的内部类 //放在最后
		
	public的新方法
	新方法中需要用到的private方法  //放在第一次用到的public方法后
	新方法中需要用到内部类的方法和相应的内部类 //放在最后
	} // of class A
1
2
3
4
5
6
7
8
9
10
11
12
13
14

  这样的代码不一定最优，因为前面的方法（如override）可能用到后面的方法（该类特有的新方法）来实现。private方法直接写在第一次用到该私有方法的public方法后面。
  在设计接口时，则是简单方法在前，复杂的涉及到内部类（返回值、参数也是接口）的方法放最后。在此基础上，再按先后顺序排布，若有新方法是对继承方法的重载则提前。
 
  然后给出MyArrayList类的框架：

public class MyArrayList<T> implements MyList<T> {
	private static final int DEFAULT_CAPACITY = 10;
	
	private int theSize;
	private T[] theItems;

	public MyArrayList() {}
	public MyArrayList(T[] paraArray) {}
	
	public int size() {}
	public boolean isEmpty() {}
	public void clear() {}
	public boolean contain(T x) {}
	public boolean add(T x) {}
	public void add(int idx, T x) {}
	public boolean remove(T x) {}
	public T remove(int idx) {}
	
	public T get(int idx) {}
	public int get(T paraValue) {}
	public T set(int idx, T newVal) {}
	public MyIterator<T> myIterator() {}

	private void doClear() {}
	private class ArrayListIterator implements MyIterator<T> {
		private int current = 0;
		
		public boolean hasNext() {}	
		public T next() {}
		public void remove() {}
	}

	// Ensure a large enough capacity.
	public void ensureCapacity(int newCapacity) {}
	// Trim theItems.length to {@size()}.
	public void trimToSize() {}
	public String toString() {}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38

  我个人将写的接口放在myList项目的myAPI包中，后面的MyArrayList和MyLinkedList都属于myList项目各自独立的包，这样它们都可以用这些接口。
  关于toString()方法，补充一点细节：
  下面给出2种可行的方法，一种利用数组的get(int)，一种利用迭代器的next()：
1:

	public String toString() {
		String s = "empty.";
		if (!isEmpty()) {
			s = "{ ";
			for (int i = 0; i < theSize - 1; i++) {
				s += get(i) + ", ";
			} // of for i
			s += get(theSize - 1) + " }";
		} // of if

		return s;
	} // of toString
1
2
3
4
5
6
7
8
9
10
11
12

2:

	public String toString() {
		ArrayListIterator itr = (ArrayListIterator) this.myIterator();
		String s = "empty.";
		if (!isEmpty()) {
			s = "{ ";
			while (itr.hasNext()) {
				s += itr.next() + " ";
			} // of while
			s += "}";
		} // of if

		return s;
	} // of toString

1
2
3
4
5
6
7
8
9
10
11
12
13
14

  这里两种都可以用，因为数组的get(int)和迭代器的next()的复杂度都是$O(1)$。但是第一种形式分明更容易理解，还把第二种写出来，是因为：
  一方面，任何的迭代过程，比如这里对集合元素的for循环，本质都是一个while循环，while( 有下一个的条件 ) { 对下一个的操作 }，for循环中是借助数组的角标 i 直观的表示位置，而迭代器是自己抽象了位置的概念current，for循环的条件被迭代器抽象成boolean hasNext()方法，迭代器的next()方法有2个作用，每次next()后：1是返回当前current位置对应的值，2是current++。因此用迭代器的思想更本质地理解了整个过程。
  另一方面，在后面的LinkedList中，get(int)方法的消耗是$O(N)$的，不再是$O(1)$，用for循环依然能做，但是消耗将会大大增加，而迭代器的next()则不会。

  最后对上述框架进行完善（将省略对成员的注释和一些错误检测），并进行相关测试：

  2021/7/21再次进行修订，使用了Java原接口Iterator，没再使用自己的接口，其他不变，这样可以用编译器实现foreach循环，而不需要自己写一个迭代器变量加while循环来改写每次的for each循环。

package myList;

import java.util.Iterator;

/**
 * @author CatInCoffee.
 * @version 1.2 Revised on 2021/7/21.
 */

public class MyArrayList<T> implements Iterable<T>{

	private static final int DEFAULT_CAPACITY = 10;

	private int theSize;
	private T[] theItems;

	// *****************************************************************************************

	public MyArrayList() {
		clear();
	} // Of the first constructor

	public void clear() {
		theSize = 0;
		ensureCapacity(DEFAULT_CAPACITY);
	} // of clear()

	// O(N)
	public void ensureCapacity(int newCapacity) {
		if (newCapacity < theSize) {
			return;
		} // if
		T[] old = theItems;
		theItems = (T[]) new Object[newCapacity];
		for (int i = 0; i < size(); i++) {
			theItems[i] = old[i];
		} // of for i
	} // of ensureCapacity(int)

	// O(N)
	public MyArrayList(T[] paraArray) {
		theSize = paraArray.length;
		theItems = (T[]) (new Object[theSize * 2 + 1]);
		ensureCapacity(DEFAULT_CAPACITY);

		System.out.println("The length of array used to store data is " + theItems.length + "\n");

		for (int i = 0; i < paraArray.length; i++) {
			theItems[i] = paraArray[i];
		} // Of for i
	} // Of the second constructor

	// *****************************************************************************************

	public int size() {
		return theSize;
	} // of size()

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

	// O(N)
	public boolean contain(T x) {
		return indexOf(x) >= 0;
	} // of contain(T)

	// *****************************************************************************************

	// O(1)
	public boolean add(T x) {
		add(size(), x);
		return true;
	} // of add(T)

	// O(N)
	public void add(int idx, T x) {
		if (theItems.length == size()) {
			ensureCapacity(size() * 2 + 1);
		} // of if
		for (int i = theSize; i > idx; i--) {
			theItems[i] = theItems[i - 1];
		} // of for i
		theItems[idx] = x;

		theSize++;
	} // of add(int, T)

	// O(N) ,因为indexOf是从前往后至idx, 而remove(idx)是从idx往后,相当于1次遍历
	public boolean remove(T paraValue) {
		int idx = indexOf(paraValue);

		if (idx == -1) {
			return false;
		} // of if

		remove(idx);
		return true;
	} // of remove(T)

	// O(N)
	public T remove(int idx) {
		T removedItem = theItems[idx];
		for (int i = idx; i < size() - 1; i++) {
			theItems[i] = theItems[i + 1];
		} // of for i

		theSize--;
		return removedItem;
	} // of remove(int idx)

	// *****************************************************************************************

	// O(1)
	public T get(int idx) {
		if (idx < 0 || idx >= size()) {
			throw new ArrayIndexOutOfBoundsException();
		} // of if
		return theItems[idx];
	} // of get(int)

	/**
	 * Return the index of the first occurrence of the specified element in this
	 * list, or -1 if this list does not contain the element. More formally, returns
	 * the lowest index, or -1 if there is no such index. O(N)
	 *
	 * @param paraValue the element to search for
	 * @return the index of the first occurrence of the specified element in this
	 *         list, or -1 if this list does not contain the element
	 */
	public int indexOf(T paraValue) {
		int tempPosition = -1;

		if (paraValue == null) {
			for (int i = 0; i < theSize; i++) {
				if (theItems[i] == null) {
					tempPosition = i;
					break;
				} // Of if
			} // Of for i
		} else {
			for (int i = 0; i < theSize; i++) {
				if (theItems[i].equals(paraValue)) { // ==比较对象地址是否相同，equals常自定义，一般为比较值
					tempPosition = i;
					break;
				} // Of if
			} // Of for i
		} // of if-else

		return tempPosition;
	} // of indexOf(T)

	// O(1)
	public T set(int idx, T newVal) {
		if (idx < 0 || idx >= size()) {
			throw new ArrayIndexOutOfBoundsException();
		} // of if
		T old = theItems[idx];
		theItems[idx] = newVal;
		return old;
	} // of set(int, T)

	// *****************************************************************************************

	public Iterator<T> iterator() {
		return new ArrayListIterator();
	} // of myIterator()

	// The time complexities of the methods in the Iterator are all O(1).
	private class ArrayListIterator implements Iterator<T> {
		private int indexOfNext = 0;

		public boolean hasNext() {
			return indexOfNext < size();
		} // of hasNext()

		public T next() {
			if (!hasNext()) {
				throw new java.util.NoSuchElementException();
			} // of if
			return theItems[indexOfNext++];
		} // 0f next()

		public void remove() {
			MyArrayList.this.remove(--indexOfNext);
		} // 0f remove()
	} // of class ArrayListIterator

	// *****************************************************************************************

	// Trim theItems.length to {@size()}.
	public void trimToSize() {
		ensureCapacity(size());
	}// of trimToSize()

	public String toString() {
		String s = "empty.";
		if (!isEmpty()) {
			s = "{ ";
			for (int i = 0; i < theSize - 1; i++) {
				s += get(i) + ", ";
			} // of for i
			s += get(theSize - 1) + " }";
		} // of if

//		ArrayListIterator itr = (ArrayListIterator) this.myIterator();
//		String s = "empty.";
//		if (!isEmpty()) {
//			s = "{ ";
//			while (itr.hasNext()) {
//				s += itr.next() + " ";
//			} // of while
//			s += "}";
//		} // of if

		return s;
	}// of toString()

	// *****************************************************************************************

	public static void main(String[] args) {
		String[] tempArray = { "1", "2", "3", "4", "5", "6", "7", "f", "c", "d", "i" };
		System.out.println("tempArray.length = " + tempArray.length);
		MyArrayList<String> testArrayList = new MyArrayList<>(tempArray);
		System.out.println("After being initialized, the list is: " + testArrayList.toString());

		String tempValue = "i";
		System.out.println(
				"The judgement that the list contains " + tempValue + " is :" + testArrayList.contain(tempValue));
		int tempPosition = testArrayList.indexOf(tempValue);
		System.out.println("The position of " + tempValue + " is " + tempPosition);

		tempValue = "e";
		System.out.println(
				"The judgement that the list contains " + tempValue + " is :" + testArrayList.contain(tempValue));
		tempPosition = testArrayList.indexOf(tempValue);
		System.out.println("The position of " + tempValue + " is " + tempPosition + "\n");

		tempPosition = 1;
		tempValue = "g";
		testArrayList.add(tempPosition, tempValue);
		System.out.println("After adding " + tempValue + " to position " + tempPosition + ", the list is: "
				+ testArrayList.toString());

		testArrayList.add("j");
		System.out.println("After adding j to the end, the list is: " + testArrayList.toString());

		tempPosition = 2;
		tempValue = "h";
		testArrayList.set(tempPosition, tempValue);
		System.out.println("After seting " + tempValue + " at position " + tempPosition + ", the list is: "
				+ testArrayList.toString());

		tempPosition = 5;
		testArrayList.remove(tempPosition);
		System.out.println("After removing data at position " + tempPosition + ", the list is: "
				+ testArrayList.toString() + "\n");

		tempValue = "d";
		System.out.println("removing value " + tempValue + " could be : " + testArrayList.remove(tempValue)
				+ ", and the list is: " + testArrayList.toString());

		tempValue = "a";
		System.out.println("Removing value " + tempValue + " could be : " + testArrayList.remove(tempValue)
				+ ", and the list is: " + testArrayList.toString());

		testArrayList.clear();
		System.out.println("After the clear() method, the list is: " + testArrayList);
	}// of main

}// of class MyArrayList<T>
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271

结果：

tempArray.length = 11
The length of array used to store data is 23

After being initialized, the list is: { 1, 2, 3, 4, 5, 6, 7, f, c, d, i }
The judgement that the list contains i is :true
The position of i is 10
The judgement that the list contains e is :false
The position of e is -1

After adding g to position 1, the list is: { 1, g, 2, 3, 4, 5, 6, 7, f, c, d, i }
After adding j to the end, the list is: { 1, g, 2, 3, 4, 5, 6, 7, f, c, d, i, j }
After seting h at position 2, the list is: { 1, g, h, 3, 4, 5, 6, 7, f, c, d, i, j }
After removing data at position 5, the list is: { 1, g, h, 3, 4, 6, 7, f, c, d, i, j }

removing value d could be : true, and the list is: { 1, g, h, 3, 4, 6, 7, f, c, i, j }
Removing value a could be : false, and the list is: { 1, g, h, 3, 4, 6, 7, f, c, i, j }
After the clear() method, the list is: empty.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

PS：if (condition) 后不加 {} 的第一条语句是 if 的判断执行语句，此后的不再与 if 相关，如

 if (false)
	System.out.print("1");
System.out.print("2");
1
2
3

等同于

if (false) System.out.print("1"); 
System.out.print("2");
1
2

和

if (false) {
	System.out.print("1"); 
}
System.out.print("2");
1
2
3
4

  出于后面修改代码的安全考虑，还是加上 {} ，免得后面把相同缩减的后续语句当成是 if 的执行语句块。