Collection 인터페이스

1. Collection 

1-1. Collection이란? 

• 많은 데이터들을 효과적으로 처리할 수 있는 방법을 제공하는 클래스들의 집합
• Collection 인터페이스는 List, Set, Queue 로 크게 3가지 상위 인터페이스로 분류 된다.
  (컬렉션은 List, Set, Queue에서 사용하는 공통사항을 뽑아 만든 인터페이스) 
• List, Set, Queue는 Collection 인터페이스를 상속 받지만, 구조 상의 이유로 Map은 따로 구현되어 있다.

1-2. Collection을 사용하는 이유

• 일관된 API: Collection 에서 제공하는 규격화된 메소드를 사용함으로 일관된 사용과 유지보수가 가능하다.
• 프로그래밍 비용 감소: 이미 제공된 자료구조를 활용하는 것으로 low-level의 알고리즘을 고민할 시간과 노력을 아낄 수 있다.
• 프로그래밍 속도 및 품질 향상: 필요한 자료구조를 사용함으로써 프로그래밍의 속도 뿐만 아니라 기동 속도, 품질 향상을 기대할 수 있다.

1-3. Collection 주요 인터페이스 

인터페이스	설명	구현 클래스
List<E>	순서가 있는 데이터의 집합으로, 데이터의 중복을 허용한다.	ArrayList, LinkedList, Stack, Queue, Vector
Set<E>	순서가 없는 데이터의 집합으로, 데이터 중복 허용하지 않는다.	HashSet, TreeSet
Map<K, V>	키와 값이 쌍를 이루어 구성되는 데이터 집합으로 순서가 없다. 키의 중복은 허용되지 않지만, 값의 중복은 허용된다.	HashMap, TreeMap, Properties

1-4. Collection 메서드 

• void clean() : Collection의 모든 요소를 삭제
• boolean remove(Object) : 해당 객체의 요소를 삭제
• boolean contains(Object) : 해당 객체를 포함하고 있는지 확인
• boolean isEmpty() : 해당 Collection이 비어있는지 확인
• int size() : 요소의 갯수 반환
• Object[] toArray() : 컬렉션을 Object배열로 변환
• Iterator<E> iterator() : 해당 Collection을 반복자(iterator)로 변환
  • List, Set구현한 모든 클래스에서 사용 가능. 하지만 iterator사용하는 것 보다 향상된 for문 쓰는 것을 권장
  • boolean hasNext() : 다음 요소가 있으면 true, 없으면 false
  • E ar.next() : 다음 요소를 반환

 

2. List 

2-1. List 인터페이스

• List는 객체를 일렬로 늘어놓은 구조로 이루어져 있다.
• 순서가 있는 데이터의 집합으로 같은 데이터의 중복 저장을 허용한다.
• List 인터페이스를 구현한 모든 클래스는 저장 순서가 유지된다.
• List 컬렉션 인터페이스에는 객체를 추가(add), 검색(contain, get, size), 삭제(remove, clear) 기능의 메서드가 선언되어 있다. 그러므로 List 컬렉션 인터페이스를 상속해서 구현하는 클래스는 해당 기능을 오버라이드 해야한다.
• 구현 클래스: ArrayList, LinkedList, Vector, Stack, Queue.. 

2-2. ArrayList

