Java의 정석 의 책을 읽고 정리한 내용입니다.

 

📚 1. 컬렉션 프레임웍(Collections FrameWork)

컬레션 프레임웍 : 데이터 군을 저장하는 클래스들을 표준화한 설계를 뜻한다.
컬렉션 : 다수의 데이터, 데이터 그룹
프레임 웍 : 표준화된 프로그램 방식을 의미

 

컬렉션 클래스 : Vector와 같이 다수의 데이터를 저장할 수 있는 클래스

 

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

💡 참고
JDK1.5부터 Iterable인터페이스가 추가되고 이를 Collection인터페이스가 상속받도록 변경되었으나 이것은 단지 인터페이스들의 공통적인 메서드인 iterator()를 뽑아서 중복을 제거하기 위한 것에 불과하므로 상속계층도에서 별 의미가 없다.

 

인터페이스	특징	구현 클래스
List	순서가 있는 데이터의 집합, 데이터의 중복을 허용한다. ex) 대기자 명단	ArrayList, LinkedList, Stack, Vector 등
Set	순서를 유지하지 않는 데이터의 집합, 데이터의 중복을 허용하지 않는다. ex) 집합	HashSet, TreeSet 등
Map	키(key)와 값(value)의 쌍(pair)으로 이루어진 데이터 집합, 순서는 유지되지 않고, 키는 중복을 허용하지 않고, 값은 중복을 허용한다. ex)우편번호, 전화번호	HashMap, TreeMap, Hashtable, Properties 등

 

💡 참고
키(Key)란, 데이터 집합 중에서 어떤 값(value)을 찾는데 열쇠(key)가 된다는 의미에서 붙여진 이름이다. 그래서 키(Key)는 중복을 허용하지 않는다.

 

• 컬렉션 프레임웍의 모든 컬렉션 리스트들은 List, Set, Map 중의 하나를 구현하고 있으며, 구현한 인터페이스의 이름이 클래스의 이름에 포함되어 있어서 이름만으로도 클래스의 특징을 쉽게 알 수 있도록 되어있다.
• Vector, Stack, Hashtable, Properties와 같은 클래스들은 컬렉션 프레임웍이 만들어지기 이전부터 존재하던 것이기 때문에 컬렉션 프레임웍의 명명법을 따르지 않는다.
• Vector나 Hashtable과 같은 기존의 컬렉션 클래스들은 호환을 위해, 설계를 변경해서 남겨두었지만 가능하면 사용하지 않는 것이 좋다.
• 새로 추가된 ArrayList나 HashMap을 사용하는 것이 좋다.

 

✔️ Collection인터페이스

메서드	설명
boolean add(Object o), boolean addAll(Collection c)	지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가한다.
void clear()	Collection의 모든 객체를 삭제한다.
boolean contains(Object o), boolean containsAll(Collection c)	지정된 객체(o) 또는 Collection의 객체들이 Collection에 포함되어 있는지 확인한다.
boolean equals(Object o)	동일한 Collection인지 비교한다.
int hashCode()	Collection의 hash code를 반환한다.
boolean isEmpty()	Collection이 비어있는지 확인한다.
Iterator iterator()	Collection의 Iterator를 얻어서 반환한다.
boolean remove(Object o)	지정된 객체를 삭제한다.
boolean removeAll(Collection c)	지정된 Collection에 포함된 객체들을 삭제한다.
boolean retainAll(Collection c)	지정된 Collection에 포함된 객체만을 남기고 다른 객체들은 Collection에서 삭제한다. 이 작업으로 인해 Collection에 변화가 있으면 true를 없으면 false를 반환한다.
int size()	Collection에 저장된 객체의 개수를 반환한다.
Object[] toArray()	Collection에 저장된 객체를 객체배열(Object[])로 반환한다.
Object[] toArray(Object[] a)	지정된 배열에 Collection의 객체를 저장해서 반환한다.

 

Java API문서를 보면, 위와 같이 사용된 Object가 아닌 E로 표기되어있는데, E는 특정 타입을 의미하는 것으로 JDK1.5부터 추가된 지네릭스(Generics)에 의한 표기이다.
E, I, K, V를 사용하는 경우도 있는데 모두 Object타입이다.

 

✔️ List 인터페이스

List인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다.

 

