Java List - 직접 구현해보기 3

다음으로 직접 만든 배열에 추가 기능을 만들어주도록 한다.

• add(Index, Data)
  • add(Data) 메소드에서 오버로딩한다.
  • Index 위치한 배열의 데이터를 추가하는 작업이다.
• remove(Index)
  • Index 위치한 배열의 데이터를 삭제한다.

기존의 add() 메소드는 배열 마지막에 데이터 추가이므로 기존 데이터는 이동하지 않고 유지하였다. 그렇지만 추가 기능으로 배열 중간 또는 처음 배열 인덱스에 기존 데이터를 위치를 한 칸씩 움직이고 데이터를 추가하는 작업을 진행할 것이다. 구현이 복잡할 수 있다.

삭제도 마찬가지로 마지막 데이터를 삭제하고 기존 데이터를 이동하지 않았다. 중간에 있는 데이터 삭제 시 빈자리를 채우도록 기존 데이터 한 칸씩 왼쪽으로 이동한다.

add(data) 기존 로직

1. add("a")
 "a"
  ↓
+---+---+---+---+---+
| a | ? | ? | ? | ? |
+---+---+---+---+---+
size = 1, capacity = 5

2. add("b")
     "b"
      ↓
+---+---+---+---+---+
| a | b | ? | ? | ? |
+---+---+---+---+---+
size = 2, capacity = 5

3. add("c")
         "c"
          ↓
+---+---+---+---+---+
| a | b | c | ? | ? |
+---+---+---+---+---+
size = 3, capacity = 5

• add() 사용해 데이터 추가 시 size 기준으로 마지막 부분만 이어서 추가하였다.
• 기존 데이터를 옮기지 않으므로 O(1) 속도로 추가된다.

신규 add, remove 동작 과정

신규 기능으로 add(index, data), remove(index) 동작 과정을 살펴보자

elementData 배열 상태

+---+---+---+---+---+
| a | b | c | ? | ? |
+---+---+---+---+---+
size = 3, capacity = 5

먼저 배열 데이터는 다음과 같이 size 3개에 a,b,c 각각 들어있는 상태로 확인해보자.

add() - 배열 마지막에 데이터 추가

1. add(3, "d")
             "d"
              ↓
+---+---+---+---+---+
| a | b | c | ? | ? |
+---+---+---+---+---+
size = 4, capacity = 5

• index(3, "d") 사용해 원하는 위치로 데이터 추가하였다.
• 추가한 인덱스 우측에는 아무것도 없으므로 기존 데이터 옮기는 작업이 없다.
• O(1) 속도로 유지하고 있다.

add() - 배열 맨 앞에 데이터 추가

1. add(0, "e")
 "e"
  ↓
+---+---+---+---+---+
| e | a | b | c | d |
+---+---+---+---+---+
size = 5, capacity = 5

• add(0, "e") 사용해 원하는 위치로 데이터 추가하였다.
• 먼저 데이터 손실이 발생되지 않도록 기존 데이터를 옮기는 작업을 한다.
• 모든 기존 데이터를 옮겼다면 원하는 인덱스 부분에 값을 삽입한다.
• O(n) 속도로 추가된다.

remove() - 배열 마지막에 데이터 삭제

1. remove(4)
                "null"
                  ↓
+---+---+---+---+---+
| e | a | b | c | d |
+---+---+---+---+---+
size = 5, capacity = 5

## Complate remove() ##
+---+---+---+---+---+
| e | a | b | c | ? |
+---+---+---+---+---+
size = 4, capacity = 5

• remove 사용으로 원하는 위치에 데이터를 삭제할 수 있다.
• 마지막 위치인 경우 기존 데이터를 옮길 필요가 없다.
• 삭제 완료 후 size를 감소한다.
• O(1) 속도로 삭제한다.

remove() - 배열 앞에 데이터 삭제

1. remove(0)
"null"
  ↓
