강의노트 3강에서는 List 자료구조를 공부하고자 합니다.
List 중 배열기반인 ArrayList에 대하여 알아보겠습니다.
1) 배열 리스트(ArrayList)
ArrayList는 List구조를 배열로 표현한 구조입니다.
2강에서 Stack과 Queue를 공부하면서, Array 기반으로 만드는 연습을 해보았기에 익숙하실 것 같습니다 :)
size가 8인 arrayList입니다.
arrayList를 포함한 List의 특징은 배열의 순서가 있다는 점입니다.
"몇 번째 순서의 List에 값을 저장하라."
등의 명령이 가능합니다.
Top에만 object를 추가할 수 있는 스텍과 큐와는 다른점입니다.
arrayList의 size가 너무 적다면 저장에 불편하고, 너무 크다면 불필요한 메모리가 잡아먹히기 때문에
arrayList의 size를 처음에 무슨값으로 선언하는지 고민해보아야합니다.
(이 문제는 DynamicSize ArrayList를 구현하면서 해결할 수 있습니다. 밑에서 더 알아보겠습니다.)
2) ArrayList Operation
- object get(integer i) : i번째 배열의 값을 불러옵니다.
- object set(integer i, obeject e) : i번째 배열의 값을 e로 바꿉니다.
- void add(integer i, object e) : i번째 배열에 값 e를 추가합니다.
- object remove(integer i) : i번째 배열의 값을 제거합니다.
- integer size() : arrayList의 size를 불러옵니다.
- boolean isEmpty() : arrayList가 비워져있는 상태인지 판단합니다.
!) ArrayList Opearation Example
| Operation | Output | In_ArrayList |
| add(0, 3) | - | (3) |
| add(0, 5) | - | (5, 3) |
| get(1) | 3 | (5, 3) |
| add(2, 2) | - | (5, 3, 2) |
| get(3) | "error" | (5, 3, 2) |
| remove(1) | 3 | (5, 2) |
| set(0, 4) | - | (4, 2) |
| remove(1) | 2 | (4) |
| remove(0) | 4 | - |
3) ArrayList 구현
arrayList 역시 자바에서 기본적으로 제공해주지만, 연습이니 직접 구현해보도록 하겠습니다.
arrayList를 구현할 때는 add와 remove를 신경써서 코딩하여야 합니다.
size가 8인 arrayLisy에 3까지 object가 채워져 있습니다.
만약 이럴 때 세번째 index(2)에 새로운 값을 추가해주고 싶으면 어떻게 해야 할까요?
이렇게 추가해주고 싶은 index보다 큰 index의 값들의 위치를 우측으로(++) 옮겨줍니다.
기존의 3번째 index의 값은 4번째 index에 저장되었고,
2번째 index의 값은 3번째 index에 저장되어 2번째 index에 아무런 값이 저장되어 있지 않게 되었습니다.
이렇게 2번째 인덱스에 새로운 값이 추가되었습니다.
remove도 마찬가지로 제거하고자 하는 index보다 큰 index에 위치한 data를 좌로(--) 옮겨주면됩니다.
그렇다면 이제 구현해보겠습니다!
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
|
public class ArrayList {
private Object[] data;
private int index;
private int size;
public ArrayList(int size) {
this.data = new Object[size];
this.index = 0;
this.size = size;
}
public Object get(int i) {
if( i > this.index) {
System.out.println("Invalid");
return null;
}
else if( this.isEmpty ) {
System.out.println("Array is Empty!");
return null;
}
else {
return this.data[i];
}
}
public Object set(int i, Object e) {
if( i > this.index) {
System.out.println("Invalid");
return null;
}
else {
Object returnO = this.data[i];
this.data[i] = e;
return returnO;
}
}
public void add(int i, Object e) {
if( i > this.index) {
System.out.println("Invalid");
return null;
}
else {
for( int k = this.index; k>i; k--) {
this.data[k] = this.data[k-1]'
}
this.data[i] = e;
this.index++;
}
}
public Object remove(int i) {
Object returnO = this.data[i];
for( int i = j; j < this.index-1; j++) {
this.data[j] = this.data[j+1];
}
this.index--;
return returnO;
}
public int size() {
reuturn this.index;
}
public boolean isEmpty() {
return ( this.index == 0 );
}
|
cs |
위 코드의 문제점이 무엇일까요?
만약 arratList가 다 차있는 상태에서 add를 시도하게된다면,
제일 마지막 index에 저장된 값이 사라져버립니다.
arrayList가 다 차있는 상태에서 add를 시도하지 못하게 하는 방법도 있겠지만,
arrayList의 size를 늘려주는 방법으로 이 문제점을 극복해보도록 하겠습니다.
만약, 이 방법을 채택한다면 arrayList의 크기를 자동으로 늘려주기 때문에,
초기에 size를 설정하는 걱정을 덜 수도 있기 때문입니다.
DynamicSize ArrayList
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public void add(int i, Object e) {
if( i > this.index) {
System.out.println("Invalid");
return null;
}
else if ( this.index == this.data.length ) {
Object[] old = this.data;
int newSize = this.size*2;
this.data = new Object[newSize];
this.size = newSize;
for(int j = 0; j < this.index; j++ ) {
this.data[j] = old[j];
}
}
for( int k = this.index; k>i; k--) {
this.data[k] = this.data[k-1]'
}
this.data[i] = e;
this.index++;
}
}
|
cs |
이렇게 arrayList 공부를 마쳤습니다.
많은 도움이 되었으면 좋겠습니다 :)
최근댓글