Collection 프레임워크
Collection 프레임워크에서 지원하는 자료구조들과 Map은 전부 힙 영역에 저장된다.
List, Set, Map의 각 노드에는 객체를 가르키는 주소가 저장되어있고 중복이 허용되는 Lsit와 Map은 A요소와 B요소가 서로 완전히 똑같은 값을 가진 객체가 배정 된다면 하나의 객체를 가르키는 주소값을 서로 공유 하는 형태로 구성된다.
상속 구조도
전체적인 구조만 표현한 구조도입니다. (생략된 부분 존재)
List
List는 중복된 값을 삽입하는 것이 가능하고 인덱스 넘버를 통해 참조하고 관리된다.
List의 종류
-
ArrayList
중간 인덱스의 요소를 특정해서 삭제하면 해당 요소보다 뒤의 인덱스를 가진 요소들이 한 칸 씩 앞으로 당겨진다.
-
Vector 스레드에 안전한 ArrayList 개념
ArrayList와 완전히 똑같이 작동하되 멀티쓰레드를 통해 동시에 호출하는 것이 불가능하다. (스레드에 안전하다)
-
LinkedList 완전한 자료구조 연결리스트의 개념, 링크 체인형태로 객체를 관리
특징 : 먼저 중간 인덱스에서 삭제가 이루어지면 해당 링크(L)와 서로 바라보던 L-1번 L+1번인덱스의 링크들과 연결을 끊고 -1, +1번 인덱스가 서로 다시 링크를 연결한다.
실질적으로 리스트의 요소 사이의 빈공간 없이 관리되지만 원래 중간 링크가 가지고있던 인덱스 번호는 비어있게 된다. 이 특징 덕분에 높은 빈도의 삽입 삭제가 이루어 질 때 속도 측면에서 ArrayList보다 유리하다.
Set
Set은 저장 순서를 보장하지않고 중복을 허용하지 않는다. 중복 금지에선 null도 해당된다. 두 개 이상의 null값을 저장하지 않는다.
Set의 종류
-
HashSet
객체들을 순서없이 저장하고 hashcode를 통한 중복을 방지한다.
-
TreeSet
Comparator인터페이스를 이용해 삽입되는 값이 비교되면서 정렬된 자리로 들어가게된다.
-
SortedSet
구현체가 없고 정렬된 셋을 다루기 위한 메서드들이 들어있는 인터페이스이다.
TreeSet을 선언에 정렬된 리스트를 구성하고
- headSet() : 가장 작은 값부터 인자로 넘긴값 직전까지의 요소들을 셋으로 리턴합니다.
- tailSet() : 가장 큰 값부터 인자로 넘긴값까지 포함해서 요소들을 셋으로 리턴합니다.
- subSet() : 인자로 넘긴 A와 B사이의 인자들을 셋으로 리턴합니다. A인자는 포함되고 B인자 직전까지의 요소들만 리턴됩니다.
- 가장자리 요소의 접근은 first(), last()
Collection의 대표적인 메서드
-
add() 컬렉션에 요소 삽입
인덱스를 지정해 값을 삽입, 값을 맨 뒤에 삽입
-
A.addAll(B) 컬렉션의 컬렉션삽입
B컬렉션의 요소들을 추출하여 A컬렉션에 삽입
인덱스를 지정해 해당 인덱스 부터 중간에 끼워넣어 삽입
-
clear() : 컬렉션의 모든 요소를 지운다.
-
contains() : 컬렉션에 요소들 중 파라미터로 넘긴 인자가 있는지 확인한다.
있으면 true 없으면 false를 리턴한다. -
A.containsAll(B) : 컬렉션 A의 요소들중 컬렉션 B의 요소가 완전히 포함되는지 확인한다.
있으면 true 없으면 false를 리턴한다. -
remove() : 컬렉션에서 인덱스나 값에 해당되는 요소를 제거한다.
-
A.removeAll(B) : A컬렉션의 요소들중 B컬렉션의 요소에 해당하는 것들을 전부 삭제한다.
-
A.retainAll(B) : A컬렉션에서 B컬렉션의 요소만 남기고 전부 삭제한다.
-
size() : 컬렉션의 현재 크기를 리턴한다.
-
toArray() : 컬렉션의 요소들을 지정한타입의 배열로 만들어 리턴한다.
-
iterator() : 요소를 하나씩 꺼내서 반복해주는 iterator 객체를 리턴해준다.
1. hasNext() : 다음 값의 유무를 판단해 참, 거짓을 리턴해준다.
2. next() : 현재 노드가 가르키고있는 객체를 리턴해주고 다음 노드로 이동한다.
3. remove() : 직전 next() 메서드에 의해 리턴 된 객체가 저장되어있는 노드를 삭제한다.
위의 메서드들 중 리턴 방식이 설명 되지않은 메서드들은 전부 메서드가 정상 작동했는지 여부를 boolean으로 리턴한다.
Stack과 Queue 그리고 Deque
스택(Stack)이나 큐(Queue)의 작동 구조를 몰라도 대부분의 사람들이 이해하고있는 선입선출(FIFO, 큐), 후입선출(LIFO, 스택) 개념이 적용된 자료구조이다.
컬렉션의 개념이 없는 프로그래밍 언어에서는 자바에서의 리스트와 같은 형태를 구현하는것보다. 스택이나 큐를 구현하여 상황에 맞게 사용하는것이 더 유리하지만,
자바에서는 List의 인덱스 참조 개념을 이용해 똑같이 동작하게 구현 할 수 있어서“특정 자료구조를 이용해 구현하도록 유도되는 문제를 풀어내야하는 경우나 극한의 효율성으로 최적화 해야하는 경우가 아니라면 거의 사용하지않는다.
데크(Deque)는 앞, 뒤 양방향에서 전부 삽입과, 추출이 가능하다. 바로 위의 구문 처럼 데크도 스택처럼 사용할 수도 큐처럼 사용할 수 도있다. 어차피 똑같은데 리스트를 쓰면 되는거 아닌가? 할 수 있지만,
데크를 사용하는 이유는 높은 빈도의 푸시, 팝 연산이 발생하는 경우에 리스트보다 좋은 성능을 보인다.
인덱스를 지정해서 값을 참조해야하는 연산이 존재하지않고 양 끝에서 삽입과 삭제 연산으로만 풀어가야하는 로직을 구현 할 때 사용하면 효율적이다.
ex) List.add(0,instance) ⇒ 스택과 큐의 삽입(push),
List.get(0) & List.remove(0) ⇒ 스택의 삭제(pop),
List.remove(List.size() - 1) ⇒ 큐의 삭제(poll);
코딩 테스트용 결론
- 중간에서 삽입 삭제가 많으면 LinkedList로 최적화
- 양끝에서 푸시, 팝이 많으면 Deque로 최적화
Map
맵의 종류
-
HashMap
Key와 Value 형태로 데이터를 관리하는 자료구조로 인덱스 대신 key통해 값을 참조하는 방식의 자료구조이다.
Key는 저장 순서를 보장하지않고 중복도 허용하지않는다 Set과 같은 특징을 가진다 Key와 매핑되기때문에 Value 또한 순서를 보장하지는 않지만 중복은 허용된다.
또 멀티스레드의 개념에서 동기화를 지원하지 않는다. (스레드에 안전하다.)
-
HashTable
해시 테이블은 해시 맵보다 조금 더 복잡한 개념이다. 키 와 밸류가 바로 매핑되는 것이아니라 해시 함수를 통해서 해시값을 생성하고 해시값과 키를 매핑하여 해시 값을 주소값처럼 사용해 검색에 용이하게 만든 자료구조이다.
Map의 대표적인 메서드
- put() : key : value형태로 값을 저장
- A.putAll(B) : 맵A에 맵B의 entry들을 전부 저장
- get() : key값을 넣으면 매치되는 밸류를 리턴
- remove() : key값을 넣으면 매치되는 entry를 삭제
- containsKey() : 요소들의 Key값들 중 인자와 같은 값이 있으면 true리턴
- containsValue() : 요소들의 Value값들 중 인자와 같은 값이 있으면 true리턴
- keySet() : Set형태로 key들을 리턴 (중복X 특징을 유지)
- values() : 컬렉션 형태로 value들을 리턴
- entrySet() : entry들을 셋에 담아서 리턴한다.
- getKey() : 해당 엔트리의 키를 리턴
- getValue() : 해당 엔트리의 밸류를 리턴
