자료구조 Collection FrameWork

5 minute read

자바에서는 다양한 자료구조를 사용자가 쉽게 활용할수 있도록 성능적으로 우수하며, 코딩에 할애할 시간을 줄일수 있는 Collection Framework를 제공하고 있다.

1. Collection Framework란?

Java Collection Framework는 자료를 저장하고, 그것을 처리하는 Logic에 대해 자바의 설계 원칙과 표준을 적용하여 구현되어있다.

Collection Framework는 자료구조와 그에 긴밀히 연관된 알고리즘 학문에서 필요한 다양한 자료구조들을 구조화 하여 제공하고 있다.

자바에서는 자료구조들을 Interface로 구현하여 사용하고 있다. 여기서는 간단히 아래의 그림을 통해 Collection Framework 구조에 대하 살펴본다.

위 그림은 Java 내 Collection Framewor의 상속 구조도를 표현한 것이다. 주로 사용 하는 인터페이스로는

List
Set
Map 들이 있다.

우선 Collection Framework 구조에서 최상위 인터페이스는 Collection 인터페이스 이다. (이 Collection은 Iterable을 상속 받는다.)

자료 구조로 사용될 Class에서 필요한 주요 기능들이 Collection 인터페이스에 정의되어 있으며, 그 뒤 각각의 필요 기능에 따라 추가적인 인터페이스와 추상 Class를 구현/상속 하고 있는 것을 확인할 수 있다.

위 내용중 Map<K,V> 라는 인터페이스는 key-value 형식으로 구현되는 자료구조로 여타 구조들과 차이가 있어 별도의 인터페이스로 구현이 된다.

2. 각 인터페이스의 특징

List
- 설명: 순서가 있는 데이터의 집합으로 데이터의 중복을 허용한다.
- 구현 클래스: Vector, ArrayList, LinkedList, Stack
Set
- 설명: 순서를 유지하지 않는 데이터의 집합으로 데이터의 중복 비허용
- 구현 클래스: HashSet, TreeSet
Queue
- 설명: 순서가 있는 데이터 집합으로 데이터의 중복을 허용(List와 유사 but 별도 기능 존재)
- 구현 클래스: PriorityQueue, LinkedList
Map<K, V>
- 설명: 키와 값의 한쌍으로 이루어지는 데이터의 집합, 순서가 없고 키는 중복 허용되지 않으나 값은 중복 가능
- 구현 클래스: HashTable, HashMap, TreeMap

3. Collection 클래스란?

Collection Framework 내 Collection interface 를 구현한 것을 Collection Class 라고 한다. 이들은 각각의 사용 방식에 따라 필요한 인터페이스 및 추상 Class를 구현 및 상속한다.

3-1. Collection 인터페이스의 주요 인터페이스에 대해 알아보자.

boolean add(E o): 해당 collection에 전달된 요소 추가
boolean addAll(Collection<? Extends E> c): 해당 collection에 모든 요소 추가
void clear(): 해당 collection의 모든 요소 제거
boolean contains(Object o): 해당 collection이 전달된 객체 포함 여부 확인
boolean containesAll(Collection<?> c): 해당 collection이 전달된 collection의 모든 요소 포함 하는지
boolean equals(Object o): 해당 collection과 전달된 객체의 동일ㅇ부 확인.
boolean isEmplty(): 해당 collection이 비어있는지 확인
Iterator iterator(): 해당 collection의 반복자(iterator)를 반환
boolean retainAll(Collection<?> c): 해당 collection에 전달된 collection의 요소한 남김
Object[] toArray(): 해당 collection의 모든 요소를 Object 타입의 배열 형태로 반환

4. HashSet

4-1 HashSet과 HashMap

Set 인테페이스를 구현한 클래스들로 집합 자료구조를 사용하기 위한 클래스이다. 중복된 값을 여러번 넣어도 하나의 값만 보유 한 상태를 유지한다.

어떻게 가능할까?

일단 HashSet 과 뒤에 배울 HashMap 의 Key의 중복을 다루는 부분이 다르긴하다. HashSet은 중복이 등록되지 않게 하고, HashMap은 이전의 값을 새로운 값으로 교체를 한다.

