๋ฆฌ์คํธ ADT
๋จผ์ ADT์ ๋ํด ์์๋ณด์.
ADT (์ถ์์๋ฃํ, Abstract data type) : ๋ฐ์ดํฐ ๊ตฌ์กฐ์ ์ถ์ํ
์ด๋ผ๊ณ ์ ์ํ๋ฉฐ ADT๋ ๋ค์์ ๋ํ๋ธ๋ค.
- ์ ์ฅ๋ ๋ฐ์ดํฐ
- ๋ฐ์ดํฐ์ ๋ํ ์์ ๋ค
- ์์ ์ค ๋ฐ์ ๊ฐ๋ฅํ ์๋ฌ ์ํฉ๋ค
์ด๊ฒ์ ๋ฆฌ์คํธ๋ก ํํํ๋ฉด ๋ฆฌ์คํธ ADT๊ฐ ๋๋ ๊ฒ์ด๋ค. ์ฌ์ค ๋ง์ด ์กฐ๊ธ ์ด๋ ต๊ธด ํ๋ฐ ์ฐ์์ ์ธ ์์ ๊ฐ์ฒด๋ค์ ๋ชจ๋ธ๋งํ ๊ฒ์ด๋ผ๊ณ ๋ณผ ์ ์๋ค. ๋ฆฌ์คํธ์ ์์์ ๋ํ ์ ๊ทผ ๋๊ตฌ๋ก๋ ์์(rank)๊ฐ ์๋ค.
๋ฆฌ์คํธ ADT ๋ฉ์๋
๋ฆฌ์คํธ ADT์์ ์์๋ ์์ (rank), ์ฆ ๊ทธ ์์ ์์ ์์ ๊ฐ์๋ฅผ ํน์ ํ์ฌ ์ ๊ทผ, ์ฝ์ , ๋๋ ์ญ์ ํ๋ค. ๋ง๋ก๋ ์ด๋ ต์ง๋ง ๊ทธ๋ฆผ์ ๊ทธ๋ ค๋ณด๋ฉด ๋์ฑ ์ดํด๊ฐ ์ฌ์ธ ๊ฒ์ด๋ค.
๋ฆฌ์คํธ ADT ๋ฉ์๋
- ์ผ๋ฐ ๋ฉ์๋
boolean isEmpty() #๋ฆฌ์คํธ๊ฐ ๋น์๋์ง ํ์ธ
integer size() #๋ฆฌ์คํธ์ ์ฌ์ด์ฆ ๋ฐํ
iterator elements() #๋ชจ๋ ๋ฆฌ์คํธ ์์ ์ถ๋ ฅ
- ์ ๊ทผ ๋ฉ์๋
element get(rank) # ํด๋น rank์ ์๋ ์์ ๋ฐํ
- ๊ฐฑ์ ๋ฉ์๋
element set(rank, element) # ํด๋น rank์ ์์๋ฅผ set
add(rank, element) # ํด๋น rank์ ์๋ก์ด ๋ ธ๋๋ฅผ ์ถ๊ฐ
addFirst(element) # rank 1์ ์๋ก์ด ๋ ธ๋ ์ถ๊ฐ
addLast(element) # rank Last์ ์๋ก์ด ๋ ธ๋ ์ถ๊ฐ
element remove(rank) #ํด๋น rank์ ์๋ ๋ ธ๋ ์ ๊ฑฐ
element removeFirst() # rank 1์ ์๋ก์ด ๋ ธ๋ ์ ๊ฑฐ
element removeLast() # rank Last์ ์๋ก์ด ๋ ธ๋ ์ ๊ฑฐ
๋ฆฌ์คํธ ADT๋ฅผ ๊ตฌ์ฑํ๋ฉด์ ์์ธ๋ฅผ ๊ตฌ์ฑํด์ค์ผ ํ๋ค. ์ฌ๊ธฐ์ ์์ธ๋ ์ด๋ค ADT์์ ์ ์คํํ๊ณ ์ ํ ๋ ๋ฐ์ํ ์๋ ์๋ ์ค๋ฅ ์ํฉ์ ๋ปํ๋ค. ์๋ฅผ ๋ค์ด rank์ ์์๊ฐ ์ ๋ ฅ๋๋ ์ํฉ์ด ์๋ค. ๋ฆฌ์คํธ ADT์์ ๋ฐ๋ น ๊ฐ๋ฅํ ์์ธ๋ ๋ค์๊ณผ ๊ฐ๋ค.
invalidRankException() # ์ ํจํ์ง ์์ rank
fullListException() # ๋ฆฌ์คํธ๊ฐ ๊ฝ ์ฐจ์์ ๋
emptyListException() # ๋ฆฌ์คํธ๊ฐ ๋น์๋๋ฐ get or remove ๋ฑ..
๋ฆฌ์คํธ ADT๋ ๋ฐฐ์ด๊ณผ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ํ์ฉํ์ฌ ๊ตฌํํ ์ ์๋ค.
๋ฐฐ์ด์ ์ด์ฉํ ๊ตฌํ
๋จผ์ N๊ฐ์ ์์๋ค๋ก ๊ตฌ์ฑ๋ ๋ฐฐ์ด V๋ฅผ ํ์ฉํ๋ค. ๊ฐ์ฅ ์ค์ํ ๊ฒ์ get ๋ฉ์๋, set ๋ฉ์๋ ๋ฑ ํ์ํ๋ค๋ฉด r < 0 ๋๋ r > n – 1 ์ธ ๊ฒฝ์ฐ ์์ธ์ฒ๋ฆฌ๋ฅผ ํด์ผํ๋ค๋ ๊ฒ์ด๋ค.
์ด๊ธฐํ (initailization)
์ด๊ธฐ์๋ ์๋ฌด ์์๋ ์กด์ฌํ์ง ์๋ ์ํ์ด๋ค. O(1) ์๊ฐ์ด ์์๋๋ค.
์ํ (Traversal)
Traverse๋ array์ ๋ชจ๋ ์์ V[0], V[1], V[2], …, V[n – 1]์ ๋ฐฉ๋ฌธํ๋ค. (์ถ๊ฐ๋ก ์ถ๋ ฅํด๋ ์ข๋ค)
์กด์ฌํ๋ ๋ชจ๋ ์์๋ฅผ ๋ฐฉ๋ฌธํ๋ฏ๋ก O(n) ์๊ฐ์ด ์์๋๋ค.
์ฝ์ (Insertion)
์์ add(rank, element)์์๋, rank ์์๋ก ์ ์์ element๊ฐ ๋ค์ด๊ฐ ๋น ์๋ฆฌ๋ฅผ ๋ง๋ค๊ธฐ ์ํด V[n – 1], … , V[r]๊น์ง์ n – r๊ฐ์ ์์๋ค ์๋ฐฉํฅ์ผ๋ก ์ด๋(shift forward)ํ๋ค. ์ด ๊ฒฝ์ฐ rank ๊ฐ 0์ด๋ฉด, n๊ฐ์ ์์๊ฐ ํ ์นธ์ฉ ์ฎ๊ฒจ์ผ ํ๋ฏ๋ก O(n) ์๊ฐ์ด ์์๋๋ค. ๊ตฌํํ๋ฉด์ ์์ธ์ ์ฃผ์ํ์!
์ญ์ (Deletion)
์ฝ์ ๊ณผ ๋ฐ๋๋ก ์์ remove(rank)์์๋, ์ญ์ ๋ ์์์ ์ํด ์๊ธด ๋น ์๋ฆฌ๋ฅผ ์ฑ์ฐ๊ธฐ ์ํด V[r + 1], … , V[n – 1]๊น์ง์ n – r – 1๊ฐ์ ์ ์๋ค์ ์ญ๋ฐฉํฅ์ผ๋ก ์ด๋(shift backward)ํ๋ค. ์ด ๊ฒฝ์ฐ rank ๊ฐ 0์ด๋ฉด, n๊ฐ์ ์์๊ฐ ํ ์นธ์ฉ ์ฎ๊ฒจ์ผ ํ๋ฏ๋ก O(n) ์๊ฐ์ด ์์๋๋ค. ๊ตฌํํ๋ฉด์ ์์ธ์ ์ฃผ์ํ์!
์ฑ๋ฅ (Performance)
* ๋ฐฐ์ด์ ์ด์ฉํ์ฌ ๋ฆฌ์คํธ ADT๋ฅผ ๊ตฌํํ ๊ฒฝ์ฐ
๋ฐ์ดํฐ๊ตฌ์กฐ์ ์ํ ๊ธฐ์ต์ฅ์ ์ฌ์ฉ๋: O(n)
size, isEmpty, get, set: O(1)
add, remove: O(n)
addFirst, removeFirst: O(n)
addLast, removeLast: O(1)
* ๋ฐฐ์ด์ ์ํ์ผ๋ก ์ด์ฉํ๋ฉด
addFirst, removeFirst: O(1)
์ด์ค์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํ ๊ตฌํ
๋จ์ผ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ํ์ฉํ์ฌ ๊ตฌํํ ์ ์์ง๋ง, ์ด๋ฒ์๋ ์ด์ค์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํด ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ๋ฐฐ์๋ณด์.
์ด์ค์ฐ๊ฒฐ๋ฆฌ์คํธ(doubly linked list)๋ฅผ ์ด์ฉํ๋ฉด ๋ฆฌ์คํธ ADT๋ฅผ ์์ฐ์ค๋ฝ๊ฒ ๊ตฌํํ ์ ์๋ค. ์ด์ค์ฐ๊ฒฐ๋ฆฌ์คํธ์ ๋ ธ๋ ๊ตฌ์ฑ๊ณผ ํน์ง์ ์ด์ ํฌ์คํ ์ ์ฐธ๊ณ ํ์.
https://mainyoung.tistory.com/21
์๋ฃ๊ตฌ์กฐ ๋ฐ ์ค์ต - [3] ๊ธฐ์ด ๋ฐ์ดํฐ ๊ตฌ์กฐ (๋ฐฐ์ด, ์ฐ๊ฒฐ๋ฆฌ์คํธ) (1)
๋ฐ์ดํฐ ๊ตฌ์กฐ์ ๊ธฐ๋ณธ ์ฌ๋ฃ ๋ฐ์ดํฐ๋ฅผ ๊ตฌ์ฑํ๋ ๊ธฐ๋ณธ ์ฌ๋ฃ๋ก๋ ๋ฐฐ์ด๊ณผ ์ฐ๊ฒฐ๋ฆฌ์คํธ๊ฐ ์กด์ฌํ๋ค. ์ด๋ ๊ณ ๊ธ ๋ฐ์ดํฐ๊ตฌ์กฐ๋ฅผ ๊ตฌ์ถํ๋ ๊ธฐ๋ณธ ์ฌ๋ฃ๋ก ์ฐ์ด๊ธฐ ๋๋ฌธ์ ์ ์์๋์ด์ผ ํ๋ค! ๋ฐฐ์ด (array) ์์ฐจ
mainyoung.tistory.com
์ด๋ฅผ ๊ตฌํํ๋ฉด์ Header ๋ ธ๋์ Trailer ๋ ธ๋๋ฅผ ์ ๊ทน์ ์ผ๋ก ํ์ฉํ๊ฒ ๋ค.
์์ get(r) ๋๋ set(r, e)๋ O(n) ์๊ฐ์ ์ง์ ๋ ์์ r์ ์์๋ฅผ ๋ฐํ ๋๋ ์ ์ฅํ๋ ๊ฒ์ด๋ค. ๋ํ ์ฐ๊ฒฐ๋ฆฌ์คํธ์์ ์์๋ 1์์ ์ถ๋ฐ๋ก ์ ์ ํ๋ค.
์ฌ๊ธฐ์ ์ฃผ์ํด์ผ ํ ์ ์ ๊ตฌํํ๋ฉด์ ์์ธ(Exception)๋ฅผ ์ฃผ์ํด์ผํ๋ค๋ ๊ฒ์ด๋ค. ์ด์ค์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์๊ฐํ ํ๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
์ด๊ธฐํ (initailization)
์ด๊ธฐ์๋ ์๋ฌด ๋ ธ๋๋ ์๋ค. ๋ฐ๋ผ์ Header ๋ ธ๋์ Trailer๋ ธ๋๋ง ์๋ก ์ฐ๊ฒฐํ๋ค. O(1) ์๊ฐ์ด ์์๋๋ค.
์ํ (Traversal)
์ฐ๊ฒฐ๋ฆฌ์คํธ์ ๋ชจ๋ ์์๋ค์ ๋ฐฉ๋ฌธํ๋ฉฐ, Printํด๋ ์ข๋ค. O(n) ์๊ฐ์ด ์์๋๋ค.
์ด๋ ํฌ์ธํฐ์ Header์ next๋ฅผ ์ ์ฅํด์ ์ฌ์ฉํ๋ค!
์ฝ์ (Insertion)
์ด์ค์ฐ๊ฒฐ๋ฆฌ์คํธ์ ์ง์ ๋ ์์ r์ ์์ e๋ฅผ ์ฝ์ ํ๋ ์์ ์ด๋ค. O(n) ์๊ฐ์ด ์์๋๋ค.
์ด๋ฒ์๋ ์์ add(rank, X)์ ์๊ฐํfmf ๋ณด์ – ์ฌ๊ธฐ์ rank = 3์ผ๋ก ์ค์ ํ๋ค.
๊ธฐ์กด์๋ rank 3 ์ C๊ฐ ์์์ง๋ง, ์ฝ์ ์ ์ํด B์ C์ ์ด์ค์ฐ๊ฒฐ์ ๋๊ณ B์ X, X์ C์ ์ด์ค์ฐ๊ฒฐ์ ๊ตฌ์ฑํ๋ค.
์ญ์ (Deletion)
์ด์ค์ฐ๊ฒฐ๋ฆฌ์คํธ์ ์ง์ ๋ ์์ r์ ๋ ธ๋๋ฅผ ์ญ์ ํ๊ณ ์์๋ฅผ ๋ฐํํ๋ค. O(n) ์๊ฐ์ด ์์๋๋ค.
rank 3๊ณผ ์ฐ๊ฒฐ๋ B์ Trailer์ ์ด์ค์ฐ๊ฒฐ์ ๋๊ณ B์ Trailer๋ฅผ ์ด์ค์ฐ๊ฒฐํ๋ค. ์ดํ C๋ฅผ ์ญ์ ํ๋ค.
์ฑ๋ฅ (Performance)
์ด์ค์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํ ๋ฆฌ์คํธ ADT๋ฅผ ๊ตฌํํ ๊ฒฝ์ฐ ์ฑ๋ฅ์ ๋ค์๊ณผ ๊ฐ๋ค.
์ฐ๊ฒฐ๋ฆฌ์คํธ์ ๊ฐ ์์์ ์ฌ์ฉ๋๋ ๊ธฐ์ต์ฅ์: O(1)
N๊ฐ์ ์์๋ก ๊ตฌ์ฑ๋ ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ์ํด ์ฌ์ฉ๋๋ ๊ธฐ์ต์ฅ์: O(n)
size, isEmpty: O(1)
get, set, add, remove: O(n)
addFirst, addLast, removeFirst, removeLast: O(1)
๋ฐฐ์ด๊ณผ ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ์ฑ๋ฅ์ ์์ฝํ์๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
์์ | ๋ฐฐ์ด | ์ฐ๊ฒฐ๋ฆฌ์คํธ |
size, isEmpty | 1 | 1 |
get, set | 1 | n |
add, remove | n | n |
addFirst, removeFirst | n | 1 |
addLast, removeLast | 1 | 1 |