• ArrayList는 인스턴스를 생성하게 되면 내부적으로 10칸짜리 배열을 생성해서 관리한다.
• 일반 배열과 ArrayList는 인덱스로 객체를 관리하는 공통점이 있지만, 크기를 동적으로 늘릴 수 있는 차이가 있다.
• 배열의 단점을 보완하기 위해 만들어졌기 때문에 크기 변경, 요소 추가/삭제/정렬 기능들을 메소드로 제공하고 있다. 단, 기능적으로 수행되는 것이지 속도가 빨라지는 것은 아니다.
• ArrayList 장점: 인덱스가 있으므로 객체 검색, 맨 마지막에 객체 추가 등에서 좋은 성능을 발휘한다.
• ArrayList 단점: 객체 삭제와 삽입이 빈번하게 일어나는 곳에서 ArrayList보다 LinkedList를 사용하는 것이 좋다.
  (배열처럼 ArrayList에서 특정 인덱스의 객체를 제거하게 되면, 제거한 객체의 인덱스부터 마지막 인덱스까지 모두 앞으로 1칸씩 앞으로 이동함

2-3. LinkedList 

• ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하지만, LinkedList는 저장되는 데이터들이 연속된 공간에 저장되는 것이 아니라 각 데이터를 링크(Link)를 연결하여 구성한다.
• 스택, 큐, 양방향 큐 등을 구성하기 용이하다.
• 장점: 데이터의 삽입, 삭제가 빈번할 경우 연결되는 링크 정보만 수정하면 되기 때문에 ArrayList보다 더 적합하다.
  (특정 인덱스의 객체를 제거하게 되면, 제거되는 인덱스의 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. ArrayList는 제거되는 인덱스를 기준으로 뒤에 있는 객체가 한칸씩 이동 했었던 점과 차이가 있다.)
• LinkecdList의 종류 
  • 단일 연결 리스트: 저장한 요소가 순서를 유지하지 않고 저장되지만 이러한 요소들 사이를 링크로 연결하여 구성하며 마치 연결된 리스트 형태인 것 처럼 만든 자료구조이다. 요소의 저장과 삭제 시 다음 요소를 가리키는 참조 링크만 변경하면 되기 때문에 요소의 저장과 삭제가 빈번히 일어나는 경우 ArrayList보다 성능면에서 우수하다.
  • 이중 연결 리스트: 단일 연결 리스트는 다음 요소만 링크하는 반면 이중 연결 리스트는 이전 요소도 링크하여 이전 요소로 접근하기 쉽게 고안된 자료구조 이다.

public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        List<String> linkedList = new LinkedList<>();
        //다형성 적용하여 선언 가능
        List list = new ArrayList();
        Collection clist = new ArrayList();

        //1. add(): 요소 추가 
        arrayList.add("apple");
        //arrayList.add(123); //제네릭 에러
        linkedList.add("apple");

        //원하는 인덱스에 값 추가도 가능
        arrayList.add(1, "banana");
        linkedList.add(1, "banana");

        //2. toString() 메소드가 오버라이딩 되어 있음
        System.out.println("arrayList : " + arrayList);
        System.out.println("linkedList : " + arrayList);

        //3. get(): 인덱스에 해당하는 값을 가져옴
        System.out.println(arrayList.get(0));
        System.out.println(linkedList.get(1));

        //4. size(): 저장된 요소의 개수 확인
        System.out.println(arrayList.size());
        System.out.println(linkedList.size());

        //5. remove(): 요소를 제거, 제거된 요소 인덱스 리턴
        linkedList.remove(0); //인덱스로 가능
        arrayList.remove("apple"); //값으로 가능
        System.out.println("arrayList : " + arrayList);
        System.out.println("linkedList : " + linkedList);

        //6. set(): 요소 수정
        arrayList.set(0, "fineapple");
        linkedList.set(0, "fineapple");
        System.out.println("arrayList : " + arrayList);
        System.out.println("linkedList : " + linkedList);

        //7. clear(): 리스트 내 요소를 모두 제거
        arrayList.clear();
        //linkedList.clear();

        //8. isEmpty(): list가 비어있는지를 확인
        System.out.println(arrayList.isEmpty()); //true
        System.out.println(linkedList.isEmpty()); //false

        //9. 향상된 for문 사용도 가능하다
        for(String a : arrayList) System.out.println(a);
        for(String s : linkedList) System.out.println(s);
    }

 

리스트 생성 시 변수 타입 선택에 따른 차이점 (다형성)

LinkedList<String> linkedList = new LinkedList<>();	List<String> linkedList = new LinkedList<>();
LinkedList 고유 메서드 사용 가능 addFirst(), removeLast() ..	List 인터페이스의 메서드만 사용 가능 add(), remove() ..
단, LinkedList 전용이므로 다른 구현체로 바꾸기 어려움	ArrayList 등 다른 List 구현체로 쉽게 변경 가능한 유연한 코드

 

2-4. Stack