메서드	설명
void add(int index, Object element), boolean addAll(int index, Collection c)	지정된 위치(Index)에 객체(element) 또는 컬렉션에 포함된 객체들을 추가한다.
Object get(int index)	지정된 위치(Index)에 있는 객체를 반환한다.
int indexOf(Object o)	지정된 객체의 위치(Index)를 반환한다. (List의 첫번째 요소부터 순방향으로 찾는다.)
int lastIndexOf(Object o)	지정된 객체의 위치(Index)를 반환한다. (List의 마지막 요소부터 역방향으로 찾는다.)
ListIterator ListIterator(), ListIterator listIterator(int index)	List의 객체에 접근할 수 있는 ListIterator를 반환한다.
Object remove(int index)	지정된 위치(Index)에 있는 객체를 삭제하고 삭제된 객체를 반환한다.
Object set(int index, Object element)	지정된 위치(Index)에 객체(element)를 저장한다.
void sort(Comparator c)	지정된 비교자(comparator)로 List를 정렬한다.
List subList(int fromIndex, int tolndex)	지정된 범위(fromIndex부터 toIndex)에 있는 객체 반환한다.

 

✔️ Set인터페이스
Set인터페이스는 중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스들을 구현하는데 사용된다. Set인터페이스르르 구현한 클래스로는 HashSet, TreeSet 등이 있다.

 

✔️ Map인터페이스

• Map인터페이스는 키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는데 사용된다. 키는 중복될 수 없지만 값은 중복을 허용한다.
• 기존에 저장된 데이터와 중복된 키와 값을 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남게된다.
• Map인터페이스를 구현한 클래스는 Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap등이 있다.
• Map이란 개념은 어떤 두 값을 연결한다는 의미에서 붙여진 이름이다.

 

메서드	설명
void clear()	Map의 모든 객체를 삭제한다.
boolean containsKey(Object key)	지정된 key객체와 일치하는 Map의 key객체가 있는지 확인한다.
boolean containsValue(Object value)	지정된 value객체와 일치하는 Map의 value객체가 있는지 확인한다.
Set entrySet()	Map에 저장되어 있는 key-value쌍을 Map.Entry타입의 객체로 저장한 Set으로 반환한다.
boolean equals(Object o)	동일한 Map인지 비교한다.
Object get(Object key)	지정한 key객체에 대응하는 value객체를 찾아서 반환한다.
int hashCode()	해시코드를 반환한다.
boolean isEmpty()	Map이 비어있는지 확인한다.
Set KeySet()	Map에 저장된 모든 key객체를 반환한다.
Object put(Object key, Object value)	Map에 value객체를 key객체에 연결(mapping)하여 저장한다.
void putAll(Map t)	지정된 Map의 모든 key-value쌍을 추가한다.
Object remove(Object key)	지정한 key객체와 일치하는 key-value쌍의 개수를 반환한다.
int size()	Map에 저장된 key-value쌍의 개수를 반환한다.
Collection values()	Map에 저장된 모든 value객체를 반환한다.

 

• values() 메서드에서 값(value)은 중복을 허용하기 때문에 Collection타입으로 반환한다.
• ketSet() 메서드에서 키(key)는 중복을 허용하지 않기 때문에 Set타입으로 반환한다.

 

✔️ Map.Entry인터페이스

• Map.Entry 인터페이스는 Map인터페이스의 내부 인터페이스이다.
• 내부 클래와 같이 인터페이스도 인터페이스 안에 인터페이스를 정의하는 내부 인터페이스(inner interface)를 정의하는 것이 가능하다.

 

메서드	설명
boolean equals(Object o)	동일한 Entry인지 비교한다.
Object getKey()	Entry의 key 객체를 반환한다.
Object getValue()	Entry의 value 객체를 반환한다.
int hashCode()	Entry의 해시코드를 반환한다.
Object setValue(Object value)	Entry의 value객체를 지정된 객체로 바꾼다.

 

📖 B. ArrayList

• ArrayList는 List인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다.
• ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일하다고 할 수 있다.
• ArrayList는 Object배열을 이용해 데이터를 순차적으로 저장한다.
• 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한다음에 저장된다.

 

