[자바의 정석_기초편] Chapter11. 컬렉션 프레임워크 (Collections framework)_1

이 글은 남궁성의 정석코딩 [자바의정석-기초편]을 수강하며 정리한 글입니다.

 

 

🟣 기본 환경: IDE: Eclipse, Language: Java

 

 

Collection: 여러 객체(데이터)를 모아 놓은 것

FrameWork: 표준화, 정형화된 체계적인 프로그래밍 방식

Collection FrameWork

: 컬렉션(다수 객체)를 다루기 위한 표준화된 프로그래밍 방식

: 컬렉션을 쉽고 편리하게 다룰 수 있는 다양한 클래스 제공

Collection Class: 다수의 데이터를 저장할 수 있는 class

 

Collection FrameWork의 핵심 interface

Data의 특징에 따라 해당 데이터의 특징을 반영한 interface를 구현한 class 선택

* List: 저장 순서가 있고 중복을 허용하는 데이터의 집합

예: 대기자 명단

* Set(집합): 순서를 유지하지 않고 중복을 허용하지 않는 데이터 집합

예: 양의 정수의 집합

* Map: Key와 Value의 pair로 이루어진 데이터의 집합

순서는 유지되지 않으며, key는 중복을 허용하지않고, value는 중복을 허용

예: 아이디-패스워드

 

* Collection interface: list + set의 공통부분을 뽑아서 collection interface 정의

Method: 추가, 삭제, 검색

List Interface

Class: Arraylist, LinkedList

 

Method: 추가, 삭제, 검색, 정렬

Set Interface

Class: HashSet, TreeSet

 

* Map Interface

Class: HashMap(순서X→순서 필요 시, LinkedHashMap), TreeMap

Method: 추가, 삭제, 검색, 읽기

key-value 한쌍 = Entry

 

- ArrayList

 

과거 Vector(동기화 처리O)가 ArrayList(동기화 처리X)로 변경됨

 

List interface를 구현하므로, 저장순서가 유지되고 중복을 허용

 

데이터(객체) 저장공간으로 배열을 사용(배열 기반)

 

Object[]: 객체 배열 - 모든 종류의 객체를 저장 가능

 

ArrayList Method

기본생성자: ArrayList()

매개변수 생성자: ArrayList(Collection c)

: 매개변수로 collection을 주면 collection 내용을 저장할 수 있는 ArrayList를 만들 수 있음

- collection간 변환 시 사용

매개변수 생성자: ArrayList(int initialCapacity=배열의 길이)

 

- 추가

boolean add(Object o): 저장할 객체인 Object를 추가, 성공하면 true, 실패하면 false

void add(int index Object element): 저장 위치를 지정하여 추가(지정안하면 맨 뒤에 추가)

boolean addAll(Collection c): collection 모든 내용 추가

boolean addAll(int index, Collection c): 위치 지정하여 collection 추가

 

- 삭제

boolean remove(Object o)

Object remove(int index)

boolean removeAll(Collection c): Collection 객체 삭제

void clear(): ArrayList 내 모든 객체 삭제

 

- 검색

int indexOf(Object o): 객체 몇번째 저장되어있는지 찾기, 못찾으면 -1 반환

int lastIndexOf(Object o): 오른쪽에서 왼쪽으로 찾음

boolean contains(Object o): 객체의 존재 유무

Object get(int index): 객체 읽기

Object set(int index, Object element): 특정 위치 객체 변경

List subList(int fromindex, int toIndex): from~to 사이 객체를 뽑아서 새로운 list 만들기

Object[] toArray(): ArrayList가 갖고있는 객체 반환

Object[] toArray(Object[] a)

boolean isEmpty(): arraylisy가 비어있는지

void trimToSize(): 빈공간 제거

int size(): arraylist에 저장된 객체의 개수

 

ArrayList에 저장된 객체의 삭제과정

1. 삭제할 데이터 아래의 데이터를 한 칸씩 위로 복사해서 삭제할 데이터를 덮어쓴다.

