Java - 자료구조(List, Set, Map)

개발자 이상규·2022년 3월 31일

목록 보기

4/6

Java Collection Framework 란

컬렉션은 기본 데이터형이 아닌, 참조 데이터형만 저장이 가능합니다.
따라서 Collection에서의 데이터는 Object 타입의 객체로서 저장이 됩니다.
오토박싱을 통해 기본 데이터형을 컬렉션에 직접 대입하여 저장해도 컴파일러가 자동으로 Wrapper 클래스로 변환해주고
저장된 값을 얻어올 때에도 객체화된 데이터를 기본 데이터형으로 바로 얻어올 수 있는 데, 이 경우 언박싱(unboxing)이라는 용어를 사용합니다.

List 인터페이스

힙(heap) 영역 내에서 List는 객체를 일렬로 늘어놓은 구조를 하고 있습니다.
객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동으로 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있습니다. 이 때 List 컬렉션은 객체 자체를 저장하여 인덱스를 부여하는 게 아니라, 해당하는 인덱스에 객체의 주소값을 참조하여 저장합니다.

ArrayList

자바에서 배열은 초기화 시 그 크기가 고정되어야하고 사용 중에 크기를 변경할 수 없다는 점에서 ArrayList와 차이가 납니다.
기본 생성자로 ArrayList 객체를 생성하면 내부에 10개의 객체를 저장할 수 있는 초기 크기를 가지게 됩니다.
크기를 초과한 객체들이 들어오면 list가 참조하고 있는 ArrayList 컬렉션에는 10*2+2 = 22개의 객체를 저장할 수 있는 공간이 자동으로 생겨납니다.

ArrayList의 크기를 늘리게 되는 경우, 기존의 ArraList에 추가하는 것이 아닌, 확장된 크기의 ArrayList를 새로 생성하고, 그 새로 생성된 ArrayList에 기존의 ArrayList 값들을 복사해주는 과정을 거칩니다. 그리고 기존의 ArrayList는 가비지 컬렉션에 의해 메모리에서 제거됩니다. 따라서 ArrayList에서 크기를 늘린다는 것은 새로운 배열 인스턴스의 생성과 기존 데이터의 복사가 필요한 번거로운 작업이 되는 것입니다.

ArrayList는 중간에 위치한 객체를 삭제하여도, 그 인덱스를 자동으로 업데이트 해주기 때문에 처음 삭제된 후 뒤의 객체들이 앞으로 한 칸씩 이동하며 그 자리를 자동으로 메꾸는 형태가 된다.

ArrayList 시간 복잡도

add(E e): ArrayList의 끝에 요소를 추가합니다.
시간 복잡도: O(1) (평균적으로)
최악의 경우(배열의 크기가 최대를 넘은경우)에는 배열 크기를 조정해야 하므로 O(n)이 될 수 있습니다.
add(int index, E element): 특정 위치에 요소를 추가합니다.
시간 복잡도: O(n) (해당 위치 이후의 요소들을 이동해야 함)
remove(int index): 특정 위치에 있는 요소를 제거합니다.
시간 복잡도: O(n) (해당 위치 이후의 요소들을 이동해야 함)
get(int index): 특정 위치에 있는 요소를 반환합니다.
시간 복잡도: O(1)

ArrayList는 특정 위치에 데이터를 추가, 제거하려면 특정 위치 다음에 존재하는 데이터를 복사한 후 한칸 뒤에 붙혀야 합니다.
즉 Shift 하는 시간이 포함되기때문에 O(n)의 시간복잡도를 가집니다.

LinkedList(이중 연결 리스트)

LinkedList는 List 구현 클래스이므로 ArrayList와 사용하는 메소드는 같지만 내부 구조는 완전 다릅니다.
LinkedList는 이중 연결 리스트로 구현되어 있으며 ArrayList는 내부 배열 객체를 저장해서 인덱스로 관리하지만, LinkedList는 양방향 포인터 구조로, 각각마다 인접하는 참조를 링크해서 체인처럼 관리합니다.
특정 인덱스의 객체를 제거하거나 삽입하면, 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 그러므로 중간 삽입/삭제가 빈번할 수록 LinkedList를 쓰는 것이 효율적이고 반대로, 순차적인 삽입/삭제가 빈번하다면 ArrayList를 사용하는 것이 효율적입니다.

LinkedList(이중 연결 리스트) 시간 복잡도

add(E e): LinkedList의 끝에 요소를 추가합니다.
시간 복잡도: O(1)
add(int index, E element): 특정 위치에 요소를 추가합니다.
시간 복잡도: O(n) (해당 위치의 가까운 쪽에서 추가)
remove(int index): 특정 위치에 있는 요소를 제거합니다.
시간 복잡도: O(n) (해당 위치의 가까운 쪽에서 제거)
get(int index): 특정 위치에 있는 요소를 반환합니다.
시간 복잡도: O(n) (해당 위치의 가까운 쪽에서 검색)

Set 인터페이스

데이터의 저장 순서를 유지하지 않기 때문에 중복저장을 허용하지 않습니다.

HashSet : 순서가 필요없는 데이터를 hash table에 저장. Set 중에 가장 성능이 좋습니다.
TreeSet : 저장된 데이터의 값에 따라 정렬되지만 정렬되는만큼 HashSet보다 속도가 느립니다.
LinkedHashSet : 연결된 목록 타입으로 구현된 hash table에 데이터 저장하고 저장된 순서에 따라 값이 정렬되나 셋 중 가장 느립니다.