메서드	설명
Arraylist()	크기가 10인 ArrayList를 생성
ArrayList(Collection c)	주어진 컬렉션이 저장된 ArrayList를 생성
ArrayList(int initialCapacity)	지정된 초기용량을 갖는 ArrayList를 생성
boolean add(Object o)	ArrayList의 마지막에 객체를 추가, 성공하면 true
void add(int index, Object element)	지정된 위치(index)에 객체를 저장
boolean addAll(Collection c)	주어진 컬렉션의 모든 객체를 저장한다.
boolean addAll(int index, Collection c)	지정된 위치부터 주어진 컬렉션의 모든 객체를 저장
void clear()	ArrayList를 완전히 비운다.
Object clone()	ArrayLIst를 복제한다.
boolean contains(Object o)	지정된 객체(o)가 ArrayList에 포함되어 있는지 확인
void ensureCapacity(int minCapacity)	ArrayList의 용량이 최소한 minCapacity가 되도록 한다.
Object get(int index)	지정된 위치(index)에 저장된 객체를 반환한다.
int indexOf(Object o)	지정된 객체가 저장된 위치를 찾아 반환한다.
boolean isEmpty()	ArrayList가 비어있는지 확인한다.
Iterator iterator()	ArrayLIst의 Iterator객체를 반환
int lastIndexOf(Object o)	객체(o)가 지정된 위치를 끝부터 역방향으로 검색해서 반환
ListIterator listIterator()	ArrayList의 ListIterator을 반환
ListIterator listIterator(int index)	ArrayList의 지정된 위치부터 시작하는 ListIterator를 반환
Object remove(int index)	지정된 위치(index)에 있는 객체를 제거
boolean remove(Object o)	지정된 객체를 제거 (성공하면 true, 실패하면 false)
boolean removeAll(Collection c)	지정한 컬렉션에 저장된 것과 동일한 객체들을 ArrayList에서 제거
boolean retainAll(Collection c)	ArrayList에 저장된 객체 중에서 주어진 컬렉션과 공통된 것들만을 남기고 나머지는 삭제
Object set(int index, Object element)	주어진 객체(element)를 지정된 위치(index)에 저장한다.
int size()	ArrayLIst에 저장된 객체의 개수를 반환한다.
void sort(Comparator c)	지정된 정렬기준으로 ArrayList를 정렬
List subList (int fromIndex, int toIndex)	fromIndex~toIndex사이에 저장된 객체를 반환
Object[] toArray()	ArrayList에 저장된 모든 객체들을 객체배열로 반환
Object[] toArray(Object[] a)	ArrayList에 저장된 모든 객체들을 객체배열 a에 담아 반환
void trimToSize()	용량을 크기에 맞게 줄인다(빈공간을 없앤다.)

 

⚠️ 주의

• Collection은 인터페이스이고, Collections는 클래스이다.

&nbps;

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

• 만일 변수 i를 증가시켜가면서 삭제하면, 한 요소가 삭제될 때마다 빈 공간을 채우기 위해 나머지 요소들이 자리이동을 하기 때문에 올바른 결과를 얻을 수 없다.
• 제어변수를 감소시켜가면서 삭제를 해야 자리이동이 발생해도 영향을 받지 않고 작업이 가능하다.

 

처음에 인스턴스를 생성할 때, 저장할 데이터의 개수를 잘 고려하여 충분한 용량의 인스턴스를 생성하는 것이 좋다.

 

💡 참고
인터페이스를 구현할 때 인터페이스에 정의된 모든 메서드를 구현해야 한다. 일부 메서드만 구현했다면 추상클래스로 선언해야한다. 그러나 JDK1.8부터 List인터페이스에 3개의 디폴트 메서드가 추가되었으며, 이 들은 구현하지 않아도 된다.

 

✔️ ArrayList remove과정

• 만일 삭제할 객체가 마지막 데이터라면, 복사할 필요없이 단순히 null로 변경해준다.

 

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

System.arraycopy(data, 3, data, 2, 2)

 

2. 데이터가 모두 한 칸씩 위로 이동하였으므로 마지막 데이터는 null로 변경해야한다.

data[size-1] = null;

 

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

size--;

 

• 배열의 중간에 위치한 객체를 추가하거나 삭제하는 경우 System.arraycopy()를 호출해서 다른 데이터의 위치를 이동시켜 줘야 하기 때문에 다루는 데이터의 개수가 많을수록 작업시간이 오래걸린다.

 

📖 C. LinkedList

• 배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어 오는데 걸리는 시간(접근 시간, access time)이 가장 빠르다는 장점을 가지고 있지만 다음과 같은 단점도 가지고 있다.

 

1. 크기를 변경할 수 없다. 
- 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야한다.
- 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.

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

• 배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.

 

• 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하면 된다.
• 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.

 

✔️ 더블 링크드 리스트

• 링크드리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.
• 이점을 보완한 것이 링크드 리스트이다.
• 더블 링크드 리스트는 링크드 리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드 리스트와 같다.
• 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트보다 많이 사용된다.

