Java 자료구조, 컬렉션 프레임웍 - 1, (List, Set, Map)

데이터 군을 저장하는 클래스들을 표준화한 설계

 

핵심 인터페이스

컬렉션데이터 그룹을 크게 3가지 타입이 존재한다고 인식 후, 3개의 인터페이스 정의

List, Set, Map 이후 List, Set의 공통된 부분을 다시 뽑아서 Collection 인터페이스를 추가 정의

List        : 순서가 있는 데이터의 집합, 데이터 중복 허용 o
Set         : 순서가 없는 데이터 집합, 중복 허용 x
Map         : 키와 값의 쌍으로 이루어진 데이터 집합, 키 중복 허용 x, 값 중복 허용 o

모든 컬렉션 클래스는 List, Set, Map 중 하나가 이름에 들어가 있어서 구별이 쉽지만,
Vector, Stack, Hashtable, Properties같은 것들은 컬렉션 프레임웍보다 먼저 생겨서 명명법이 다름.
호환을 위해 설계를 바꿔서 남겨뒀지만 사용하는 건 비추

ArrayList

Object배열을 이용해 데이터를 순차적으로 저장
더 이상 저장할 공간이 없으면, 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음 저장
    
elementData라는 이름의 Object배열을 멤버변수로 선언하고 있다. 따라서 모든 종류의 객체를 담을 수 있다

예시

for(int i = list2.size()-1; i >= 0; i--;){
    if(list1.contains(list2.get(i))){
        list2.remove(i);
    }
}

list2에서 list1과 공통되는 것들을 찾아 삭제하는 부분

변수 i를 0부터 증가시키지 않고 size-1부터 감소시키며 삭제했다.

증가시키면서 삭제하면, 한 요소가 삭제될 때마다 빈 공간을 채우기 위해 뒤의 요소들이 앞으로 자리이동을 하기 때문에 올바른 결과가 안나온다

생성할 때, 저장할 요소의 개수를 고려해서 약간 여유 있는 크기로 하는 것이 좋다.
더 많은 값이 들어오면 자동으로 배열 크기를 늘려주지만, 이 과정에서 처리 시간이 많이 소요된다.

    

용량(capacity)과 크기(size)

용량        : 실제 배열의 크기
크기        : 배열에서 1, 2, 3등의 실질적인 값이 들어가있는 것들의 크기

예시

a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = null;
a[4] = null;

용량은 5, 크기는 3
        

LinkedList

    배열의 단점 개선

배열의 단점

1. 크기 변경 불가
2. 비순차적 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
   차례대로 데이터를 추가하고, 마지막부터 데이터를 삭제하는 것은 빠르지만,
   배열 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다

LinkedList의 구조
        LinkedList[0]이 LinkedList[1]을 참조, LinkedList[1]이 LinkedList[2]를 참조해나가는 방식

        가운데 있는 LinkedList[1]을 지우고 싶으면, LinkedList[0]이 LinkedList[2]를 참조하는 방식으로 하면 빠름
    

링크드 리스트는 이동 방향이 단방향이기 때문에,

다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.
이 점을 보완한 것이 더블 링크드 리스트

단순히 링크드 리스트에 참조변수를 하나 더 추가하여 다음 요소, 이전 요소에 대한 참조가 가능하게 했을 뿐,

나머지는 똑같다.
    예시
        doubly-LinkedList의 구조
            LinkedList[0]의 첫 참조변수가 LinkedList[1], 두번째 참조변수가 null 참조,           

            // LinkedList[0]보다 앞에 있는게 없어서 null을 참조할 수 밖에 없다
           // 반대로 LinkedList[LinkedList.length-1]의 첫 참조변수도 null을 참조한다.
            LinkedList[1]의 첫 참조변수가 LinkedList[0], 두번째 참조변수가 LinkedList[2]를 참조해나가는 방식
    

doubly circular linked list

        더블 링크드 리스트 양 끝에서 null 참조하는게 불만이어서 만들어졌다

        LinkedList[0]의 두번째 참조변수가 LinkedList[LinkedList.length-1]을 참조,
        LinkedList[LinkedList.length-1]의 첫 참조변수는 LinkedList[0]을 참조한다.

ArrayList와 LinkedList

 

1. 순차적으로 추가, 삭제하는 경우, ArrayList가 빠르다

다만, ArrayList 크기가 충분하지 않으면,

새로운 ArrayList를 생성하고 복사하는 일이 발생해서 LinkedList가 더 빠를 수 있다
    

2. 중간 데이터를 추가/삭제하는 경우, LinkedList가 빠르다    

3. 다루고자 하는 데이터의 개수가 변하지 않는 경우, ArrayList가 빠르다

배열의 경우 인덱스가 n인 요소의 값을 얻어오고자 할 때, 아래의 수식을 계산한다
        
인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기
예시
arr[2]의 값을 읽으려 한다면 n은 2, 모든 참조형변수의 크기는 4byte, 생성된 배열의 주소는 0x100, 
3번째 데이터가 저장되어 있는 주소는 0x108이 된다

배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 간단한 계산만으로 데이터를 읽어올 수 있지만,
LinkedList는 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다
    

ArrayList, LinkedList간의 변경

        처음에 데이터를 ArrayList로 저장한 다음, 
        작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율이 나올 수 있다.

예시

ArrayList al = new ArrayList(1000000);
for(int i=0; i<100000; i++){
    al.add(i + "");
}

LinkedList li = new LinkedList(al);
for(int i = 0; i<1000; i++){
    li.add(500, "X");
}