근데 HashSet은 Set인터페이스의 구현체 이면서도 내부적으론 HashMap 인서튼스를 사용하고 있다. 그렇기 때문에 HashMap과 비슷한 자료구조를 가지고 있다.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{   
    private transient HashMap<E,Object> map;
    
    // 생략
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    // 생략
}

이를 통해 HashSet 자료구조는 HashMap의 키 처럼 데이터의 중복이 없이 사용이 가능하다. 그럼 HashMap 의 Keyset을 HashSet 과 동일하다고 보면될까?

HashMap처럼 순서에 의미를 두지 않으며, 데이터의 중복이 없다.

데이터를 저장할 떄는 eqauls(), hashcode() 를 사용하여 저장을 하게된다. 간략하게만 말하자면

hashcode 를 통해 특정한값을 넣었을때 고정된 길이의 값을 리턴 해준다.
equals 를 통해 위값이 이전에 들어있는 값인지 확인 한다.

key와 value 를 넣는 방식에는 2가지 방식이 존재하는데 (왜 HashSet 인데 value를 말하냐 하면 HashSet도 HashSet 클래스 내부 필드의 더비 객체를 value로 하고 있기 때문이다. 즉 HashMap과 동일) (1) 이미 존재하는 데이터의 Key 값이 새로 넣으려는 데이터의 Key 값과 같으면, 이미 존재하는 데이터의 Value 값을 새로 넣으려는 데이터의 Value 값으로 교체하거나

(2) 이미 존재하는 데이터의 Key 값이 새로 넣으려는 데이터의 Key 값과 다르면, 이미 존재하는 데이터의 뒤에 새로 넣으려는 데이터를 연결하여 삽입한다.

연결 방법
자바(Java)에서는 전달된 요소를 Hash 함수를 이용해 특정 code로 변형하여 그 값을 기반으로 배열 Index 내에 연결리스트를 구현하여 저장하고 있다.

4-2 HashSet과 TreeSet

두 Set의 차이를 코드를 통해 확인해보자

public class SetTest {
    public static void main(String[] args){
        // HashSet 의 예제
        Set<Integer> hashSet = new HashSet<>();
        hashSet.add(1);
        hashSet.add(2);
        hashSet.add(3);
        hashSet.add(4);
        hashSet.add(5);

        Iterator<Integer> iterator = hashSet.iterator();
        while(iterator.hasNext()){
            System.out.print(iterator.next() + ", ");
        }
        // 결과 : 3, 19, 6, 7, 8
        System.out.println();

        // TreeSet의 예제
        Set<Integer> treeSet = new TreeSet<>();
        treeSet.add(19);
        treeSet.add(7);
        treeSet.add(6);
        treeSet.add(8);
        treeSet.add(3);
        Iterator<Integer> iterator2 = treeSet.iterator();
        while(iterator2.hasNext()){
            System.out.print(iterator2.next() + ", ");
        }
        // 결과 : 3, 6, 7, 8, 19
    }
}

두 코드를 보면 알듯 , HashSet은 자료의 순서에 대한 보장을 해주지 않는다. TreeSet은 HashSet과 달리 SortedSet이라는 인터페이스를 구현하여 Natural Ordering을 지원하기 때문에 위와 같이 정렬되어서 나온다. TreeSet을 Natural Ordering이 아닌 별도의 순서로 저장하는 방식을 취하고 싶은 경우, Comparator 인터페이스를 구현(참조)하여 인자로써 전달하면 사용 가능하다.

Comparator 인터페이스는 내 블로그에도 있으니 확인해보자.

5. 리스트 인터페이스

순서 개념이 있는 데이터의 집합 (인덱스 관리) 요소의 순서가 유지되며, 동일한 요소의 중복 저장을 허용한다. 대표적인 List 관련 클래스

ArrayList
LinkedList
Vector
Stack

5-1 단방향 리스트와 양방향 리스트

단방향 리스트
- 한쪽 방향에서 데이터를 찾아가는 단방향 리스트
- 리스트 안에서, 앞쪽에서 뒷쪽으로 가리키는 방향성을 가진 끈으로 순서가 있는 데이터를 연결하는 방식을 단방향 리스트라고 한다.
- 단방향 리스트의 두가지 요소
  - 데이터
  - 다음 요소를 가리키는 포인터

위 그림을 보면 맨 앞의 데이터를 가리키는 Head포인터가 있으며 각각의 데이터와 다음 요소를 가리키는 포인터로 이루어져 있다.

