컬렉션 프레임웍

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

컬렉션 프레임웍의 핵심 인터페이스

• List : 순서가 있는 데이터의 집합. 데이터의 중복을 허용한다
• Set : 순서를 유지하지 않는 데이터의 집합. 데이터의 중복을 허용하지 않는다
• Map : 키와 값의 쌍을오 이루어진 데이터의 집합. 순서는 유지되지 않으며 키는 중복을 허용하지 않고, 값은 중복을 허용한다

List 인터페이스

• 중복 허용, 저장순서 유지
• ArrayList, LinkedLists, Stack 등

Set 인터페이스

• 중복 허용 안함, 저장순서 유지 안함
• HashSet, TreeSet 등

Map 인터페이스

• Key와 Value를 하나의 쌍으로 묶어서 저장
• Key값은 중복 허용 안함, Value값은 중복 허용
• 중복된 키를 사용하면 기존의 값은 사라지고 마지막에 저장된 값이 남게된다
• Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap 등

Map.Entry 인터페이스

• Map 인터페이스의 내부 인터페이스
• Key-Value 쌍을 다루기 위해 내부적으로 Entry 인터페이스를 정의함

ArrayList

• List 인터페이스 구현
• 기존의 Vector를 개선한 것
• Object 배열을 이용해서 데이터를 순차적으로 저장
• 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장
• 모든 객체의 최고조상인 Object를 멘버변수로 선언하고 있기 때문에 모든 종류의 객체를 담을 수 있다
• ArrayList에서 한 요소가 삭제되면 빈 공간을 채우기 위해 나머지 요소들이 자리를 이동한다
• ArrayList를 생성할 때, 저장할 요소의 개수를 고려해서 실제 저아할 개수보다 약간 여유있는 크기로 하는 것이 좋다
• 생성할 때 지정한 크기보다 더 많은 객체를 저장하면 자동적으로 크기가 늘어나기는 하지만 이 과정에서 처리시간이 많이 소요된다
• ArrayList의 배열 크기(용량)와 실제 배열의 사이즈를 변경한 경우 매번 기존의 인스턴스를 다시 사용하는게 아니라 새로운 인스턴스를 생성함
• ArrayList의 remove는 삭제할 때 저장된 위치(index)에 있는 객체를 삭제하고 삭제한 객체를 반환하도록 작성되었다
• 삭제할 객체의 바로 아래에 있는 데이터를 한 칸씩 위로 복사해서 삭제할 객체를 덮어쓰는 방식
• 만약 삭제할 객체가 마지막 데이터라면 복사할 필요 없이 단순히 null로 변경만 해주면 된다
• 배열에 객체를 순차적으로 저장할 때와 객체를 마지막에 저장된 것부터 삭제하면 arraycopy()를 호출하지 않기 때문에 작업 시간이 짧지만 배열의 중간에 위치한 객체를 추가하거나 삭제하는 경우 arraycopy를 호출해서 다른 데이터의 위치를 이동시켜줘야 하기 때문에 다루는 데이터의 개수가 많을수록 작업 시간이 오래 걸린다

LinkedList

• List 인터페이스 구현
• 배열은 가장 기본적인 형태의 자료 구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠르다는 장점을 가지고 있다
• 하지만 크기를 변경할 수 없고 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸리는 단점이 있다
• 이런 배열의 단점을 보완하기 위해 링크드리스트라는 자료구조가 고안되었다
• 배열은 모든 데이터가 연속적으로 존재하지만 링크드리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다
• 링크드리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)왕 데이터로 구성되어 있다
• 링크드리스트에서의 데이터 삭제는 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경한다
• 배열처럼 데이터 이동을 위한 복사 과정이 없기 때문에 처리 속도가 빠르다
• 링크드리스트는 이동 방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다
  - 이를 보완한 것이 더블 링크드 리스트이다
  - 더블 링크드 리스트는 참조변수를 하나 더 추가하여 다음 요소에 대한 참보뿐이 아니라 이전 요소에 대한 참조가 가능하도록 했다
  - 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드리스트보다 더 많이 사용된다
• 더블 링크드 리스트의 접근성을 보다 향상시킨 것이 더블 서큘러 링크드 리스트(이중 원형 연결 리스트)이다
  - 더블 링크드 리스트의 첫번째 요소와 마지막 요소를 서로 연결시킨 것
• 실제로 LinkedList 클래스는 더블 링크드 리스트로 구현되어 있다
• List 인터페이스를 구현했기 때문에 ArrayList와 내부구현방법만 다를 뿐 제공하는 메서드의 종류와 기능은 거의 같다

ArrayList와 LinkedList 비교

• 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다
  - 단 저장공간이 부족해서 새로운 ArrayList를 생성해야 하는 상황에는 데이터를 복사하는 일이 발생하게 되므로 LinkedList가 빠를 수 있다
  - 순차적으로 삭제하는 경우에는 마지막 데이터부터 역순으로 삭제한다는 것이기 때문에 ArrayList는 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않아서 상당히 빠르다
• 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다
  - LinkedList는 요소간의 연결만 변경하면 되지만 ArrayList는 새로 배열을 생성해서 재배치해줘야 하기 때문에 속도가 느리다
  - 데이터의 개수가 그리 크지 않다면 어느 것을 사용해도 크게 차이가 나지 않는다
• 배열의 경우 인덱스가 n인 요소의 값을 얻어오고자 하는 경우, 각 요소들이 연속적으로 메모리상에 존재하기 때문에 간단하게 요소의 주소를 얻어서 저장된 데이터를 곧바로 잃어올 수 있지만 LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야 원하는 값을 얻을 수 있다
  - 그래서 LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어오는 시간, 즉 접근 시간이 길어진다