자료구조

ArrayList

ArrayList

LinkedList에 이어서 ArrayList를 공부한다.
ArrayList는 내부적으로 Array를 사용해서 만든 List 자료구조이다.
Array의 크기를 자동으로 늘려주기때문에
ArrayList는 Array처럼 고정된 크기를 신경쓰지 않아도 된다.
또한 GENERIC을 사용해서 참조형 변수를 요소로 받고
기본형 변수는 Autoboxing을 통해 받는다.

구현을 하려다가 코드확인으로..

java의 ArrayList와 생활코딩을 참고했다.
add, remove, get, size, indexOf만 간단하게 구현하려고 했는데
어쩌다 보니 java의 ArrayList를 따라쓰는 모양이 되어버렸다.
간단하게 구현하려고 했는데 뭔가를 빼기가 너무 애매해
리뷰가 됐다.

코드

[변수] []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//기본 list 크기
   private static final int DEFAULT_CAPACITY = 10;

   //새로 만들어 졌는지 확인하는데 사용
   private static final Object[] DEFAULT_EMPTY_ELEMENTDATA = {};
   
   //리스트의 최대 크기 지정
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
   
   //실제 값이 들어갈 배열
   transient Object[] elementData;
   
   // 리스크의 크기
   private int size;

먼저 변수들을 필요한 살펴보면
초기 생성에 필요한 상수 2개와 최대 크기 제한을 위한 상수 1개
(최대 크기가 Integer.MAX_VALUE - 8인 이유는 몇몇 JVM에서 Integer.MAX_VALUE가 OutOfMemoryError를 일으키기 때문이다.)
값이 들어갈 배열과 사이즈변수 2개 총 5개가 필요하다.
실제 자바의 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
//요소를 받아서 배열에 추가한다.
   public boolean add(E e) {
       ensureCapacityInternal(size + 1);
       elementData[size++] = e;
       return true;
   }
   
//배열에 자리가 있는지 확인한다
   private void ensureCapacityInternal(int minCapacity) {
       ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }

//배열의 크기를 계산한다 / 최초생성일 때는 기본크기를  필요 크기로 반환한다.
   private static int calculateCapacity(Object[] elementData, int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           return Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       return minCapacity;
   }

//배열의 크기가 필요 이하일 경우에 늘린다
   private void ensureExplicitCapacity(int minCapacity) {
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }
   
   //현재 배열의 크기가 필요 이하일 경우에 현재 배열의 크기 + 현재 배열의 크기/2를 한다.
//그리고 그래도 작으면 필요크기로 설정한다. / 이건 여기서 구현하지 않은 addAll에서 한번에 받을때 크기를 설정하기 위해서인 것 같다
//새로운 배열크기가 최대 배열크기를 넘으면 hugeCapacity를 호출한다.
   private void grow(int minCapacity) {
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       elementData = Arrays.copyOf(elementData, newCapacity);
   }
   
//최대 크기를 초과할 경우 Integer.MAX_VALUE로 값을 반환한다. 
   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0)
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }

처음 생성자로 생성하고 add함수를 호출하면 ensureCapacityInternal를 호출해 배열에 자리가 있는지 확인하고
calculateCapacity로 처음 생성했으면 최소 크기를 10으로 설정, ensureExplicitCapacity로 확장이 필요한 경우 확장한다.
grow 메서드에서 크기를 비교해 원래 크기의 2/1을 더해 새로운 배열을 만들어 복사하거나 그보다 공간이 더 필요하면
필요한 공간의 크기만큼 확장한다.

[메서드] []
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
	//사이즈 확인
public int size() {
      return size;
  }
   
//비었는지 확인
   public boolean isEmpty() {
       return size == 0;
   }
   
//인덱스를 받아서 삭제
   public E remove(int index) {
       rangeCheck(index);

       E oldValue = elementData(index);

       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null;

       return oldValue;
   }
   
//범위 확인
   private void rangeCheck(int index) {
       if (index >= size)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }
   
//에러 메세지를 생성
   private String outOfBoundsMsg(int index) {
       return "Index: "+index+", Size: "+size;
   }
   
//요소 반환
   @SuppressWarnings("unchecked") // element의 형태가 E라는 걸 보장할 수 없어 경고가 뜸
private E elementData(int index) {
       return (E) elementData[index];
   }
   
//요소 반환
   public E get(int index) {
       rangeCheck(index);

       return elementData(index);
   }
   
//위치를 반환
   public int indexOf(Object o) {
       if (o == null) {
           for (int i = 0; i < size; i++)
               if (elementData[i]==null)
                   return i;
       } else {
           for (int i = 0; i < size; i++)
               if (o.equals(elementData[i]))
                   return i;
       }
       return -1;
   }

remove는 인덱스를 받아서 범위 검사를 먼저 하고
배열을 새로 만들어서 인덱스 위치의 다음 요소들 부터 끝의 요소까지를
인덱스 위치에서부터 붙여넣어 덮어쓴다.

결과

간단하게 LinkedList의 구조를 확인해봤다.
너무 잘 만들어져 있어 구현하려던게 따라적기로 바뀌어버렸다.
하지만 한번 보고 실제로 코드를 쳐보니 이해에 도움이 되긴한다.
ArrayList와 LinkedList를 잘 구별해서 쓸 수 있을 것 같다.

끝!

공유하기