• 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조 
• LIFO(Last In First Out) 방식으로 자료를 처리한다.
• 리스트 계열 클래스인 Vector 클래스를 상속받아 구현됨
  • 하지만 Java에서 Stack이 Vector를 상속한 것은 설계적으로 최선은 아니라고 평가받는다. 
  • Vector는 동기화를 지원하는 옛날 List 구현체라서, 성능상 불필요한 오버헤드가 발생할 수 있기 때문에 요즘은 Deque(특히 ArrayDeque)을 사용해서 Stack을 구현하는 게 더 추천된다. 
• 메소드가 호출될 때 해당 구조로 메모리에 올라가게 된다.
• Top/Bottom
  • Top: 스택의 할당된 기억공간에서 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소
  • Bottom: 스택의 가장 밑바닥
• 오버플로/언더플로
  • 오버플로(Overflow): 스택의 모든 기억공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 발생
  • 언더플로(Underflow): 더이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 발생

import java.util.Stack; //import
Stack<Element> stack = new Stack<>(); //int형 스택 선언

stack.push(값);    // 값 추가
stack.pop();       // stack의 첫번째 값을 반환하고 제거, 비어있다면 null
stack.peek();      // stack의 가장 상단의 값 반환만하고 제거X
stack.clear();     // stack의 전체 값 제거 (초기화)

stack.size();      // stack의 크기 출력
stack.empty();     // stack이 비어있는지 check (비어있다면 true)
stack.contains(1);  // stack에 1이 있는지 check (있다면 true)

2-5. Queue

• 큐는 Front 포인터와 Rear 포인터를 정하고 한 곳에는 삭제만, 다른 한 곳에서는 삽입 연산만 처리한다.
• FIFO(First In First Out) 방식으로 자료를 처리한다 .
• Queue 인터페이스를 상속받는 하위 인터페이스 들은 Deque, BlockingQueue, BlockingDeque, TreansferQueue 등 다양하지만 대부분의 큐는 LinkedList를 이용한다.
• LinkedList는 List와 Queue 둘 다 지원하는 클래스. 
  • LinkedList는 내부적으로 연결 리스트(Linked List) 구조를 사용해서 요소를 저장
  • List 인터페이스를 구현해서 get(index), add(index, element) 같은 인덱스 기반 접근이 가능
  • Queue 인터페이스도 구현해서 offer(), poll(), peek() 같은 FIFO 방식 접근이 가능해
• Priority Queue
  • 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 원소는 비교가 가능한 기준이 있어야함
  • 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음

import java.util.LinkedList; //import
import java.util.Queue; //import

// Queue 자체로는 인터페이스 이기 때문에 인스턴스 생성이 불가능하다
// Queue<String> que = new Queue<>(); //에러남
Queue<Element> queue = new LinkedList<>() //큐 선언

queue.offer(값);  // 값 추가
queue.poll();     // queue에 첫번째 값을 반환하고 제거, 비어있다면 null
queue.peek();     // queue의 첫번째 값 반환만하고 제거X
queue.clear();    // queue 초기화

queue.size();     // queue의 크기 출력
queue.isEmpty();  // queue가 비어있는지 check (비어있다면 true)

//우선순위큐 
PriorityQueue<Integer> queSmall = new PriorityQueue<>(); //작은 수가 우선
PriorityQueue<Integer> queBig = new PriorityQueue<>(Collections.reverseOrder()); //큰 수가 우선 
queBig.offer(1);
queBig.offer(9);
queBig.offer(7);
System.out.println(queBig.poll()); //9
System.out.println(queBig.poll()); //7
System.out.println(queBig.poll()); //3

 

add()와 offer()의 차이 ▼

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

 

3. Set

3-1. Set 인터페이스

 

• Set이란 집합처럼 중복되지 않는 데이터를 저장하는 자료구조
• 데이터 저장 순서가 보장되지 않는다. 
• 종류: HashSet, LinkedHashSet, TreeSet 등 
• Set 사용 사례
  • 유일한 값을 저장하고 싶을 때
  • 중복 데이터 제거가 필요할 때

3-2. Set의 종류

