자료구조(Data Structure)
자료구조는 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말한다. 각각의 자료구조는 장단점이 있어 어떤 자료구조를 사용하는 것이 최선인지는 해결하고자 하는 문제의 종류와 어떤 부분을 우선적으로 최적화할지에 따라 달라질 수 있다. 결국 알고리즘을 작성하고 그에 맞는 자료구조를 선택하는 것이 중요하므로 자료구조를 충분히 이해하지 못한담면 좋은 프로그램을 작성할 수 없다.
자료구조의 분류
추상 데이터 타입은 자료구조를 설명하는 데이터 타입을 말하며, 자료구조는 추상 데이터 타입을 실제로 구현한 결과를 말한다.
자료구조는 여러 속성을 기반으로 분류할 수 있는데 대표적으로 많이 분류하는 방법으로는 선형 자료구조(Linear Data Structure)과 비선형 자료구조(Nonlinear Data Structure)가 있다.
선형 자료구조(Linear Data Structure)는 데이터를 순서대로 정렬된 형태로 기존에 사용하던 배열과 같은것이라고 생각하면 된다. 대표적인 선형 자료구조로는 리스트(List), 큐(Queue), 덱(Deque)이 있다.
비선형 자료구조(Nonlinear Data Structure)는 선형 자료구조의 반대로 일렬로 나열되는 것이 아니라 각 요소가 요소와 연결 된 형태로 데이터를 비연속ㅈ적으로 연결할것을 말한다. 대표적인 비선형 자료구조는 그래프(Graph), 트리(Tree)가 있다.
위 두가지 분류에 포함되지 않는 자료구조로 집합(Set)과 파일 자료구조도 있으며 집합은 데이터가 연결된 형식이 아니라 table에 가까운 자료구조이다.
컬렉션 프레임웍(Java Collections framework)
일반적으로 컬렉션(collection)은 어떤 일정한 부류의 것을 수집해 한 공간에 모아놓은 것을 말한다. Collections는 일반적인 컬렉션의 의미와 비슷하게 Java에서 여러 객체(데이터)를 쉽게 다루기 위해 모아놓은 자료구조를 의미한다.
프레임웍(framework)은 건물의 뼈대를 생각하면 된다. 건물의 뼈대와 같이 표준화 정형화된 체계적인 프로그래밍 방식을 뜻하며 만들어 놓은 기능을 모아 놓은 라이브러리와 같이 단순히 가능만을 제공한다. 프레임웍은 라이브러리를 제공 하며 프로그래밍 방식을 제공하여 강제한다. 프로그램의 생산성이 증가하며 유지보수가 쉬워진다.국내에서 많이 사용되며 Spring이 Java를 기반으로 한 대표적인 웹 어플리케이션 프레임워크이다.
위의 단어들의 의미를 합쳐 말하면 다수의 데이터(Collections)를 쉽고 효과적으로 처리할 수 있는 표준화된 방법(framework)을 제공하는 클래스의 집합을 의미한다. 즉 데이터를 저장하는 자료구조와 데이터를 처리하는 알고리즘을 구조합하여 클래스로 구현해 놓은 것이다.(인터페이스를 사용하여 구현된다.)
컬렉션 프레임웍의 핵심 인터페이스
컬렉션 프레임워크에서는 데이터를 저장하는 자료 구조에 따라 다음과 같은 핵심이 되는 주요 인터페이스를 정의하고 있다. 주요 인터페이스로 List, Set, Map이 있으며 List와 Set은 공통된 부분이 많은 List 인터페이스와 Set인터페이스 둘의 공통점을 모아서 새로운 인터페이스인 Collection 인터페이스를 정의하였다.
Map은 List와 Set과 달리 키(key와 값(value)을 쌍(pair)으로 관리하는 구조이기 때문에 독립된 인터페이스를 가진다.
인터페이스 | 특징 |
List | 순서가 있는 데이터의 집합, 데이터의 중복을 허용한다. 예) 대기 명단 |
구현 클래스 : ArrayList, LinkedList, Stack, Vector 등 | |
Set | 순서가 존재하지 않는 데이터의 집합, 데이터의 중복을 허용하지 않는다. 예) 집합 |
구현 클래스 : Hashset, TreeSet 등 | |
Map | 키(Key)와 값(value)의 쌍(pair)으로 이루어진 데이터의 집합. 순서는 존재하지 않다. 키는 중복을 허용하지 않고, 값은 중복을 허용한다. 예) 우편번호 |
구현 클래스 : HashMap,TreeMap,Hashtable,Properties 등 |
컬렉션 클래스(collection class)
컬렉션 프레임워크에 속하는 인터페이스를 구현한 클래스를 컬렉션 클래스(collection class)라고 한다. 컬렉션 프레임워크의 모든 컬렉션 클래스는 List, Set, Map 3가지 형태의 자료구조의 인터페이스 중 하나의 인터페이스를 구현하며 클래스로 제공한다.
- 클래스 이름에 구현한 인터페이스의 이름이 포함되어 구분할 수 있다.
- 포함 되어 있지 않은 컬렉션 클래스는 예전부터 사용되어 기존 코드와의 호환을 위해 아직도 남아있다.
(새로 추가된 클래스를 사용하는 것이 성능면에서 바람직하다.)
- Queue와 Set에서 더 구체화된 Deque와 SortedSet라는 자료구조의 인터페이스가 존재한다.
Collection 인터페이스
List와 Set 인터페이스의 많은 공통된 부분을 Collection 인터페이스에서 정의하고, 두 인터페이스는 그것을 상속받는다. 따라서 Collection 인터페이스는 컬렉션을 다루는데 가장 기본적인 동작들을 정의하고, 그것을 메소드로 제공하고 있습니다.
Collection인터페이스의 메서드
메서드 | 설명 |
boolean add(Object o) boolean addAll(Collection c) |
지정된 객체(o)또는 Collections(c)의 객체들을 Collection에 추가한다. |
void clear() | Collection의 모든 객체를 삭제한다. |
boolean contains(Object o) | 지정된 객체(o)또는 Collections의 객체들이 Collection에 포함되어 있는지 확인한다. |
boolean equals(Object o) | 동일한 Collection인지 비교한다. |
int hasCode() | Collection의 Hash code를 반환한다. |
boolean isEmpty() | Collection이 비어있는지 확인한다. |
iterator iterator() | Collection의 iterator를 얻어서 반환한다. |
boolean remove(Object o) | 지정된 객체를 삭제한다. |
boolean removeAll(Collection c) | 지정된 Collection에 포함된 객체들을 삭제한다. |
boolean retainAll(Collection c) | 지정된 Colelction에 포함된 객체만을 남기고 다른 객체들은 Collection에서 삭제한다. 이 작업으로 인해 Collection에 변하가 있으면 true 그렇지 않으면 false를 반환한다. |
int size() | Collection에 저장된 객체의 개수를 반환한다. |
Object[] toArray() | Collection에 저장된 객체를 객체배열(Object[])로 반환한다. |
Object[] toArray(Object[] a) | 지정된 배열에 Collection의 객체를 저장해서 반환한다. |
Iterable
Collection의 상위에 있는 Iterable 인터페이스는 자바의 컬렉션 프레임워크에서 컬렉션의 저장된 요소들을 읽거오는 방법을 표준화하기 위해 사용된다.
public interface Iterable<T> {
Iterator<T> iterator();
.....
}
Iterable인터페이스 안에는 Iterator 메소드가 추상 메소드로 선언되어 있어 Collection 인터페이스의 계층구조에 속하는 클래스들은 모두 iterator() 메서드를 가지게 된다. Iterable 인터페이스의 역할은 하위 클래스들이 iterator() 메서드를 무조건 구현하게 하는 것이다.
Iterator 인터페이스
- Iterator 인터페이스는 Map인터페이스와 마찬가지로 Collection과 별개로 존재하는 인터페이스이다.
public interface Iterator<E> {
....
boolean hasNext();
....
E next();
...
default void remove() {
throw new UnsupportedOperationException("remove");
}
- Iterator() 메서드의 반환값이 Iterator이기 때문에 Iterator() 메서드를 호출하여 사용 한다면 Iterator 인터페이스를 구현한 객체를 얻을 수 있다.
// ArrayList 클래스의 iterator() 메서드
public Iterator<E> iterator() {
return new Itr();
}
- 따라서 Iterator 인터페이스의 hasNext(), next(), remove() 등의 메소드를 이용할 수 있게 된다.
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
// prevent creating a synthetic constructor
Itr() {}
public boolean hasNext() {...............}
@SuppressWarnings("unchecked")
public E next() {...............}
public void remove() {...............}
@Override
public void forEachRemaining(Consumer<? super E> action) {...............}
final void checkForComodification() {...............}
}
컬렉션에 저장된 데이터를 접근하는데 사용되는 인터페이스로 컬렉션클래스의 데이터를 하나씩 읽어올 때 사용한다.
표준화가 되어 있지 않다면 컬렉션에 저장된 데이터를 읽어오는 방법이 다른데 이를 방지하기 위해 Iterator 인터페이스가 존재한다.
Iterator 인터페이스의 메서드
메서드 | 설명 |
boolean hasNext() | 읽어 올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환한다. |
Object next() | 다음 요소를 읽어온다. next()를 호출하기 전에 hasNext()를 호출해서 읽어 올 요소가 있는지 확인하는 것이 안전하다. |
void remove() | next()로 읽어온 요소를 삭제한다. next()를 호출한 다음에 remove()를 호출해야 한다.(선택적 기능) |
void forEachRemaining(Consumer<? super E> action) | 컬렉션에 남아 있는 요소들에 대해 지정된 작업(action)을 수행한다. 람다식을 사용하는 디폴트 메서드. (JDK1.8부터 추가) |
- 컬렉션에서 iterator() 메서드를 호출하면 컬렉션에서 Iterator 인터페이스를 구현한 객체를 반환한다. 이를 얻어 사용한다.
- Iterator 인터페이스를 구현한 클래스의 인스턴스를 반환하는 iterator() 메소드는 Collectuon인터페이스에 정의되어 있어 Collection인터페이스를 구현한 List와 Set인터페이스에서 iterator() 메소드 사용이 가능하다.
- Iterator는 일회용으로 Iterator의 요소를 전부 읽어오고 나서는 다시 사용할 수 없기 때문에 다시 새로운 Iterator객체를 생성하여 사용해야 한다.
for문을 사용하여 list의 get() 메서드를 통해 데이터를 접근하여 사용하여도 같은 결과 값을 얻을 수 있지만 만약 컬렉션이 HashSet으로 변경된다면 많은 변경이 필요하다.
ArrayList list = new ArrayList();
list.add(10);
list.add(20);
for(int i = 0; i < list.size(); i++) {
if(i <= list.size()) {
System.out.print(list.get(i)+ " ");
}
}
하지만 Collection인터페이스를 구현한 HashSet의 Iterator()메서드를 사용한다면 표준화된 접근 방법을 사용하여 컬렉션 클래스의 변경에도 코드의 변경을 최소화할 수 있다.
List list = new ArrayList();
Iterator it = list.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
// for(int i=0; i <list.size(); i++) {
// System.out.println(list.get(i));
// }
HashSet list = new HashSet();
Iterator it = list.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
참조변수를 Collection으로 해놓는다면 컬렉션 인터페이스에 정의된 메서드만을 사용했음을 알 수 있기 때문에 컬렉션이 변경되어도 코드를 변경할 필요가 없어진다.
Collection c = new HashSet();
//Collection c = new TreeSet();
c.add("1");
Iterator it = c.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
Enumeration 인터페이스
Iterator와 같은 동작을 하는 인터페이스, Iterator이전에 사용하던 인터페이스로 기존 코드와의 호환성을 위해서만 남아 있는 것으로 Iterator인터페이스를 사용하는 것이 좋다.
메소드 | 설명 |
boolean hasMoreElements() | 읽어 올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환한다. Iterator의 hasNext()와 같다. |
Object nextElement() | 다음 요소를 읽어온다. nextElement()를 호출하기 전에 hasMoreElements()를 호출해서 읽어올 요소가 남아있는지 확인하는 것이 안전하다. Iterator의 next()와 같다. |
ListIterator 인터페이스
ListIterator 인터페이스는 Iterator 인터페이스를 상속받아 여러 기능을 추가한 인터페이스다. 기존의 Iterator인터페이스는 컬렉션의 요소에 접근할 때 단방향으로만 이동할 수 있없지만 ListIterator 인터페이스는 컬렉션 요소의 대체, 추가 그리고 인텍스 검색 등을 위해 작업에서 양방향으로 이동하는 것을 지원하여접근성을 향상시킨것이다.
- List를 구현한 경우에만 사용이 가능하다.
메서드 | 설명 |
void add(E e) | 해당 리스트(list)에 전달된 요소를 추가함. (선택적 기능) |
boolean hasNext() | 이 리스트 반복자가 해당 리스트를 순방향으로 순회할 때 다음 요소를 가지고 있으면 true를 반환하고, 더 이상 다음 요소를 가지고 있지 않으면 false를 반환함. |
boolean hasPrevious() | 이 리스트 반복자가 해당 리스트를 역방향으로 순회할 때 다음 요소를 가지고 있으면 true를 반환하고, 더 이상 다음 요소를 가지고 있지 않으면 false를 반환함. |
E next() | 리스트의 다음 요소를 반환하고, 커서(cursor)의 위치를 순방향으로 이동시킴. |
int nextIndex() | 다음 next() 메소드를 호출하면 반환될 요소의 인덱스를 반환함. |
E previous() | 리스트의 이전 요소를 반환하고, 커서(cursor)의 위치를 역방향으로 이동시킴. |
int previousIndex() | 다음 previous() 메소드를 호출하면 반환될 요소의 인덱스를 반환함. |
void remove() | next()나 previous() 메소드에 의해 반환된 가장 마지막 요소를 리스트에서 제거함. (선택적 기능) |
void set(E e) | next()나 previous() 메소드에 의해 반환된 가장 마지막 요소를 전달된 객체로 대체함. (선택적 기능) |
컬렉션 클래스 정리 & 요약
- 배열이 순차적으로 추가/삭제시 유리하기 때문에 Stack을 구현하는데 배열 기반의 컬렉션 클래스(ArrayList, Vector)를 사용한다.
- 배열의 단점인 추가/삭제가 불리한 점을 개선한 연결기반 컬렉션 클래스(LinkedList)를 사용하여 Queue 구현한다.
- 배열과 링크드리스트가 조합하여 배열을 장점과 링크드 리스트의 장점을 가지는 해시 테이블을 사용해 검색기능 향상시킨 HashMap
- 연결기반 컬렉션 클래스(LinkedList)를 변형하여 이진 탐색 트리구조인 TreeMap은 검색과 범위검색, 정렬(중위순회) 기능이 향상되었다.
- HashMap과 TreeMap의 키(key)부분으로 만든 HashSet과 TreeSet
- HashMap의 변형인 Properties (Object , Object) => (String, String), 파일의 읽기와 쓰기가 용이하다.
- 순서가 필요할 때 사용하는 LinkedHashMap, LinkedHashSet
'Java' 카테고리의 다른 글
[JAVA] Set 인터페이스 (0) | 2023.11.10 |
---|---|
[JAVA] Comparator와 Comparable 인터페이스 (0) | 2023.11.08 |
[JAVA] List 인터페이스 (0) | 2023.11.07 |
[JAVA] 형식화 클래스 (0) | 2023.11.04 |
[JAVA] 유용한 클래스(Math클래스, 래퍼클래스, Number클래스) (0) | 2023.11.04 |