[JAVA] 자바의 정석 _ Collection Framework/ List(ArrayList, LinkedList), Stack, Queue, Iterator

 * collections framework

- 컬렉션(collection) : 여러 객체(데이터)를 모아놓은 것

- 프레임웍(framework) : 표준화, 정형화된 체계적인 프로그래밍 방식 , 생산성 증가 유지보수 편해짐.

- 라이브러리(library) : 단순 기능 제공하는 이미 만들어진 툴.

- 컬렉션 프레임웍 : 컬렉션을 다루기 위한 표준화된 프로그래밍 방식

                               컬랙션을 쉽고 편리하게 다룰 수 있는 다양한 클래스 제공 (저장, 삭제, 검색, 정렬)

- java.util 패키지에 포함.

핵심 인터페이스

- List : 순서가 있는 데이터의 집합, 중복 허용. ArrayList, LinkedList, Stack, Vector 등

- Set : 순서를 유지하지 않는 데이터의 집합, 중복 허용 X. HashSet, TreeSet 등

- Map : 키(key)와 값(value)의 쌍으로 이루어진 데이터의 집합. 순서 X 키는 중복 X 값은 중복 O. HashMap, TreeMap, Hashtable, Properties 등

List, Set의 공통부분 --> Collection 이라는 Interface 만듦.

 

 * List 인터페이스 - 순서O 중복O

추가, 검색, 삭제, 정렬을 위한 다양한 메서드를 가지고 있다.

그런데,, 인터페이스는 추상 메서드만 있는 거 아니었나..? 인터페이스가 구현부가 있는 메서드를 가질 수 있는 건가....?

맞다! add() get() 메서드는 추상 메서드가 맞고, 해당 메서드들은 List 인터페이스를 상속받는 ArrayList나 LinkedList에서 구현되어있다.

 

- ArrayList : List 인터페이스 구현해 저장 순서가 유지되고, 중복을 허용. 데이터의 저장 공간으로 배열 사용.

remove 메서드 사용 시 주의사항

boolean remove(Object obj)를 호출하려면 매개변수로 객체를 넣어야 함. 즉 new Integer(i)를 넣어야 원하는 값 삭제,

그냥 숫자를 넣으면 Object remove(int index)가 호출되어 index위치에 값 삭제.

   

 - ArrayList의 장단점

장점:  구조가 간단하고 데이터를 읽는 데 걸리는 시간이 짧다. 배열 주소 + 4*n 하면 n+1 번째 데이터에 접근 가능.

          순차적 데이터 추가, 삭제(끝에)는 빠르다.

단점: 크기를 변경할 수 없다. 크기 변경 시 새로운 배열 생성 후 데이터를 복사해야 함. (더 큰 배열 생성, 복사, 참조 변경)

         배열의 중간에 있는 데이터를 추가하거나 삭제할 때 시간이 많이 걸린다.

 

  - LinkedList - 배열의 단점을 보완 : 불연속적으로 존재하는 데이터를 연결

크기 변경 X, 추가 삭제 시간 빠름. 

노드에 데이터, 다음 노드의 주소를 가지고 있음.

class Node{
    Node next; // 다음 노드
    Object obj;// 데이터
}

데이터 삭제: 다음 노드의 주소 변경(참조 변경)만으로 가능.

데이터 추가: Node 객체 생성과 두 번의 참조 변경으로 가능

 

LinkedList의 단점 : 데이터 접근성이 나쁨. ArrayList처럼 n번째 데이터 한 번에 접근 불가. 징검다리처럼 하나하나씩 이동.

--> 극복 위해 doubly linked list 만듦.

 

- doubly linked list

노드에 다음, 이전 노드의 주소 및 데이터를 가지고 있음. 

자바에선 doubly linked list로 구현되어 있음

앞 뒤로 움직일 수 있어 접근성이 조금 좋아졌지만 여전히 ArrayList에 비해선 좋지 않다.

