JAVA의 자료구조 (JAVA Collection Framework)

자료구조와 Collection Framework?

자료구조란 Data의 집합을 의미하며 컴퓨터가 데이터를 효율적으로 처리하기 위해 만든 구조이다. Collection Framework는 이러한 자료구조를 표준화된 방법으로 제공 가능하게 하는 클래스의 집합이다.

Collection Framework는 대표적으로 List, Set, Map이 있으며 아래와 같은 구조를 가지고 있다.

 

Collection Framework 구조

 

List, Set, Map은 기본형(primitive) 데이터의 저장이 불가능하고 참조형(reference) 데이터만 저장 가능하다. 만약 기본형 데이터를 저장하고 싶다? 그럼 Wrapper클래스를 사용하면 된다. 예) int 대신 Integer클래스, boolean 대신 Boolean 클래스 사용.

 

해당 글에서는 Collection Framework중에서도 Collection을 인터페이스로 가지는 List와 Set에 대해 정리해 볼 것이다.

 

 

 

 

 

List란?

다른 컬렉션과 비교했을때 List는 아래의 특징을 갖고 있다.

• 데이터의 중복 허용
• 데이터 저장순서 유지

 

리스트는 인덱스를 사용한다. 데이터가 들어오면 차례대로 인덱스에 저장되기 때문에 데이터 입력 순서의 유지가 가능하다. (방금 데이터가 인덱스에 저장된다고 했지만 정확히 말하자면 데이터를 그대로 저장하는 것이 아니라 각 인덱스에 객체의 주소값을 참조시키는 것).

 

리스트의 구현체로는 대표적으로 ArrayList, Vector, LinkedList가 존재한다.

 

ArrayList

이름에서부터 알 수 있듯이 ArrayList는 Array방식을 사용하는 List구현체이다. 둘은 인덱스를 사용한다는 점에서 매우 비슷한 특징을 갖고 실제로도 사용 방식이 비슷하다. 하지만 특징이 100%같은 자료구조는 없다.

 

ArrayList	Array
초기화시 길이 선언 불필요	초기화시 길이 선언 필수

Array는 초기화시 컴퓨터가 그 길이를 알아야 한다. 즉 길이의 고정이 필요하다는 말이다. 그렇기에 배열을 한 번 생성하고 나면 길이를 변경시키기 힘들다. 하지만 ArrayList는 초기화시 컴퓨터에게 길이를 알려줄 의무가 없다. 그렇기에 데이터의 추가가 배열에 비해 매우 편리하다.

 

 

Vector

ArrayList	Vector
비동기 방식	동기 방식

Vector는 ArrayList와 비슷하지만 한 가지 큰 차이점이 있다. 바로 동기화 방식의 메소드를 제공한다는 것이다. 그렇기 때문에 멀티스레드 환경에서 안정적일 수 있다는 장점을 갖는다. 반면에 동기화 기능때문에 성능이 매우 떨어진다는 단점을 동시에 갖게 된다. 현재도 사용 가능하긴 하나 호환성등의 이유가 아니라면 사용을 권장하지는 않고 있다.

 

 

LinkedList

LinkedList는 ArrayList와 완전히 다른 내부 구조를 갖는다.

 

ArrayList	LinkedList
단방향 포인터	양방향 포인터

ArrayList는 단방향의 포인터를 사용하지만 LinkedList는 양방향의 포인터를 사용한다. 즉 ArrayList는 Index → 객체의 주소 형식이기 때문에 단방향, LinkedList는 이전객체 주소 + Node + 다음객체 주소 형식이기 때문에 양방향을 갖는 것이다.

 

ArrayList는 인덱스만 알면 데이터를 가져올 수 있다. 그래서 검색이 빠르다. 하지만 LinkedList는 각 Node가 다음 데이터에 대한 정보를 갖고있다. 그렇기에 원하는 데이터를 찾으려면 첫 Node부터 순회하며 찾아내야 한다. 그래서 검색이 느리다.

 

 

 

 

 

Set이란?

• 데이터 중복 허용X
• 데이터 저장순서 유지X

 

Set은 List와 다르게 중복 데이터를 허용하지 않는다. null값도 하나만 저장 가능하다. 즉 Set에 저장된 모든 데이터는 유일성을 갖는다. Set은 인덱스를 사용하지 않고 자신만의 function으로 데이터를 저장하기 때문에 순서가 보장되지 않는다.

 

HashSet

Set의 가장 대표적 구현체이다. 이름처럼 Hash Algorithm을 사용한다. Hash Algorithm은 빠르다. 그렇기에 HashSet은 성능이 매우 좋다는 장점을 가진다.

반면 별도의 정렬작업을 해 주지는 않기 때문에 순서의 보장이 필요한 경우라면 사용하기 적합하지 않겠다.

 

 

LinkedHashSet

데이터의 유일성을 보존하면서 순서의 보장이 가능하다. HashSet보다는 느리며 TreeSet보다는 빠르다. 

 

 

TreeSet

마찬가지로 순서를 보장받을 수 있는 Set 구현체이다. TreeSet은 데이터를 저장하기 전 Comparator를 사용하여 정렬을 해 준다. 그렇기에 값을 순차적으로 저장 가능한 것이다. 대신 정렬이라는 추가 작업이 필요하기 때문에 HashSet보다 성능은 낮다.

 

한가지 더 특이한 점은 TreeSet은 null저장이 불가능하다. null 저장을 시도할 시 NullPointerException이 뜬다. HashSet과 LinkedList가 데이터 중복 비교를 위해 hashCode()와 equals()를 쓰는 반면 TreeSet은 compare() 혹은 compareTo()를 사용한다.