→ 데이터를 많이 잡아먹으므로 일어나지 않도록 하는 것이 관건

2. 데이터가 모두 한 칸씩 이동했으므로 마지막 데이터는 null로 변경

→ data[size-1]=null;

3. 데이터가 삭제되어 데이터의 개수가 줄었으므로 size값을 감소시킨다.

→ size--;

cf. 마지막 데이터를 삭제하는 경우, 1(배열의 복사) 과정은 필요X

 

* 중요

for(int i=0; i<list.size(); i++)

list.remove[i];

→ ArrayList에 저장된 첫 번째 객체부터 삭제하는 경우 배열의 복사로 인해서 데이터가 남아 있음

for(int i=list.size()-1; i≥0; i--)

list.remove[i];

→ ArrayList에 저장된 마지막 객체부터 삭제하는 경우배열의 복사가 일어나지 않으므로 모든 데이터 삭제 가능, 복사도 없으므로 빠름

 

Array의 장단점

장점: 배열구조가 간단, 데이터 읽는 시간(접근 시간)이 짧음

단점: 크기를 변경할 수X

→ 변경 시, 새로운 배열 생성, 기존 배열 복사, 참조를 변경

→ 큰 배열 생성시, 메모리 낭비 문제

비 순차적 데이터 추가, 삭제에 시간이 오래 소요

(단, 순차적 데이터 추가 삭제(끝 부분부터 추가 삭제)는 빠름)

 

LinkedList

배열과 달리 linkedlist는 불연속적으로 존재하는 데이터를 연결

연결리스트, 불연속적이라서 데이터 접근성이 나쁨

→doubly linked list: 이중 연결리스트, 접근성 향상(앞 뒤로 이동이 가능)

→doubly circular linked list: 이중 원형 연결리스트, 접근성 향상(TV channel과 유사)

 

Stack: LIFO구조, 마지막에 저장된 것을 제일 먼저 꺼내게 됨 - 배열

- 저장: push, 추출: pop

- boolean empty(): 비어있는지 확인

- Object peak(): 맨 위에 저장된 객체 반환

- Object pool(): Stack 맨 위에 저장된 객체 꺼내기

- Object push(Object item): stack에 객체 저장

- int search(Object o): 객체의 위치 반환, array indexOf(0부터 시작), 1부터 시작(맨 위부터 1,2,3), 못찾으면 -1 반환

 

Queue: FIFO구조, 제일 먼저 저장한 것을 제일 먼저 꺼내게 됨 - linkedList(배열 사용 시, 자리 이동 필요)

- 저장: offer, 추출: poll

- boolean add(Object): 추가-예외 발생

- Object remove(): 삭제-예외 발생

- Object element(): 읽어오기 - 예외발생

- boolean offer(Object o): 추가

- Object poll: 제거

- Object peek(): 읽어오기

→ 주로 offer, poll, peek 사용

 

Stack - 클래스O, stack st = new Stack(); 가능

Queue - Interface, 객체 생성 불가

 

다형성 활용, 자손이 구체화 한 것을 활용

Queue q = new LinkedList();

q.offer(”0”);

 

Stack의 활용: 수식계산, 수식괄호검사(여는괄호는 넣고,(push) 닫는괄호는 빼기(pop)→최종적으로 스택이 비어있어야 함), Undo-Redo

Queue 활용: 최근사용문서, 인쇄작업대기목록, buffer

 

Ex11_4 오류

Illegal modifier for parameter MAX_SIZE; only final is permitted

→

매개변수와 지역변수는 컴파일 후 프로그램이 실행될 때 메서드 호출과 동시에 할당되거나 호출된 메서드 내부가 실행되는 도중에 할당됨

반면, static 변수는 컴파일 시 미리 메모리에 할당됨.

이러한 특징을 가진 static 변수가 매개변수나 지역변수와 함께 선언될 경우,