class Node{
		Node next;  	//다음 요소의 주소를 저장
		Node previous; //이전 요소의 주소를 저장
		Object obj; 	//데이터를 저장
}

• 더블 링크드 리스트의 접근성을 보다 향상 시킨것이 더블 써큘러 링크드 리스트(이중 원형 연결리스트, doubly circular linked list) 인데, 단순히 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다.
• 마지막 요소의 다음요소가 첫 번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 된다.
• 실제 LinkedList클래스는 이름과 달리 링크드 리스트가 아닌, 더블 링크드 리스트로 구현되어 있다. (링크드 리스트의 단점인 낮은 접근성을(accessability) 높이기 위해)

 

생성자 또는 메서드	설명
LinkedList()	LinkedList 객체를 생성
LinkedList(Collection c)	주어진 컬렉션을 포함하는 LinkedList 객체를 생성
boolean add(Object o)	지정된 객체(o)를 LinkedList의 끝에 추가, 저장에 성공하면 true, 실패하면 false
void add(int index, Object element)	지정된 위치에 객체를 추가
boolean addAll(Collection c)	주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가한다. 성공하면 true, 실패하면 false
boolean addAll(int index, Collection c)	지정된 위치에 주어진 컬렉션에 포함된 모든 요소를 추가, 성공하면 true, 실패하면 false
void clear()	LinkedList의 모든 요소 삭제
boolean contains(Object o)	지정된 객체가 LinkedList에 포함되어 있는지 알려줌
boolean containsAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되어 있는지 알려줌
Object get(int index)	지정된 위치의 객체를 반환
int indexOf(Object o)	지정된 객체가 저장된 위치(앞에서 몇 번째)를 반환
boolean isEmpty()	LinkedList가 비어있는지 알려준다. 비어있으면 true
Iterator iterator()	Iterator를 반환한다.
int lastIndexOf(Object o)	지정된 객체의 위치(index)를 반환(끝부터 역순검색)
ListIterator listIterator()	ListIterator를 반환한다.
ListIterator listIterator(int index)	지정된 위치에서부터 시작하는 ListIterator를 반환
Object remove(int index)	지정된 위치의 객체를 LinkedList에서 제거
boolean remove(Object o)	지정된 객체를 LinkedList에서 제거, 성공하면 true, 실패하면 false
boolean removeAll(Collection c)	지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
boolea retainAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되어 있는지 확인
Object set(int index, Object element)	지정된 위치의 객체를 주어진 객체로 바꿈
int size()	LinkedList에 저장된 객체의 수를 반환
List subList(int fromIndex, int toIndex)	LinkedList의 일부를 List로 반환
Object[] toArray()	LinkedList에 저장된 객체를 배열로 반환
Object[] toArray(Obejct[] a)	LinkedList에 저장된 객체를 주어진 배열에 저장하여 반환
void addFirst(Object o)	LinkedList의 맨 앞에 객체를 추가
void addLast(Object o)	LinkedList의 맨 끝에 객체를 추가
Iterator descendingIterator()	역순으로 조회하기 위한 DescendingIterator를 반환
Object getFirst()	LinkedList의 첫번쨰 요소를 반환
Obejct getLast()	LinkedList의 마지막 요소를 반환
boolean offerFirst(Object o)	LinkedList의 맨 앞에 객체를 추가, 성공하면 true
boolean offerLast(Object o)	LinkedList의 맨 끝에 객체를 추가, 성공하면 true
Object peekFirst()	LinkedList의 첫번쨰 요소를 반환
Object peekLast()	LinkedList의 마지막 요소를 반환
Object pollFirst()	LinkedList의 첫번쨰 요소를 반환하면서 제거
Object pollLast()	LinkedList의 마지막 요소를 반환하면서 제거
Object pop()	removeFirst()와 동일
void push(Object o)	addFirst()와 동일
Object removeFirst()	LinkedLIst의 첫번째 요소를 제거
Object removeLast()	LinkedList의 마지막 요소를 제거
boolean removeFirstOccurrence(Object o)	LinkedList에서 첫번째로 일치하는 객체를 제거
boolean removeLastOccurerence(Object o)	LinkedList에서 마지막으로 일치하는 객체를 제거

 

🔔 결론
1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.

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

 

배열의 경우 인덱스가 n인 요소의 값을 얻어 오고자 한다면 단순히 아래와 같은 수식을 계산함으로써 해결된다.

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터의 타입 크기

 

• LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라, 처음부터 n번째 데이터까지 차례로 따라가야만 원하는 값을 얻을 수 있다.
• LinkedList 는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어오는 시간, 즉 접근시간이 길어진다는 단점이 있다.

