배열(Array)

  • 동일한 타입의 데이터를 연속적인 메모리 공간에 저장하는 자료구조
  • 선언할 때 크기를 지정해야 하며, 한번 정해진 크기를 변경할 수 없다.
  • 인덱스를 이용해 상수시간(O(1))에 배열의 임의의 원소에 접근할 수 있다.

타입[ ] 배열이름 = new 타입[ ] 형태로 선언한다.

int[] arr = new int[5];

리스트(List)

  • 데이터를 순서대로 저장하는 자료 구조
  • 선언 이후에도 크기를 동적으로 변경 가능
  • 구현체로 ArrayList, LinkedList 등이 있다. 
    List<Integer> list = new ArrayList<>();
List<Character> list = new LinkedList<>();

ArrayList

  • 원소들을 내부 배열에 저장한다.
    • 조회 : index를 이용해 상수 시간에 임의의 원소에 접근 가능
    • 추가 / 삭제 / 수정 자체는 상수 시간에 처리할 수 있지만, 그 과정에서 배열을 재할당 하거나 원소들을 이동시키는 경우 추가 작업이 필요하다.

1

  • 이때 반복문으로 복사하는것이 아닌 System.arraycopy(src, srcPos, dest, destPos, length) 함수를 이용한다.
    (src배열의 srcPos번째부터 length개의 원소를 dest배열의 destPos번째부터 length개의 원소에 복사) -> 단순 반복문보다 2배이상 빠르다.

ArrayList - get : (x축 : 원소 번호, y축 : 걸린시간(ms))

  • 길이가 1,000인 ArrayList에서 get메소드로 각 원소에 접근하는데 걸린 시간

2

ArrayList - add : (x축 : 추가한 원소 개수, y축 : 걸린시간(ms))

add 작업 시 내부 배열이 가득 찰 경우 배열 재할당 작업이 발생(O(N))한다. 이때, 기존 배열의 1.5배 크기의 배열을 할당한다. 3

  • ArrayList에서 1~1000개의 원소를 맨 뒤에 add하는데 걸린 시간 4

배열이 가득 찼을때만, 새로운 배열을 할당 하므로, 거의 상수시간에 근접하게 원소를 추가할 수 있다. N개의 원소를 추가하는데 O(N)에 근접한 시간복잡도를 가진다.

ArrayList - 리스트 중간에서의 add : (x축 : 추가한 원소 개수, y축 : 걸린시간(ms))

  • 리스트 맨 앞에 원소를 add하는 경우 5

  • 리스트 중간에 원소를 add하는 경우 6

리스트 맨앞/중간에 원소를 add하는 경우, 각 add마다 arraycopy가 발생하므로, 성능이 좋지 않다. N개의 원소를 추가하는데 O(N^2)의 시간복잡도를 가진다.

LinkedList

  • 내부적으로 double linked list 형태로 구현되어있다.
    • 각 노드들은 자신의 이전 노드와 다음 노드에 대한 정보만 가지고 있다.

7

  • LinkedList는 전체 노드가 아니라 맨 처음 노드와 마지막 노드만 가지고있다.

8

그렇기에 n번째 원소를 조회하기 위해서는 맨 앞 또는 뒤에서부터 순차적으로 탐색(O(N))을 해야 한다.
하지만, 추가/삭제의 경우 앞뒤 노드의 연결을 변경(O(1))해주는것만으로 처리할 수 있기 때문에 매우 빠르게 처리할 수 있다. 9

LinkedList - get : (x축 : 원소 번호, y축 : 걸린시간(ms))

  • 길이가 1,000인 LinkedList에서 get메소드로 각 원소에 접근하는데 걸린 시간 10

맨 앞 또는 뒤에서부터 순차적으로 탐색하므로, 중앙의 원소에 가까울수록 조회 성능이 떨어진다.

LinkedList - add : (x축 : 추가한 원소 개수, y축 : 걸린시간(ms))

  • 리스트 맨 앞에 원소를 add하는 경우 11

  • 리스트 맨 뒤에 원소를 add하는 경우 12

-> 양 끝에서의 추가/삭제는 탐색 없이 이루어지므로 N개의 원소를 추가/삭제하는데 O(N)의 시간복잡도를 가진다.

  • 리스트 중간에 원소를 add하는 경우 13

-> 추가/삭제 작업 자체는 상수시간내에 이루어지지만, 추가/삭제 위치까지 탐색하는데 O(N)이 필요하므로, N개의 원소를 추가/삭제하는데 O(N^2)의 시간복잡도를 가진다.

ArrayList vs LinkedList

  • 인덱스로 원소에 접근하는 경우(get(idx))
    • ArrayList : O(1)
    • LinkedList : O(N)
  • 맨 앞에 추가/삭제하는 경우(add(0, element), remove(0, element))
    • ArrayList : arraycopy로 전체 배열을 이동시켜야하므로 O(N)
    • LinkedList : 추가적인 노드 탐색 없이 노드 추가 가능 O(1)
  • 중간에 추가/삭제하는 경우(add(idx, element), remove(idx, element))
    • ArrayList : 추가/삭제하는 위치(idx)부터 마지막 원소까지를 한칸씩 앞/뒤로 이동시켜야함(arraycopy)
      -> 이동시키는 원소의 개수에 따라 성능이 결정됨
      -> idx가 리스트 앞쪽에 있을수록 성능이 나쁘고,리스트 끝쪽에 있을수록 성능이 좋아짐
    • LinkedList : 추가/삭제하는 위치(idx)까지 first/last 노드에서부터 탐색하여 idx번째 노드를 찾고 추가/삭제를 진행
      추가/삭제는 상수 시간에 처리되므로 idx번째 노드를 찾는데 까지 걸리는 시간에서 성능 차이가난다.
      노드 탐색은 양끝(first/last)에서 가능하므로, idx가 리스트 양 끝쪽에 가까울수록 성능이 좋고, 가운데에 가까울수록 성능이 나쁘다.
  • 맨 뒤에 추가/삭제하는 경우(add(element), remove(element))
    • ArrayList
      • 배열이 가득 차지 않음 : 배열에 원소를 추가/삭제 하는 것이므로 오버헤드가 적다.
      • 배열이 가득 참 : 새로운 배열(기존크기의1.5배)을 할당하고 기존 배열의 원소들을 복사(arraycopy)
    • LinkedList : 추가적인 노드 탐색 없이 노드 추가 가능 O(1) 하지만 배열에 비해 오버헤드(노드 연결 비용)가 존재한다. -> 맨 뒤에 추가하는 경우 간헐적으로 일어나는 arraycopy비용 vs 노드 생성 비용 에 따라서 ArrayList와 LinkedList의 성능 차이가 난다.

간헐적으로 일어나는 arraycopy비용 vs 노드 생성 비용

14

  • ArrayList와 LinkedList에서 1,000~100,000개의 원소를 맨 뒤에 add하는데 걸린 시간 x축 : 원소 개수(1,000개 단위), y축 : 걸린시간(ms)

  • 사실상 ArrayList와 LinkedList에 큰 차이가 나지 않는다.
    • 배열재할당이 일어난 직후에는 LinkedList가 성능이 좋다.
    • 하지만 배열에 원소를 추가하는 비용이 노드를 생성 연결 비용보다 작으므로 배열 재할당이 일어나지 않을때는 ArrayList가 성능이 좋다.
  • ArrayList(pre-allocated)는 배열재할당이 일어나지 않도록 초기 크기를 충분히 크게 설정한것 -> 배열 재할당이 일어나지 않으므로 성능이 가장 좋다.