“컴파일 시 미리 할당되어있어야 하는 static변수가 프로그램이 실행되는 도중에 할당된다는 의미불명의 해석”이 되면서 지역변수/매개변수/static변수에 해당하는 건지를 판단할 수 없게됨

 

LinkedList is a raw type. References to generic type LinkedList<E> should be parameterized

LinkedList가 원시형으로 generic 타입의 LinkedList<>에 대한 매개변수를 지정해야한다.

= LinkedList에서 사용할 객체 타입이 정해져있지 않다.

→ 객체를 포함하는 자료형도 어떤 객체를 포함할 것인지 명시할 것을 권고

객체의 데이터 종류가 모두 동일하다면 LinkedList(Integer)등으로 객체를 같이 지정

 

null과 빈문자열

“”는 실제 문자열이지만 빈 문자열, 그러나 null은 String 변수가 아무것도 가리키지 않음을 의미

String s1 = “”; → length = 0

String s2 = null; → length = nullpointException

 

Iterator(new), ListIterator, Enumeration(old)

boolean hasNext(): 읽어올 요소가 남아 있는가

Object next(): 다음 요소를 읽어 옴

ListIterator: Iterator의 접근성 향상(단방향→양방향)

Collection: List(Array, LinkedList), Set(), Queue(): 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화 한 것

Iterator는 Collection Interface에 정의되어있어 Collection의 자손인 List와 Set이 모두 갖고 있는 method

Iterator를 2번 사용할 경우, 이미 다 읽었으므로 뒤의 Iterator는 작동하지 X

그러므로 다쓰고나면 다시 객체를 만들어서 읽어야 함 → 유연한 코드

Collection c= new HashSet();

으로 코드를 작성할 경우, 만일 collection method만 구현하면 될 경우, hashset 대신 TreeSet으로 사용하면 코드 검토가 필요X

 

Map에는 iterator가 없다.

→ keySet(), entrySet(), values()를 호출해야 한다.

Map map = new HsahMap();

Iterator it = map.entrySet().iterator();

→ Set eSet = map.entrySet();

→ Iterator it = eSet.iterator();

 

Array: 배열을 다루기 편한 static method 제공

(비슷. Math. Object, Collections 등)

- toString(): 배열의 출력

- copyOf(), copyOfRange(): 배열의 복사하여 새로운 배열을 생성해서 반환(넘치면 0으로 채움)

- fill(), setAll(): 배열 채우기

- fill(특정값), setAll(람다식)

- sort(), binarySearch(): 배열의 정렬과 검색

* binarySearch 전 sort 필요

 

cf. 순차검색과 이진검색

순차검색: 앞에서부터 1개씩

이진검색: 반을 나눠서 범위 좁히기

 

- deepToString(): 다차원 배열의 출력

- deepEquals(): 다차원 배열의 비교

- asList(배열, 가변 매개변수=개수가 정해져 있지 않음): 배열을 list로 변환

- 읽기 전용이므로 변경이 필요할 경우, 새로운 arraylist 생성 필요

List list = new ArrayList(Arrays.asList(1,2,3,4,5));

- paralle~(), spliterator(), stream(): 람다와 스트림 관련

 

Comparator, Comparable

객체 정렬에 필요한 메서드(정렬기준 제공)를 정의한 인터페이스

- Comparable: 기본 정렬기준 구현

- compareTo(Object o): 주어진 객체와 자신을 비교

- Comparator: 기본 정렬기준 외 정렬 시 사용

- compare(Object o1, Object o2): o1, o2 두 객체 비교

왼쪽이 큼: 양수, 같음: 0, 오른쪽이 큼: 음수

 

static void sort(Object[] a): 객체 배열에 저장된 객체가 구현한 Compable에 의한 정렬

예: String의 경우, Comparable 정렬 기준 기본 내장

static void sort(Object[] a, Comparator c): 지정한 Comparator에 의한 정렬

Integer: Comparable(기본 정렬 기준) 내장

 

HashSet - 순서X, 중복X