양방향 리스트
- 리스트 안에서 앞에서 뒤를 가리키는 끈과 뒤에서 앞을 가리키는 끈 2개를 사용하여 순서가 있는 데이터를 연결하는 방법.
- 양방향 리스트의 세가지 요소
  - 데이터
  - 다음 요소를 가리키는 포인터
  - 이전 요소를 가리키는 포인터 ![]https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fr50SD%2FbtqHxcyPMgz%2FUg5bkSpga1kzCIwp1nple0%2Fimg.png

5-2. ArrayList

단방향 포인터 구조로 각 데이터의 인덱스를 가지고 있어 조회 성능이 뛰어 나다. 내부적으로 배열을 이용하여 요소를 저장 __배열의 크기를 고정할 수 없는 인스턴스__로, 크기 조정을 위해 새로운 배열을 생성하고 기존 요소들을 옮기는 작업이 수행된다.

단방향 리스트와 양방향 리스트를 배우기 앞서 배열과 리스트에 대해 먼저 알아본다.

배열이란 데이터를 빈틈없이 나열한 자료구조를 나타낸다.
리스트는 데이터를 순서대로 나열한 자료구조이다.
얼핏 보면 비슷하지만 두 자료구조는 서로 다른 특징을 갖는다.
- 배열
  - 1차원 배열의 경우 요소를 일직성 상에 빈틈없이 나열하여 리스트를 정렬한다.
  - 조회가 빠르다.
  - 삽입 삭제시 오래 걸린다.
- 리스트
  - 방향성이 있는 끈으로 각각의 요소들을 연결시켜 데이터를 정렬한다.
  - 조회가 느리다(조회하는 요소가 뒤에 있을수록 검색 시간 비용이 커지고 속도가 늦어진다.)
  - 삽입, 삭제가 빠르다 (포인터)조작으로 빠르게 가능

5-3 LinkedList

각 데이터가 노드와 포인터로 구성이 되어 연결되어 있는 방식의 구조
각 데이터가 포인터로 연결되어 있는 구조여서 중간에 데이터를 삽입하거나 삭제하기가 용이하다. (ArrayList에 비해)
LinkedList는 그렇다면 어떻게 다를까? LinkedList는 ArrayList, Vector와 달리 배열 구조를 기반으로 하지 않는다.
LinkedList의 각 요소들은 하나의 분리된 Object로써 존재하여 그 Object는 Data 부분과 Address 부분으로 구성되어 있다. 각 요소들은 서로 Pointer와 Address를 이용하여 연결되어 있는 방식으로 이러한 요소들을 Node라고 명명한다.
배열구조 처럼 Index를 이용한 참조가 불가하여 특정 요소를 찾아내기 위해 첫 Node 부터 마지막 Node까지 순환해야 한다는 단점을 갖고 있다.

LinkedList를 이해하기 위해 다음의 그림을 참조하자

주요메서드
- add(int idx, Object o): 지정된 index에 객체를 추가
- offer(E o): 해당 요소를 끝에 추가
- peek(): 첫번째 요소를 리턴
- poll(): 첫번째 요소를 리터 후 삭제
- subList(int, int t): f~t사이의 객체를 리스트로 변환하여 리턴

6. Vector

기본적으로 ArrayList와 동일한 자료 구조를 가지고 있음 ArrayList와 동일한 기능으로 동작 유일하게 다른 부분은 ArrayList와 다르게 Thread-Safe 하다는 것 - Vector는 동기화된 메서드로 구성되어 있다. 하지만 Thread가 한개일 경우에도 동기화를 하기 떄문에 ArrayList에 비해 성능은 조금 떨어진다.

7. Stack

Vector 클래스를 상속받아 전형적인 Stack 메모리 구조를 제공한다. 다우는 데이터에 대해 후입선출 구조를 가지고 있다.

참고 https://hongjw1938.tistory.com/4 https://www.youtube.com/watch?v=uPSkCKB4Kuo&t=200s https://stackoverflow.com/questions/12940663/does-adding-a-duplicate-value-to-a-hashset-hashmap-replace-the-previous-value https://www.javatpoint.com/difference-between-hashset-and-hashmap

Twitter Facebook LinkedIn

한승우