컬렉션	읽기(접근시간)	추가/삭제	비 고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름. 비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

 

📣 그러면?
ArrayList : 다루고자 하는 데이터의 개수가 변하지 않는 경우 사용한다.
LInkedList : 데이터 개수의 변경이 잦을 때 사용한다.

 

✔️ 두 클래스의 장점을 이용해서 두 클래스를 조합해서 사용하는 방법

• 처음에 작업하기 전에 데이터를 저장할 때는 ArrayList를 사용한 다음, 작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 수 있다.

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

LinkedList ll = new LinkedList(al);
for(int i=0; i<100000;i++) ll.add(500,"X");

컬렉션 프레임웍에 속한 대부분의 컬렉션 클래스들은 이처럼 서로 변환이 가능한 생성자를 제공한다. 이를 이용하면 간단히 다른 컬렉션 클래스로 데이터를 옮길 수 있다.

 

📖 D. Stack과 Queue

• 스택은 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하다.
• 큐는 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

 

✔️ Stack의 메서드

메서드	설명
boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환, pop()과 달리 Stack에서 객체를 꺼내지 않음.(비어있을 때는 EmptyStackException 발생)
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다. (비어있을 때는EmptyStackException 발생)
Object push(Object item)	Stack에 객체(item)를 저장한다.
int search(Object o)	Stack에서 주어진 객체를찾아서 그 위치를 반환, 못찾으면 -1을 반환 (배열과 달리 위치는 0이 아닌 1부터 시작)

 

✔️ Queue의 메서드

메서드	설명
boolean add(Object o)	지정된 객체를 Queue에 추가한다. 성공하면 true를 반환, 저장공간이 부족하면 IIIegalStateException 발생
Object remove()	Queue에서 객체를 꺼내 반환, 비어있으면 NoSurchElementException발생
Object element()	삭제없이 요소를 익어온다. peek과 달리 Queue가 비어있을 떄 NoSuchElementException 발생
boolean offer(Object o)	Queue에 객체를 저장, 성공하면 true, 실패하면 false를 반환
Object poll()	Queue에서 객체를 꺼내서 반환, 비어있으면 null을 반환
Object peek()	삭제없이 요소를 읽어온다. Queue가 비어있으면 null을 반환

 

✔️ 스택과 큐의 활용

스택의 활용 예 - 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로

큐의 활용 예 - 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)

 

✔️ PriorityQueue

• Queue인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것 부터 꺼내게 된다는 특징이 있다.
• null을 저장할 수 없다. null을 저장하면 NullPointerException이 발생한다.
• PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장한다. (힙 : 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징이 있다.)

 

💡 참고

• 자료구조 힙(heap)은 JVM의 힙(heap)과 이름만 같을 뿐 다른것이다.

 

import java.util.*;

public class PriorityQueueEx {

	public static void main(String[] args) {
		Queue pq = new PriorityQueue();
		pq.offer(3); // pq.offer(new Integer(3)); 오토박싱
		pq.offer(1);
		pq.offer(5);
		pq.offer(2);
		pq.offer(4);
		System.out.println(pq); // pq의 내부 배열을 출력

		Object obj = null;

		// PriorityQueue에 저장된 요소를 하나씩 꺼낸다.
		while ((obj = pq.poll()) != null)
			System.out.println(obj);

	}

}

• 객체를 저장할 수도 있는데 그럴 경우 각 객체의 크기를 비교할 수 있는 방법을 제공해야 한다.
• 컴파일러가 Integer로 오토박싱 해준다.
• Integer와 같은 Number의 자손들은 자체적으로 숫자를 비교하는 방법을 정의하고 있기 때문에 비교 방법을 지정해주지 않아도 된다.

 

✔️ Deque(Double - Ended Queue)

• Queue의 변형으로 한쪽 끝으로만 추가/삭제할 수있는 Queue와 달리, Deque(덱, 또는 디큐라고 읽음)은 양쪽 끝에서 추가/삭제가 가능하다.
• Deque의 조상은 Queue이며, 구현체로는 ArrayDeque과 LinkedList등이 있다.
• 덱은 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다.

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()
peekLast()	-	peek()

• offer() : 저장
• poll() : 추출
• offerLst : 끝에 저장
• pollLast : 끝에서 삭제
• pollFirst : 앞에서 삭제
• offerFirst : 앞에 저장

 

📖 E. Iterator, ListIterator, Enumeration