(List - 순서O, 중복O)

- HashSet: Set Interface를 구현한 대표적 collection class

- 순서를 유지하려면 LinkedHashSet Class 사용

- TreeSet: 범위 검색과 정렬에 유리한 collection class

- HashSet보다 데이터 추가, 삭제에 시간이 더 걸림

 

HashSet 주요 메서드

- 생성자: HashSet(), HashSet(Collection c), HashSet(int initialCapacity) - collection class 공간 부족하면 스스로 늘리지만, 처음 지정해주는 크기,

HashSet(int initialCapacity, float loadFactor- 언제 용량을 늘릴지 결정)

- 추가: add, addAll(합집합)

- 제거: remove, removeall(교집합), retainAll(조건부 삭제-차집합), clear(모두 삭제)

- 포함: contains, containsAll, iterator

- 기타: isEmpty, size, toArray(객체 배열로 반환)

 

HashSet

- HashSet은 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인(있으면 저장X)

- boolean add(Object o)는 저장할 객체의 equals()와 HashCode()를 호출→equals()와 hashCode()가 오버라이딩 되어있어야 함(그래야 바르게 동작)

* Source→Generate Hash and equals 활용

 

TreeSet

이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리

이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음, 각 요소(node)가 나무(tree) 형태로 연결(LinkedList의 변형-next→left, right)

 

- LinkedList

class Node{

Node next;

Object obj;

}

 

- TreeSet

class TreeSet {

TreeNode left; // 왼쪽 자식노드

Object element; // 저장할 객체

TreeNode right; // 오른쪽 자식노드

}

 

이진 탐색 트리(binary search tree)

이진트리의 유형으로, 부모보다 작은 값을 왼쪽, 큰 값을 오른쪽에 저장

데이터가 많아질수록 추가, 삭제 시간이 오래 걸림(최고조상 root부터 재비교 시작)

(0x100: null/1/0x200) ←(0x200: 0x100/5/0x300)→(0x300: 0x200/7/null)

 

TreeSet

- 저장: boolean add(Object o)

TreeSet은 중복을 허용하지 않으므로 add method 내 equals와 hashcode overriding을 자체 내장

TreeSet에 7, 4, 1, 5를 저장하면, 7을 root로 하여 크고 작음을 계속 비교하여 저장

 

TreeSet 주요 생성자와 메서드

- TreeSet(): 기본 생성자

- TreeSet(Collection c): 주어진 컬렉션을 저장하는 TreeSet 생성

- TreeSet(Comparator comp): 주어진 정렬 기준으로 정렬하는 TreeSet 생성(비교 기준이 제공되지 않을 경우, comparable 사용)

- Object first(): 정렬된 순서에서 제일 처음 객체 반환(제일 작은 값)

- Object last(): 정렬된 순서에서 제일 마지막 객체 반환(제일 큰 값)

- Object ceiling(Object o): 지정된 객체와 같은 객체를 반환, 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null

- Object floor(Object o)

- Object higher(Object o): 지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null

- Object lower(Object o)

- SortedSet subSet(Object fromElement, Object toElement): 범위 검색(from-to)의 결과 반환(to는 미포함)

- SortedSet headSet(Object toElement): 지정된 객체보다 작은 값의 객체를 반환

- SortedSet tailSet(Object fromElement): 지정된 객체보다 큰 값의 객체를 반환

 

트리 순회(tree traversal)

이진 트리의 모든 노드를 한 번씩 읽는 것

- 전위 순회(pre order): 부모 먼저 읽기

- 후위 순회(post order): 부모 나중에 읽기

- 중위 순회(im order): 부모 중간에 읽기(자식-부모-자식)

- 레벨 순회: 트리 위에서부터 순서대로

 

예: 중위 순회

 

80

 

50 95

 

35 65 100

 

10 45

 

1차 중위 순회

 

80

 

50 95

 

(10 35 45) 65 100

 

2차 중위 순회

 

80

 

