随机存储实现动态数组ArrayList

1、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
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
package com.yusian;
 
public interface List<E> {
 
	static final int ELEMENT_NOT_FOUND = -1;
	/**
	 * 获取数组长度
	 * @return 数组长度
	 */
	public int size();
 
	/**
	 * 是否为空
	 * @return true / false
	 */
	public boolean isEmpty();
 
	/**
	 * 是否包含某元素
	 * @param element
	 * @return true / false
	 */
	public boolean contains(E element);
 
	/**
	 * 添加元素,默认添加到末尾位置
	 * @param element
	 */
	public void add(E element);
 
	/**
	 * 获取元素
	 * @param index 索引
	 * @return 值
	 */
	public E get(int index);
 
	/**
	 * 替换元素
	 * @param index 索引
	 * @param element 元素
	 * @return 原元素内容
	 */
	public E set(int index, E element);
 
	/**
	 * 添加元素
	 * @param index 索引
	 * @param element 元素值
	 */
	public void add(int index, E element);
 
	/**
	 * 移除元素
	 * @return 返回被移除元素
	 */
	public E remove(int index);
 
	/**
	 * 获取元素索引
	 * @param element
	 * @return 索引
	 */
	public int indexOf(E element);
 
	/**
	 * 清除数组
	 */
	public void clear();
}

2、AbstractList

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
package com.yusian;
 
public abstract class AbstractList<E> implements List<E> {
 
	protected int size;
 
	/**
	 * 获取数组长度
	 * @return 数组长度
	 */
	public int size() {
		return size;
	}
 
	/**
	 * 是否为空
	 * @return true / false
	 */
	public boolean isEmpty() {
		return size == 0;
	}
 
	/**
	 * 是否包含某元素
	 * @param element
	 * @return true / false
	 */
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}
 
	/**
	 * 添加元素,默认添加到末尾位置
	 * @param element
	 */
	public void add(E element) {
		add(size, element);
	}
 
	/**
	 * 内部判断
	 * @param index
	 */
	protected void rangeCheck(int index) {
		if (index < 0 || index >= size) {
			outOfRange(index);
		}
	}
	protected void rangeCheckForAdd(int index) {
		if (index < 0 || index > size) {
			outOfRange(index);
		}
	}
	protected void outOfRange(int index) {
		throw new IndexOutOfBoundsException("超出范围,Index:"+index+", size:"+size);
	}
}

3、ArrayList

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
package com.yusian;
 
@SuppressWarnings("unchecked")
public class ArrayList<E> extends AbstractList<E>{
 
	private E[] elements;
	private static final int DEFAULT_CAPACITY = 10;
 
 
	public ArrayList() {
		this(DEFAULT_CAPACITY);
	}
 
	public ArrayList(int capacity) {
		if (capacity < DEFAULT_CAPACITY) {
			capacity = DEFAULT_CAPACITY;
		}
		elements = (E[])new Object[capacity];
	}
	/**
	 * 获取元素
	 * @param index 索引
	 * @return 值
	 */
	public E get(int index) {
		rangeCheck(index);
		return elements[index];
	}
 
	/**
	 * 替换元素
	 * @param index 索引
	 * @param element 元素
	 * @return 原元素内容
	 */
	public E set(int index, E element) {
		rangeCheck(index);
		E old = elements[index];
		elements[index] = element;
		return old;
	}
 
	/**
	 * 添加元素
	 * @param index 索引
	 * @param element 元素值
	 */
	public void add(int index, E element) {
		rangeCheckForAdd(index);
		ensureCapcity(size + 1);
		for (int i = size; i >= index; i--) {
			// 此处有可能超出elements的有效范围
			elements[i+1] = elements[i];
		}
		elements[index] = element;
		size++;
	}
 
	/**
	 * 移除元素
	 * @return 返回被移除元素
	 */
	public E remove(int index) {
		rangeCheck(index);
		// 0 1 2 3 4 5 6 7
		// 1 2 3 4 5 6 7 8
		E del = elements[index];
		for (int i = index; i < size - 1; i++) {
			elements[i] = elements[i+1];
		}
		elements[--size] = null;
		return del;
	}
 
	/**
	 * 获取元素索引
	 * @param element
	 * @return 索引
	 */
	public int indexOf(E element) {
		if (element == null) {
			for (int i = 0; i < size; i++) {
				if (elements[i] == null) return i;
			}
		} else {
			for (int i = 0; i < size; i++) {
				if (element.equals(elements[i])) return i;
				// if (element == elements[i]) return i;
			}
		}
		return ELEMENT_NOT_FOUND;
	}
 
	/**
	 * 清除数组
	 */
	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;
	}
 
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		StringBuilder str = new StringBuilder();
		str.append(super.toString()).append(" size = ").append(size).append(", [");
		for (int i = 0; i < size; i++) {
			if (i > 0) {
				str.append(", ");
			}
			str.append(elements[i]);
		}
		str.append("]");
		return str.toString();
	}
 
	/**
	 * 私有方法
	 */
	private void ensureCapcity(int capcity) {
		if (elements.length > capcity) return;
		int oldCapcity = elements.length;
		// 扩容原来的约1.5倍
		int newCapcity = oldCapcity + (oldCapcity >> 1);
		E[] newElements = (E[]) new Object[newCapcity];  
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
		System.out.println("容量:" + oldCapcity + " --> " + newCapcity);
	}
}

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package com.yusian;
 
public class Main {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(5);
		list.add(1, 0);
		System.out.println(list);
	}
 
}

发表评论