• Iterator, ListIterator, Enumeration 모두 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스이다.
• Enumeration은 Iterator의 구버전이며, ListIterator는 Iterator의 기능을 향상 시킨 것이다.

 

✔️ Iterator

메서드	설명
boolean hasNext()	읽어 올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환한다.
Object next()	다음 요소를 읽어 온다. next()를 호출하기 전에 hasNext()를 호출해서 읽어 올 요소가 있는지 확인하는 것이 안전하다.
void remove()	next()로 읽어 온 요소를 삭제한다. next()를 호출한 다음에 remove()를 호출해야한다. (선택적 가능)

 

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

➡

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

 

StringBuffer sb = new StringBuffer();
sb.append("A");
sb.append("B");

➡

StringBuffer sb = new StringBuffer();
sb.append("A").append("B"); // StringBuffer append(String str)

• 위와 같이 되는 이유는 append 메서드가 수행 결과로 StringBuffer를 리턴하기 때문에 가능하다.

 

✔️ ListIterator와 Enumeration

• Enumeration은 컬렉션 프레임웍이 만들어지기 전에 사용하던 것으로 Iterator의 구버전이다.
• Enumeration 대신, Iterator를 사용하자!
• ListIterator : Iterator를 상속받아서 기능을 추가한 것

 

Emumeration : Iterator의 구버전
ListIterator : Iterator에 양방향 조회기능추가(List를 구현한 경우만 사용가능)

 

Enumeration

메서드	설명
boolean hasMoreElements()	읽어 올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환한다. Iterator의 hasNext()와 같다.
Object nextElement()	다음 요소를 읽어온다. nextElement()를 호출하기전에 hasMoreElements()를 호출해서 읽어올 요소가 남아있는지 확인하는 것이 안전한다. Iterator의 next()와 같다.

 

ListIterator

메서드	설명
void add(Obejct o)	컬렉션에 새로운 객체(o)를 추가한다. (선택적 기능)
boolean hasNext()	읽어 올 다음 요소가 있는지 확인한다. 있으면 true, 없으면 false를 반환
boolean hasPrevious()	읽어 올 이전 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환
Object next()	다음 요소를 읽어온다.next()를 호출하기 전에 hasNext()를 호출해서 읽어올 요소가 있는지 확인하는 것이 안전하다.
Object previous()	이전 요소를 읽어온다. previous()를 호출하기 전에 hasPrevious()를 호출해서 읽어 올 요소가 있는지 확인하는 것이 안전하다.
int nextIndex()	다음 요소의 index를 반환한다.
int previousIndex()	이전 요소의 index를 반환한다.
void remove()	next()또는 previous()로 읽어 온 요소를 삭제한다. 반드시 next()나 previous()를 호출한 후에 이 메서드를 호출해야 한다.(선택적 기능)
void set(Object o)	next()또는 previous()로 읽어 온 요소를 지정된 객체(o)로 변경한다. 반드시 next()나 previous()를 먼저 호출한 다음에 이 메서드를 호출해야한다. (선택적 기능)

• ListIterator는 양방향으로 이동하기 때문에, 이동하기 전에 반드시 has Next()나 hasPrevious()를 호출해서 이동할 수 있는지 확인해야 한다.

import java.util.*;

public class ListIteratorEx1 {

	public static void main(String[] args) {
		ArrayList list = new ArrayList();
		list.add("1");
		list.add("2");
		list.add("3");
		list.add("4");
		list.add("5");

		ListIterator it = list.listIterator();

		while (it.hasNext()) {
			System.out.print(it.next()); // 순방향 진행
		}
		System.out.println();

		while (it.hasPrevious()) {
			System.out.print(it.previous()); // 역방향
		}
		System.out.println();

	}

}

 

Iterator를 어떻게 구현하는지 예제

import java.util.*;

public class MyVector2 extends MyVector implements Iterator {
	int cursor  = 0;
	int lastRet = -1;
	
	public MyVector2(int capacity) {
		super(capacity);		
	}
	
	public MyVector2() {
		this(10);		
	}

	public String toString() {
		String tmp = "";
		Iterator it = iterator();

		for(int i=0; it.hasNext();i++) {
			if(i!=0) tmp+=", ";
			tmp += it.next(); 	// tmp += next().toString();
		}

		return "["+ tmp +"]";		
	}

	public Iterator iterator() {
		cursor=0;		// cursor와 lastRet를 초기화 한다.
		lastRet = -1;
		return this;		
	}	
	