(10 35 45 50 65) (95 100)

 

3차 중위 순회

 

10 35 45 50 65 80 95 100

 

→ 오름차순 정렬

 

TreeSet은 정렬과 범위검색에 유리하나 추가, 삭제에 시간이 오래 걸림

HashMap, Hashtable-순서X, 중복(키X, 값O)

순서 유지 필요→ LinkedHashMap

table- old, 동기화 o

map - new, 동기화 x

 

TreeMap(TreeSet과 동일): 범위 검색과 정렬에 유리한 Collection Class

HashMap보다 데이터 추가, 삭제에 더 시간이 걸림

 

HashMap의 key와 value

Hashing기법*으로 데이터를 저장하며, 데이터가 많아도 검색이 빠르다.

Map Interface를 구현, 데이터를 키와 값의 쌍으로 저장

key: 유일, value: 중복허용

 

HashMap map = new HashMap();

map.put(”abc”, “1234”); // 저장

map.put(”bcd”, “1111”);

map.put(”bcd”, “1234”);

 

최종 Entry(key, value)

abc, 1234

bcd 1234(최종 value로 저장)

 

비객체지향적 코드(배열)

Object[] key;

Object[] value;

 

객체지향적 코드(Entry)

Entry[] table;

 

class Entry {

Object key;

Object value;

}

 

* 해싱: 해시함수를 이용해서 해싱테이블에 데이터를 저장하고 읽어오기

해시테이블: 배열(인덱스만 알면 캐비넷에 쉽게 찾아갈 수 있음)과 링크드 리스트(변경에 유리)가 조합된 형태

= 2차원 배열, table

 

- 해시테이블에 저장된 데이터를 가져오는 과정

1. 키로 해시함수를 호출해서 해시코드를 얻는다.

2. 해시코드(해시함수의 반환값)에 대응하는 링크드리스트를 배열에서 찾는다.

3. 링크드리스트에서 키와 일치하는 데이터를 찾는다.

→ 해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야한다.

→ 서로 다른 키일지라도 같은 값의 해시코드를 반환할 수 있다.

(72년생들은 키값(주민번호)이 다를지라도 같은 출생년도 캐비넷(해시코드)에 있을 수 있음)

 

HashMap 주요 Method

- HashMap(): 기본 생성자

- HashMap(int initialCapacity): 배열 초기용량 설정

- HashMap(int initialCapacity, float loadFactor): 배열 초기용량 설정 및 용량 언제 늘릴지 지정

- HashMap(Map m): Map→HashMap

- Object put(Object key, Object value): 추가

- void putAll(Map m)

- Object remove(Object key): 삭제

- Object replace(Object key, Object value): 변경

- boolean replace(Object key, Object oldValue, Object newValue)

- Set entrySet(): entry(key+value) 읽기

- Set keySet(): key 읽기

- Collection values(): value 읽기

- Object get(Object key): value 반환

- Object getOrDefault(Object key, Object defaultValue): 없는 key 입력 시, 어떤 value 반환

- boolean containsKey(Object key): 입력된 key가 있나

- boolean containsValue(Object value): 입력된 value가 있나

- int size()

- boolean isEmpty()

- void clear()

- Object clone(): 복사

 

Collections: collection을 위한 static method 제공

(Object+static-객체, Array+static-배열)

- fill(): 채우기

- copy(): 복사

- sort(): 정렬

- binarySearch(): 검색

- synchronized~(): 동기화

 

List syncList = Collections.syncronizedList(new ArrayList());

- unmodified~(): 변경 불가, 읽기 전용

- singleton~(): 객체 1개만 저장

 

set의 경우에는 singletonSet(X), singleton(O)

- checked~(): 한 종류의 객체만 저장

 

List list = new ArrayList();

List checkedList = checkedList(list, String.class) // String만 저장 가능

checkedList.add("adc")

checkedList.add(new Integer(3)); // Error

 

 

 

 

소스 코드

🔗 HJ0216/java-practice