+---+---+---+---+---+
| e | a | b | c | ? |
+---+---+---+---+---+
size = 4, capacity = 5

## Complate remove() ##
+---+---+---+---+---+
| a | b | c | ? | ? |
+---+---+---+---+---+
size = 3, capacity = 5

• remove 사용해 원하는 위치에 데이터를 삭제하였다.
• 마지막 위치가 아닌 데이터 위치 기준으로 데이터를 옮기는 작업이 필요하다.
• 데이터 이동에는 O(n) 요구된다.
• O(n)으로 표현된다.

add 메소드 추가

add() shiftRightForm(), remove(), shiftLeftForm() 메소드를 각각 추가한다.

add()

public void add(int index, Object e) {
    // 코드 추가
    if (size == elementData.length) {
        grow();
    }

    // 데이터 이동
    shiftRightForm(index);

    elementData[index] = e;
    size++;
}

• 데이터 이동에는 별도의 shiftRightForm 메소드로 처리한다.

shiftRightForm()

// 코드 추가 요소 마지막까지 데이터 밀기
private void shiftRightForm(int index) {
    for (int i = size; i > index; i--) {
        elementData[i] = elementData[i - 1];
    }
}

• for문 초기값을 배열의 사이즈로 선택한다.
• 배열의 인덱스에서 앞에 있는 인덱스를 불려와 채우도록 한다.

remove()

// 코드 추가
public Object remove(int index) {
    Object oldValue = get(index);
    shiftLeftFrom(index);
    // 데이터 이동
    size--;
    elementData[size] = null;
    return oldValue;
}

• remove 에서는 변경의 set 했던 것과 유사한 코드이다. 배열에 할당 할 때에는 null 값으로 주어진다.
• shiftLeftFrom 에서 기존 데이터를 옮기는 작업이 있다.

shiftLeftForm()

// 코드 추가 요소의 index 부터 마지막까지 왼쪽으로 밀기
private void shiftLeftFrom(int index) {
    for (int i = index; i < size - 1; i++) {
        elementData[i] = elementData[i + 1];
    }
}

• 삽입한 인덱스와 배열 사이즈 사이의 기존 데이터를 안으로 당겨줘야 한다.

테스트

Main.class

CList list = new CList();
System.out.println("** 데이터 추가하기 **");
list.add("a");
list.add("b");
list.add("c");
System.out.println(list);

System.out.println("** addLast **");
list.add(3, "addList");
System.out.println(list);

list.add(0, "addFirst");
System.out.println(list);

Object rev = list.remove(4);
System.out.println("removed(4) = " + rev);
System.out.println(list);

Object first = list.remove(0);
System.out.println("removed(0) = " + first);
System.out.println(list);

** 데이터 추가하기 **
[a, b, c], size = 3, capacity = 10
** addLast **
[a, b, c, addList], size = 4, capacity = 10
[addFirst, a, b, c, addList], size = 5, capacity = 10
removed(4) = addList
[addFirst, a, b, c], size = 4, capacity = 10
removed(0) = addFirst
[a, b, c], size = 3, capacity = 10

정리

지금까지 리스트 자료구조를 만들었고 내부 배열로(Array) 보관하여 부가기능을 추가해 편리하게 사용할 수 있었다.

배열 리스트의 빅오

• 데이터 추가
  • 마지막 데이터 추가 O(1)
  • 중간에 데이터 추가 O(n)
• 데이터 삭제
  • 마지막 데이터 삭제 O(1)
  • 중간에 데이터 삭제 O(n)
• 데이터 조회 O(1)
• 데이터 검색 O(n)

배열 리스트 마지막 부분을 추가하거나 데이터 삭제에는 O(1) 매우 빠르나 중간 데이터 추가에는 O(n) 만큼 느리다.

배열은 순서대로 출력하거나 삭제하는 것이 가장 빠르고, 만약 맨 앞의 데이터를 추가하거나 삭제할 경우 다른 자료구조에 비해 현저리 느려진다.