	public boolean hasNext() {
	    return cursor != size();
	}
	
    public Object next(){
		Object next = get(cursor);
		lastRet = cursor++;
		return next;
    }
	
	public void remove() {
         // 더이상 삭제할 것이 없으면 IllegalStateException를 발생시킨다.
		if(lastRet==-1) {  
			throw new IllegalStateException();
		} else {
			remove(lastRet);
			cursor--;           // 삭제 후에 cursor의 위치를 감소시킨다.
			lastRet = -1;		// lastRet의 값을 초기화 한다.	
		}
	}		
}

• remove()는 next()로 읽어 온 객체를 삭제하는 것이기 때문에 remove()를 호출하기 전에는 반드시 next()가 호출된 상태이어야 한다.

 

import java.util.*;

public class MyVector2Test {

	public static void main(String[] args) {
			MyVector2 v = new MyVector2();
			v.add("0");
			v.add("1");
			v.add("2");
			v.add("3");
			v.add("4");
			
			System.out.println("삭제 전 : "+v);
			Iterator it = v.iterator();
			it.next();
			it.remove();
			it.next();
			it.remove();
			
			System.out.println("삭제 후 : "+v);

	}

}

삭제 전 : [0, 1, 2, 3, 4]
삭제 후 : [2, 3, 4]

 

📖 F. Arrays

✔️ 배열의 복사-copyOf(), copyOfRange()

• copyOf() : 배열 전체 복사해서 새로운 배열을 만들어 반환한다.
• copyOfRange() : 배열의 일부를 복사해서 새로운 배열을 만들어 반환한다.

int[] arr = {0,1,2,3,4};
int[] arr2 = Arrays.copyOf(arr,arr.length); //arr2 =[0,1,2,3,4]
int[] arr3= Arrays.copyOf(arr,3);  //arr3 = [0,1,2]
int[] arr4 = Arrays.copyOf(arr,7); //arr4 = [0,1,2,3,4,0,0]
int[] arr5 = Arrays.copyOfRange(arr, 2, 4); //arr5 =[2,3] <-4는 불포함
int[] arr6 = Arrays.copyOfRange(arr,0,7); //arr6 =[0,1,2,3,4,0,0]

 

✔️ 배열 채우기 - fill(), setAll()

• fill() : 배열의 모든 요소를 지정된 값을 채운다.
• setAll() : 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받는다.
  • setAll() 메서드는 람다식이 반환한 임의의 정수로 배열을 채운다.

int[] arr= new int[5];
Arrays.fill(arr,9);  // arr=[9,9,9,9,9]
Arrays.setAll(arr, () -> (int)(Math.random()*5)+1); //arr=[1,5,2,1,1]

 

✔️ 배열의 정렬과 탐색 - sort(), binarySearch()

• sort()는 배열을 정렬할 때, 그리고 배열에 저장된 요소를 검색할 때는 binarySearch()를 사용한다.
• binarySearch()는 배열에서 지정된 값이 저장된 위치(index)를 찾아서 반환하는데, 반드시 배열이 정렬된 상태이어야 올바른 결과를 얻는다.
• 만일 검색한 값과 일치하는 요소들이 여러 개있다면, 이 중에서 어떤 것의 위치가 반환될지는 알 수 없다.

int[] arr= {3,2,0,1,4};
int idx = Arrays.binarySearch(arr, 2) : // idx = -5 ⬅ 잘못된 결과

Arrays.sort(arr); //배열 arr을 정렬한다.
System.out.println(Arrays.toString(arr));  //[0,1,2,3,4]
int idx =Arrays.binarySearch(arr, 2);  //idx=2 ⬅ 올바른 결과

 

✔️ 배열의 비교와 출력 - equals(), toString()

• toString()은 배열의 모든 요소를 문자열로 편하게 출력할 수 있다.
• toString()은 일차원 배열에만 사용할 수 있으므로, 다차원배열에는 deepTo String()을 사용해야 한다.

int[] arr= {0,1,2,3,4};
int[][] arr2D = {{11,12}, {21,22}};

System.out.println(Arrays.toString(arr)); //[0,1,2,3,4]
System.out.println(Arrays.deepToString(arr2D)); //[[11,12], [21,22]]

String[][] str2D = new String[][] {{"aaa","bbb"}, {"AAA","BBB"}};
String[][] str2D2 = new String[][] {{"aaa","bbb"}, {"AAA","BBB"}};

System.out.println(Arrays.equals(str2D, str2D2)); //false
System.out.println(Arrays.deepEquals(str2D, str2D2)); //true;

