Java와 자료구조 - Collection Framework 1

 

 

 

• Collection : 가장 기초가 되는 인터페이스. List와 Set를 상속시킨다.
• List : Order (O) / replacement (O) - ArrayList, LinkedList, Stack, Vector...
• Set : Order (X) / replacement (X) - HashSet, TreeSet..
• Map : List와 Set과는 다른 형태로 컬렉션을 다룬다. 
  key) Order (X) / Replacement (X)
  value) Order (X) / Replacement (O) - HashMap, TreeMap, Hashtable, Properties...

 

 

Collection인터페이스

 

<메서드>

• add
• clear
• contains
• equals
• isEmpty
• remove
• iterator
• ....

 

 

저장된 데이터를 읽고 추가하고 삭제하는 등 가장 기본적인 메서드들이 정의되어있다.

 

 

 

List인터페이스

 

 

중복을 허용하고, 저장순서가 유지되는 컬렉션을 구현할 때 사용한다.

 

 

<메서드>

• add
• get
• indexOf
• listIterator
• set
• sort
• subList

 

Collection인터페이스로부터 상속받은 메서드들 외에도 다양한 메서드들이 정의되어있다.

 

 

ArrayList

 

 

List인터페이스를 구현하기에 원소들의 순서가 유지되고 중복을 허용한다. 

Object배열로 구현되어있고, 배열의 공간이 부족하면 용량이 큰 배열을 새로 만들어 기존 배열을 복사해서 사용한다.

배열을 새로 만들고 복사하는 과정에서 시간을 많이 소요하니 되도록이면 배열의 크기를 넉넉하게 설정하자.

 

 

 

LinkedList

 

 

각 요소들이 자신과 연결된 다음 요소에 대한 주소값과 데이터로 구성되어있다.

데이터의 추가와 수정에 빠른 처리속도를 보인다.

 

 

Doubly LinkedList

 

 

다음 요소에 대한 주소값 뿐만 아니라 이전 요소에 대한 주소값까지 포함하도록 해 양방향으로 탐색을 진행할 수 있도록 설계되어있다.

 

 

Doubly Circular LinkedList

 

 

더블 링크드 리스트에서 첫 번째 요소와 마지막 요소를 서로 연결시킨 형태이다.

 

 

ArrayList와 LinkedList를 비교해 보면, 순차적으로 데이터를 추가하거나 삭제하는 경우에는 ArrayList가 더 좋은 모습을 보인다.

 

마지막 데이터부터 역순으로 데이터를 삭제하게 되면 각 요소들의 재배치가 필요하지 않고, 마지막 요소의 값만 null로 바꿔 주면 되기에 ArrayList는 빠르게 처리할 수 있다.

 

중간 부분의 데이터를 추가하거나 삭제하는 경우에는 LinkedList가 더 좋은 모습을 보인다.

 

ArrayList는 각 요소들을 재배치하고 공간도 재조정해야 하지만, Linkedlist는 각 요소간 연결만 변경해주면 된다.

 

물론, 데이터를 읽어오는데 걸리는 시간은 ArrayList가 빠르다.

 

 

 

Stack

 

 

LIFO 구조의 컬렉션 클래스이다.

순차적으로 데이터를 추가하고 삭제하기 때문에 배열기반의 컬렉션 클래스를 사용하는게 합리적이다.

 

 

 

Queue

 

 

FIFO 구조의 컬렉션 클래스이다.

데이터를 추가하고 삭제하기 쉬운 LinkedList로 구현하는게 합리적이다.

 

 

Deque

 

 

앞으로도 나갈 수 있고, 뒤로도 나갈 수 있는 큐이다.

ArrayDeque나 LinkedList로 구현한다.

 

 

 

Set인터페이스

 

 

중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용된다.

 

 

 

Map인터페이스

 

 

키와 값을 한 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는데 사용된다.

중복되는 키를 저장할 경우 키에 해당하는 기존 값이 새로운 값으로 덮어써진다.

 

• containsKey
• containsValue
• remove
• keySet
• entrySet
• values

 

Map인터페이스의 내부에는 Entry인터페이스가 있으며, Map에 저장되는 key-value쌍을 다룰 때 사용된다.

 

 

 

Iterator

 

 

컬렉션의 요소에 접근할 때 사용하는 인터페이스이다.

Iterator의 기능을 향상시킨것으로 ListIterator인터페이스가 있고, Iterator의 구버전으로 Enumeration인터페이스가 있다.

 

Collection인터페이스를 구현한 컬렉션 클래스에 대해서 이터레이터를 사용할 수 있다.

 

Map은 키와 값의 쌍으로 데이터를 저장하기 때문에 이터레이터를 직접 호출할 수는 없고, 키와 값을 Set형태로 얻어오면 이터레이터를 사용할 수 있다.