• HashSet: 해시 테이블을 이용하여 데이터를 저장하는 구조, 중복X 순서X
• LinkedHashSet: HashSet과 동일한 구조를 가지지만 데이터 삽입 순서대로 출력된다. 
• TreeSet: 데이터가 정렬된 상태로 저장되는 이진 검색 트리의 형태로 요소를 저장한다.

//HashSet (순서 보장X)
HashSet<Integer> set = new HashSet<Integer>(); 

set.add(1);    //값 추가
set.remove(1); //값 1 제거
set.clear();   //모든 값 제거
set.contains(1); //boolean 리턴 

//출력	
Iterator iter = set.iterator();	// Iterator 사용
while(iter.hasNext()) {//값이 있으면 true 없으면 false
    System.out.println(iter.next()); //순서 보장되지 않음 
}

//LinkedHashSet: 등록 순서대로 저장 
LinkedHashSet<String> lhset = new LinkedHashSet<>();
lhset.add("banana");
lhset.add("orange");
lhset.add("apple");
System.out.println("lhset : " + lhset); //banana, orange, apple 

//TreeSet : 자동 오름차순 정렬
TreeSet<String> tset = new TreeSet<>();
tset.add("banana");
tset.add("orange");
tset.add("apple");
System.out.println("tset : " + tset); //apple, banana, orange

4. Map 

4-1. Map 인터페이스 

• Map은 키와 값을 하나의 쌍으로 저장하는 자료구조
  • 키(Key) : 키를 통해 값에 접근할 수 있다, 키는 고유한 값으로 중복 불가  
  • 값(Value) : 값에 매핑된 데이터, 값은 중복될 수 있다. 
• 데이터 저장 순서가 보장되지 않는다. 
• Map은 Collection 인터페이스와는 다른 저장 방식을 가지고 있기 때문에 하위 인터페이스에 포함되지 않는다.
  • Collection은 단일 값을 저장하는 자료 구조이고, Map은 키-값의 쌍을 저장하는 자료구조 이다. 
  • 따라서 Map은 Collection의 하위 클래스가 아니고 독립적인 구조로 존재
• 종류: HashMap, HashTable(-Properties), TreeMap 등
• Map 사용 사례 
  • 데이터의 매핑 관계를 표현할 때 (예: 학생 ID와 이름)
  • 빠른 검색, 삽입, 삭제가 필요한 경우

4-2. HashMap

• Map 인터페이스를 구현하고 있는 클래스 중에 가장 자주 쓰이는 클래스
• 저장은 느리지만 Hashing 이라는 해시 함수를 이용해서 데이터를 해시 테이블에 저장하기 때문에 검색 측면에서 뛰어나다.
• 중복된 키 값에 값을 저장하면 기존의 값에 새로운 값이 덮어 씌어진다.

HashMap<Integer,String> map = new HashMap<>();   //HashMap 선언 및 생성
map.put(1,"사과");   //값 추가
map.put(1,"바나나"); //키 중복 저장 안됨 -> 값 갱신 
map.put(2,"바나나"); //값 중복 저장 가능  
map.get(1);          //key값 1의 value얻기 : 바나나 
map.remove(1);       //key값 1 제거
map.clear();         //모든 값 제거

map.size();                  //개수 리턴 
map.containsKey(1)           //key값 1 검색 -> true
map.containsValue("바나나");  //value값 "바나나" 검색 -> false

//getOrDefault(map에서 찾을 key값(있으면 key값의 value 리턴), map에 해당하는 key값이 없으면 리턴할 디폴트값);
map.getOrDefault(1, "없음");  // map의 key값으로 1이 있으면 "사과" 리턴, 없으면 "없음" 리턴   
 
// map 출력
for (String key : map.keySet()) {
        String value = map.get(key);
        System.out.println("[key]:" + key + ", [value]:" + value);
}

//keySet()을 이용해서 키만 따로 set으로 만들고,
Iterator<String> keyIter = map.keySet().iterator();

while(keyIter.hasNext()) {
    String key = (String)keyIter.next();
    String value = (String) hmap2.get(key);
    System.out.println(key + " = " + value);
}