class Node{
    Node next;
    Node previous;
    Object obj;
}

 

- doubly circular linked list : 맨 앞과 맨 뒤를 연결함.

 

- Stack : LIFO(Last In First Out) 구조. 

저장 : push, 추출: pop

ArrayList로 구현하는 게 효율적.

class 여서 객체 생성 가능.

메서드	설명
boolean empty()	비어있는지 알려줌
Object peek()	맨 위에 저장된 객체를 반환  pop과 달리 꺼내진 않음.
Object pop()	맨 위에 저장된 객체를 꺼냄
Object push(Object item)	item을 stack에 저장
int search (Object o)	o를 찾아 그 위치를 반환 배열과 달리 위치 0부터 시작이 아니라 1부터 시작.

 

- Queue : FIFO(First In First Out) 구조.

저장: offer, 추출: poll

LinkedList로 구현하는 게 효율적.

메서드	설명
boolean add(Object o)	o를 Queue에 추가. 성공하면 true반환 저장 공간이 부족하면 IllegalStateException 발생
Object remove()	Queue에서 객체를 꺼내 반환. Queue가 비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어옴. pop과 달리 꺼내진 않음. Queue가 비어있으면 NoSuchElementException 발생
boolean offer(Object item)	item을 Queue에 저장 성공하면 true, 실패하면 false 반환
Object poll()	Queue에서 객체를 꺼내 반환 Queue가 비어있으면 null 반환 (예외 X)
Object peek()	삭제없이 요소를 읽어옴. Queue가 비어있으면 null 반환 (예외 X)

Java에서 Queue는 인터페이스임.. 객체 생성 불가.

방법 1. Queue 직접 구현

방법 2. Quete 구현한 클래스 사용 : LinkedList를 Queue처럼 사용 가능!

Queue q = new LinkedList();

 

 * Iterator, ListIterator, Enumeration

- 컬렉션에 저장된 데이터를 접근(읽어오기) 하는 데 사용되는 인터페이스

Iterator의 메서드

boolean hasNext()	읽어 올 요소가 남아있는지 확인 있으면 true, 없으면 false
Object next()	다음 요소를 읽어온다. hasNext()로 읽어올 요소가 있는지 확인하기.

Enumeration (Iterator의 구 버전)의 메서드

boolean hasMoreElements()	읽어 올 요소가 남아있는지 확인 (hasNext와 비슷)
Object nextElement()	다음 요소를 읽어온다. hasMoreElements()로 있는지 확인하기.

ListIterator는 Iterator의 접근성을 향상시킨 것 (양뱡향)

 

필요성 : 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것.

사용방법: 컬렉션에서 iterator()을 호출해서 Iterator를 구현한 객체를 얻어 사용.

List list = new ArrayList();
Iterator it = list.iteratoe(); // Iterator 객체를 반환

while(it.hasNext()){
    System.out.println(it.next());
}
-----------------------------
public iterface Collection{
    ....
    public Iterator iterator();
    ....
}

Iterator는 1회용이라 다 쓰고 나면 다시 얻어와야 함.

 

** collection framework 사용 시 최대한 조상으로 참조 변수를 선언하면 좋은 점

--> 사용하는 것(list, set 등등) 이 변해도 그 아래 코드를 바꾸거나 검토하지 않아도 괜찮음.

Collection c = new TreeSet();
//위 처럼 선언한 후 TreeSet을 사용하면, 나중에 TreeSet에서 다른거로 변경해도 메서드들 그냥 사용 가능
//왜냐면! Collection에 선언된 메서드만 사용했고 다른 class들도 Collection을 상속했기 때문!

 

- Map과 Iterator

Map은 Collection의 자손이 아니어서 Iterator가 없음.

keySet(), enrtySet(), values()를 호출한 후 Iterator를 사용.

Map map = new HashMap();
...
Iterator it = map.entrySet().iterator();