• 다차원 배열은 배열의 배열의 형태로 구성하기 때문에 equals()로 비교하면 ,문자열을 비교하는 것이 아니라 배열에 저장된 배열의 주소를 비교하게 된다.
• 서로 다른 배열은 항상 주소가 다르므로 false를 결과로 얻은다.

 

✔️ 배열을 List로 변환 - asList(Object ...a)

• asList()는 배열을 List에 담아서 반환한다. 매개변수의 타입이 가변인수라서 배열 생성없이 저장할 요소들만 나열하는 것도 가능하다.

List list = Arrays.asList(new Integer[]{1,2,3,4,5});
List list = Arrays.asList(1,2,3,4,5);
list.add(6); // UnsupportedOperationException 예외발생

• 한 가지 주의할 점은 asList()가 반환한 List의 크기를 변경할 수 없다는 것이다.
• 즉 추가, 또는 삭제가 불가능하다.
• 저장된 내용은 변경가능하다.
• 만일 크기를 변경할 수 있는 List가 필요하다면 다음과 같이 하면된다.

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

 

✔️ parallelXXX(), spliterator(), stream()

• parallel로 시작하는 이름의 메서드들이 있는데, 이 메서드들은 보다 빠른 결과를 얻기 위해 여러 쓰레드가 작업을 나누어 처리하도록 한다.
• spliterator()는 여러 쓰레드가 처리할 수 있게 하나의 작업을 여러 작업으로 나누는 Spliterator를 반환하며 stream()은 컬렉션을 스트림으로 변환한다.

 

import java.util.*;
public class ArraysEx {

	public static void main(String[] args) {
		int[] arr = {0,1,2,3,4};
		int[][] arr2D = {{11,12,13}, {21,22,23}};
		
		System.out.println("arr="+Arrays.toString(arr));
		System.out.println("arr2D="+Arrays.deepToString(arr2D));
		
		int[] arr2= Arrays.copyOf(arr,arr.length);
		int[] arr3 = Arrays.copyOf(arr, 3);
		int[] arr4 = Arrays.copyOf(arr, 7);
		int[] arr5= Arrays.copyOfRange(arr, 2, 4);
		int[] arr6= Arrays.copyOfRange(arr, 0, 7);
		
		System.out.println("arr2="+Arrays.toString(arr2));
		System.out.println("arr3="+Arrays.toString(arr3));
		System.out.println("arr4="+Arrays.toString(arr4));
		System.out.println("arr5="+Arrays.toString(arr5));
		System.out.println("arr6="+Arrays.toString(arr6));
		
		int[] arr7 = new int[5];
		Arrays.fill(arr7, 9); //arr=[9,9,9,9,9]
		System.out.println("arr7"+Arrays.toString(arr7));
		
		Arrays.setAll(arr7, i -> (int)(Math.random()*6)+1);
		System.out.println("arr7"+Arrays.toString(arr7));
		
		for(int i : arr7){
			char[] graph = new char[i];
			Arrays.fill(graph, '*');
			System.out.println(new String(graph)+i);
		}
		
		String[][] str2D = new String[][] {{"aaa","bbb"}, {"AAA","BBB"}};
		String[][] str2D2 = new String[][] {{"aaa","bbb"}, {"AAA","BBB"}};
		
		System.out.println(Arrays.equals(str2D, str2D2));  //false
		System.out.println(Arrays.deepEquals(str2D, str2D2)); //true
		
		char[] chArr ={'A','D','C','B','E'};
		
		System.out.println("chArr="+Arrays.toString(chArr));
		System.out.println("index of B ="+Arrays.binarySearch(chArr, 'B'));
		System.out.println("After Sorting");
		Arrays.sort(chArr);
		System.out.println("chArr="+Arrays.toString(chArr));
		System.out.println("index of B ="+Arrays.binarySearch(chArr, 'B'));
	}	

}

arr=[0, 1, 2, 3, 4]
arr2D=[[11, 12, 13], [21, 22, 23]]
arr2=[0, 1, 2, 3, 4]
arr3=[0, 1, 2]
arr4=[0, 1, 2, 3, 4, 0, 0]
arr5=[2, 3]
arr6=[0, 1, 2, 3, 4, 0, 0]
arr7[9, 9, 9, 9, 9]
arr7[1, 2, 1, 6, 1]
****1
*2
**1
***6
*****1
false
true
chArr=[A, D, C, B, E]
index of B =-2
After Sorting
chArr=[A, B, C, D, E]
index of B =1