HashTable을 기반으로 한 가장 일반적으로 사용되는 Map의 구현체이다. 해싱을 통해 얻은 고유의 해시 값으로 버킷에 저장되며, 해시 충돌이 없는 한 최고의 연산 속도를 가진다.
TreeSet TreeSet은 이진 트리 형태인 레드 블랙 트리 구조를 기반으로 하는 구현체이다. 데이터 저장 시 키값을 기준으로 오름차순을 기본으로 자동 정렬되어 저장된다. HashMap에 비해 연산 속도는 느리지만 항상 O(log n)값을 가지므로 특정 상황에선 HashMap보다 연산적으로 이점을 가진다.
LinkedHashMap
LinkedHashMap은 HashMap에서 연결 리스트를 추가한 구현체이다. 따라서 해당 구현체는 순서가 존재한다. 기본적으로 이중 연결(Doubly Linked) 형태로 구현된다. 전체적인 연산은 HashMap보다 조금 느리다.
연결 리스트는 각 요소를 포인터로 연결하여 관리하는 데이터 집합체다. 기본적으로 노드(node)와 헤드(head)로 이루어져 있고, 경우에 따라 꼬리(tail)도 포함이 된 구조이다.
노드(node) : 데이터와 다른 노드와 연결 짓는 포인터로 구성
헤드(head) : 리스트의 첫 노드를 가리키는 포인터
꼬리(tail) : 리스트의 마지막 노드를 가리키는 포인터
배열이 “1번, 2번, 3번…”처럼 index로 접근한다면, 연결 리스트는 “철수 다음 영희, 영희 다음 민수…“처럼 노드 참조로 순서를 유지한다
연결 리스트 종류 및 구조 형태
연결 리스트의 기본 구조는 포인터를 기점으로 리스트를 순회하는 구조이다.
이때 포인터는 1개 혹은 2개가 될 수 있으며, 각 노드들의 참조 방식에 따라 단방향 혹은 양방향으로 순회가 가능하다.
노드는 두 가지 참조 방식이 존재한다. 다음 노드만을 참조하는 방식과 이전 노드도 포함하여 참조하는 방식이 있다.
노드 간 참조 형식으로 인해 리스트를 수정할 땐 각 데이터의 위치를 수정할 필요 없이 참조하는 노드 정보만 변경해 주면 되기 때문에 노드의 위치를 알고 있다면 성능면으로 이점을 얻을 수 있다.
하지만 인덱스로 접근하는 방식은 헤드 포인터를 기점으로 순차적으로 순회하여 접근하기 때문에 성능면으로 불이점을 얻게 된다.
연결 리스트는 크게 세 분류로 구분된다.
단일 연결 리스트 (Singly Linked List)
이중 연결 리스트 (Doubly Linked List)
원형 연결 리스트 (Circular Linked List)
단일 연결 리스트 (Singly Linked List)
단일 연결 리스트는 연결 리스트의 기본적인 형태라고 보면 된다.
단일 연결 리스트의 형태
위 그림을 참조하여 단일 연결 리스트의 구조적 특징을 살펴보면, 헤드 포인터 하나만을 가지고 순회하는 구조이다. 그림에서 볼 수 있듯이 한 방향으로만 순회하기 때문에 각 노드들은 데이터를 포함하여 다음 노드를 참조하는 형태가 되고, 마지막 노드의 경우 NULL을 참조하여 노드의 끝을 알리고 있다.
정리하면 다음과 같다.
헤드 포인터를 기점으로 모든 노드들을 연결함
각 노드들은 다음 노드만을 참조함
마지막 노드는 NULL을 참조해 끝을 알림
한 방향으로만 데이터를 조회할 수 있음
위 특징들을 바탕으로 삽입과 삭제 과정에 대해 알아보자.
변경전 : [A] -> [C] ( [B]를 삽입 하려는 상황 )
변경후 : [A] -> [B] -> [C]
B를 A와 C사이에 넣는 상황이라면 A 다음 노드 정보를 새로 생성된 B를 대입해 주고 B 다음 노드 정보에 C를 대입해 주면 모든 게 끝난다. 그렇기 때문에 삽입의 시간 복잡도는 O(1)이 된다.
변경전 : [A] -> [B] -> [C] ( [A]를 삭제 하려는 상황 )
변경후 : [B] -> [C]
변경전 : [A] -> [B] -> [C] ( [B]를 삭제 하려는 상황 )
변경후 : [A] -> [C]
삭제의 경우 리스트 첫 번째를 삭제한다면 헤드 포인터에 다음 노드를 대입해주기만 하면 끝나지만,
중간 삭제의 경우 A와 C를 이어 주기 위해 B 외로 A의 정보까지 필요하기 때문에 순회과정이 필요하다.
그렇기 때문에 삭제의 시간 복잡도는 첫 노드시 O(1) 그 외에는 O(n)이 된다.
이중 연결 리스트 (Doubly Linked List)
이중 연결 리스트는 단방향에서 양방향으로 바뀐 형태이다.
이중 연결 리스트의 형태
이중 연결 리스트의 구조적 특징은 헤드 포인터와 꼬리 포인터를 통해 순회하는 구조이다. 그림에서 볼 수 있듯이 양방향으로 순회하기 때문에 각 노드들은 다음 노드뿐만 아니라 이전 노드를 포함하여 참조하게 된다. 또한 리스트의 끝은 양방향 순회로 인해 헤드와 꼬리 모두 끝을 알리는 NULL을 참조하게 된다.
정리하면 다음과 같다.
헤드 포인터와 꼬리 포인터를 기점으로 모든 노드들을 연결함
각 노드들은 다음 및 이전 노드를 참조함
양방향으로 데이터 조회가 가능
헤드와 꼬리 모두 NULL을 참조하여 리스트의 끝을 알림
이중 연결 리스트의 삽입과 삭제는 단일 연결 리스트와 크게 다를거 없지만 삭제 과정이 좀 달라진다.
변경전 : [A] -> [B] -> [C] ( [B]를 삭제 하려는 상황 )
변경후 : [A] -> [C]
단방향의 경우 중간 삭제시 이전 노드의 정보를 얻기 위해 리스트를 순회해야하는 번거로움이 있었지만, 이중 연결 리스트의 경우 양방향 순회가 가능하므로 B 노드만으로 A와 C의 참조 관계를 수정할 수 있어 번거로움이 없어진다.
그로 인해 삭제의 시간 복잡도는 O(1)이 되게 된다.
처리 시간에 대해선 성능적 이점을 얻긴하지만, 그만큼 더 많은 정보를 가져야 되므로 메모리 사용량에 대해선 기존 보다 불이점을 얻게 된다.
원형 연결 리스트 (Circular Linked List)
원형 연결 리스트의 형태
원형 연결 리스트의 구조적 특징은 끝이 존재하지 않는 것이다. 위 그림을 보면 헤드 포인터를 기점으로 순회하며 리스트의 끝에 도달하면 다시 리스트의 첫 위치로 이동하는 것을 확인할 수 있다. 원형 연결 리스트의 구조는 끝이 존재하지 않다는 특징 외로 연결 리스트와 똑같으므로 상황에 맞게 단일 혹은 이중으로 설계하면 된다.
정리하면 다음과 같다.
끝이 없는 순회구조
단일 혹은 이중으로 설계
원형 연결 리스트를 순회할 땐 끝이 존재하지 않아 무한 순회를 하게 될 수 있어 설계시 순회 끝 조건을 잘 설계 해야한다.