forked from rangken/AlgorithmStudy
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathArrayList.java
More file actions
154 lines (138 loc) · 4.09 KB
/
Copy pathArrayList.java
File metadata and controls
154 lines (138 loc) · 4.09 KB
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
public class ArrayList<E> implements List<E>{
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity){
super();
this.elementData = new Object[initialCapacity];
}
public ArrayList(){
super();
this.elementData = EMPTY_ELEMENTDATA;
}
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 최대 array 크기
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity){
int oldCapacity = elementData.length;
// 얼레 크기에 2배를 늘려줌
int newCapacity = oldCapacity + (oldCapacity >> 1);
if(newCapacity-minCapacity < 0){
newCapacity = minCapacity;
}
// 최대 ARRAY 크기를 넘음
if(newCapacity-MAX_ARRAY_SIZE > 0){
newCapacity = MAX_ARRAY_SIZE;
}
// 크기를 늘려서 Array copy
// 그냥 java.util 에 Arrays 클래스 사용
elementData = java.util.Arrays.copyOf(elementData,newCapacity);
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
return elementData(index);
}
public boolean add(E e){
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
public E remove(int index) {
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o){
if (o == null){
for(int i=0; i < size; i++){
if(elementData[i] == null){
fastRemove(i);
return true;
}
}
}else{
for(int i=0; i < size; i++){
// LinkedList 에서는 hashCode비교(==) 하지만
// ArrayList 에서는 내용이 같은지(equals) 를 한다.
if(o.equals(elementData[i])){
fastRemove(i);
return true;
}
}
}
return false;
}
private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0){
// 원본,읽어올부분,복사할대상,카피할 위치,얼마만큼 읽어올지
// elementData를 index+1 부터 numMoved 만큼 읽어서 index 로 elementData 에 카피
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
}
public Iterator<E> iterator(){
return new ListItr(0);
}
private class ListItr implements ListIterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
public ListItr(int index){
cursor = index;
}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
int i = cursor;
if (i >= size)
{
}
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
{
}
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
{
}
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
}
}
}