[23일차] Stack, Queue, Deque, LinkedList, HashTable, TreeSet

유태형·2022년 5월 26일

Java 알고리즘 코드스테이츠

코드스테이츠

목록 보기

23/77

오늘의 목표

Stack
Queue
Deque
LinkedList
HashTable
TreeSet

내용

Stack

스택은 FILO(First In Last Out) 구조로 가장 먼저 들어온 데이터가 가장 나중에 나가고, 가장 나중에 들어온 데이터가 가장 먼저 나갑니다.
즉 입력방향과 출력방향이 한 방향인 방향이 동일한 선형 자료구조입니다. Stack을 구현할때 꼭 정해진 것은 아니지만, 관례상 Stack에 데이터를 입력하는 것을 push, 데이터를 출력하는 것을 pop이라고 부릅니다. 다수의 데이터를 한번에 또는 임의의 위치에 데이터를 입출력 할 수 없습니다.

스택은 브라우저의 앞뒤로 뒤로가기, 실행취소, 동전꽂이등에 사용될 수 있습니다.

Queue

큐는 FIFO(First In First Out) 구조로 가장 먼저 들어온 데이터가 가장 먼저 나가고, 가장 나중에 들어온 데이터가 가장 나중에 나갑니다.
입력과 출력 방향이 상반된 방향인 방향이 다른 선형 자료구조입니다. Queue를 구현할 때 데이터를 입력하는 것을 Enqueue 데이터를 출력하는 것을 Dequeue라고 관례상 부릅니다. 스택과 마찬가지로 다수의 데이터를 한번에 또는 임의의 위치에 데이터를 입출력 할 수 없습니다.

큐는 순서대로 처리해야할 줄서기, 버퍼, 게임서칭 등 스택보다 더 많은 분야에서 활용 될 수 있습니다.

Dequeue

디큐는 FIFO와 LIFO의 성질을 모두 가지고 있습니다.
입력과 출력의 방향을 그때마다 선택하여 같을 수도, 다를 수도 있습니다. 큐에서 입력을 offer, 출력을 poll이라고 한다면,

메서드	설명
offerFirst	데이터를 맨 앞에 입력
offerLast	데이터를 맨 마지막에 입력
pollFirst	맨 앞의 데이터를 출력
pollLast	맨 마지막의 데이터 출력

메서드로 처음과 마지막에 각각 입력과 출력이 가능합니다.
다만 주의해야할 점은 양 끝단에서 각각 입력과 출력이 모두 가능하지만, 다수의 데이터를 한번에 또는 임의의 위치에 데이터를 입출력 할 수는 없습니다.

LinkedList

LinkedList는 배열과 기능은 동일하나 작동방식과 구성에서 차이가 존재합니다.
우선 배열은 물리적 메모리 내에서 연속적으로 배치되어 쉽고 빠르게 요소에 접근가능하나 배열의 크기를 조절할 수도 없습니다.
반면 LinkedList는 메모리에 비 연속적으로 배치되어 인덱스가 아닌 다음 노드의 주소값으로 다음 요소의 값을 확인합니다. 이를 위해서는 노드는 데이터와 다음 노드를 가리키는 주소가 필요합니다.

배열과 LinkedList는 메모리내에 어떻게 구성되고 요소를 어떻게 탐색하는지 다르므로 탐색, 삽입, 삭제에서 상당히 상이합니다.

탐색 : 배열은 연속된 공간에서 인덱스로 탐색을 수행하므로 O(1)이지만 LinkedList의 경우 첫 노드부터 다음노드의 주소를 따라 가야하므로 O(n)만큼 걸립니다.
삽입 : 배열은 삽입하려는 주소까진 인덱스로 바로 이동할 순 있지만 삭입후 배열을 재정렬 해야 합니다. 마지막 노드부터 삽입하려는 위치의 노드까지 모두 1칸씩 뒤로 이동해야 삽입할 자리가 생길 것입니다 따라서 O(n). 반면 LinkedList는 연속되어 저장됨을 보장하지 않으므로 삽입 하려는 노드를 아무곳에나 만들고 삽입 노드 자신의 Link와 바로 이전 노드의Link만 수정하면 됩니다 O(1).
삭제 : 삽입과 마찬가지로 삭제하려는 주소까지는 인덱스로 바로 이동할 순 있지만, 삭제후 다시 재정렬 해야하고 삭제후 모두 1칸씩 앞으로 이동해야 하므로 O(n)이 필요합니다. LinkedList는 이전노드의 주소만 삭제하려는 노드를 건너띄고 다음 노드의 주소를 가리키면 되므로O(1)만큼 걸립니다.

탐색에 있어 배열이 시간을 덜 사용하고, 수정과 삭제는 LinkedList가 시간을 덜 사용 합니다. 따라서, 수정, 삭제가 빈번하지 않은 자료는 배열을 수정과 삭제가 빈번히 발생하는 자료는 LinkedList가 유리합니다.

HashTable

HashTable은 Map인터페이스를 구현한 컬랙션 클래스입니다. 기본적으로 (키,값)쌍으로 이루어져 있으며 Hash를 이용합니다.

길이와 크기가 다양한 키들을 해시함수(hash Function)를 사용해 변환한 해시(hash)를 인덱스로 삼아 키와 값의 쌍들을 저장합니다.

해시 알고리즘

Division Method : Number type의 키를 저장소의 크기로 나누어 나온 나머지를 색인으로 사용합니다. 이때 저장소의 크기는 소수고 2의 제곱수와 먼 값일 수록 효과적입니다.
Digit Folding : 키의 문자열을 ASCII코드로 바꾸고 그 값을 합해 저장소에서 인덱스로 사용합니다. 인덱스가 저장소의 크기를 넘어간다면 Division Method를 적용할 수 있습니다.
Multiplication Method : 인덱스 = (KA mod 1)m, 숫자로된 키 K, 0과 1사이 실수 A, 2의 제곱수인 m
Universal Hashing : 여러개의 해시함수를 미리 저장해 두고 무작위로 해시함수를 선택해서 해시값을 구하는 방법

해시충돌

해시충돌이란? 키값이 다르지만, 해시함수를 거치면서 나온 해시값이 같을때 이를 처리하는 방법입니다.
보통 개방연결법과 분리연결법, 저장소 확장이 존재합니다.

개방 연결법(Open Addressing)
o Linear Probing : 현재 중복된 인덱스 부터 고정된 숫자만큼 이동한 색인에 데이터 저장
o Quadratic Probing : 현재 중복된 인덱스 부터 이동할 숫자를 키우며 제곱하는 방식 ex) 1 -> 4 -> 9 -> 16
o Double Hasing Probing : 하나의 해시함수 충돌시 미리 저장해둔 다른 해시함수를 사용하는 방법입니다.
분리 연결법(Seperate Chaining) : 동일한 색인에 연결리스트 LinkedList나 트리 Red-Black Tree)등의 자료구조를 이용해 여러개의 데이터를 저장하는 방법

저장소 확장 : 해시테이블에 데이터가 많아지면 많아질 수록 해시충돌의 빈도와 확률이 올라가게 됩니다. 이때 해시 테이블을 2배로 늘려주면 다시 충돌의 빈도와 확률이 낮아지게 됩니다. 실제로 자바에서 사용하는 HashMap이 저장소 확장 방식을 채택중이며 75%이상 사용시 크기를 2배로 늘립니다.