Array์ด๋?
Array๋ ์ฐ๊ด๋ Data๋ฅผ ๋ฉ๋ชจ๋ฆฌ์์ ์ฐ์์ ์ด๋ฉฐ ์์ฐจ์ ์ผ๋ก ๋ฏธ๋ฆฌ ํ ๋น๋ ํฌ๊ธฐ๋งํผ ์ ์ฅํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
Array์ ํน์ง
- ๊ณ ์ ๋ ์ ์ฅ ๊ณต๊ฐ(fixed-size)
- ์์ฐจ์ ์ธ ๋ฐ์ดํฐ ์ ์ฅ(order)
Array์ ์ฅ์ ์ lookup๊ณผ append๊ฐ ๋น ๋ฅด๋ค๋ ๊ฒ์ด๋ค.
์ฆ, ์กฐํ๋ฅผ ์์ฃผ ํด์ผ๋๋ ์์ ์์๋ Array ์๋ฃ๊ตฌ์กฐ๋ฅผ ๋ง์ด ์ด๋ค.
Array ์๊ฐ๋ณต์ก๋
Array | |
access | O(1) |
append | O(1) |
๋ง์ง๋ง ์์ delete |
O(1) |
insertion | O(n) |
deletion | O(n) |
search | O(n) |
์์ํ Array์ size๋ณด๋ค ๋ ๋ง์ ์์ data๋ฅผ ์ ์ฅํ๊ฒ ๋ ๋, ํด๊ฒฐ ๋ฐฉ๋ฒ์?
๊ธฐ์กด size๋ณด๋ค ๋ ํฐ Array๋ฅผ ์ ์ธํ์ฌ ๋ฐ์ดํฐ๋ฅผ ์ฎ๊ฒจ ํ ๋นํ๋ค.
๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ ์ฎ๊ฒผ๋ค๋ฉด ๊ธฐ์กด Array๋ ๋ฉ๋ชจ๋ฆฌ์์ ์ญ์ ํ๋ฉด ๋๋ค.
์ด๋ฐ์์ผ๋ก ๋์ ์ผ๋ก ๋ฐฐ์ด์ ํฌ๊ธฐ๋ฅผ ์กฐ์ ํ๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ Dynamic array๋ผ๊ณ ํ๋ค.
๋ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ผ๋ก๋, size๋ฅผ ์์ธกํ๊ธฐ ์ฝ์ง ์๋ค๋ฉด Array ๋์ Linked list๋ฅผ ์ฌ์ฉํจ์ผ๋ก์จ ๋ฐ์ดํฐ๊ฐ ์ถ๊ฐ๋ ๋๋ง๋ค ๋ฉ๋ชจ๋ฆฌ๊ณต๊ฐ์ ํ ๋น๋ฐ๋ ๋ฐฉ์์ ์ฌ์ฉํ๋ฉด ๋๋ค.
Dynamic Array ๋?
Array์ ๊ฒฝ์ฐ size๊ฐ ๊ณ ์ ๋์๊ธฐ ๋๋ฌธ์ ์ ์ธ์์ ์ค์ ํ size๋ณด๋ค ๋ง์ ๊ฐ์์ data๊ฐ ์ถ๊ฐ๋๋ฉด ์ ์ฅํ ์ ์๋ค.
ํ์ง๋ง Dynamic Array๋ ์ ์ฅ๊ณต๊ฐ์ด ๊ฐ๋ ์ฐจ๊ฒ ๋๋ฉด resize๋ฅผ ํ์ฌ ์ ๋์ ์ผ๋ก size๋ฅผ ์กฐ์ ํ์ฌ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
Dynamic Array ํน์ง?
- resize์ ํ๋ ๋ฐฉ์
- ๋ฐ์ดํฐ ์ถ๊ฐํ ๋์ ์๊ฐ๋ณต์ก๋
resize ํ๋ ๋ฐฉ์
Dynamic Array๋ size๋ฅผ ์๋์ ์ผ๋ก resizeing์ ํ๋ Array์ด๋ค.
๊ธฐ์กด์ ๊ณ ์ ๋ size๋ฅผ ๊ฐ์ง Static Array์ ํ๊ณ์ ์ ๋ณด์ํ๊ณ ์ ๊ณ ์๋๋ค.
Dynamic Array๋ data๋ฅผ ๊ณ์ ์ถ๊ฐํ๋ค๊ฐ ๊ธฐ์กด์ ํ ๋น๋ memory๋ฅผ ์ด๊ณผํ๊ฒ ๋๋ฉด, size๋ฅผ ๋๋ฆฐ ๋ฐฐ์ด์ ์ ์ธํ๊ณ ๊ทธ๊ณณ์ผ๋ก ๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ ์ฎ๊น์ผ๋ก์จ ๋์ด๋ ํฌ๊ธฐ์ size๋ฅผ ๊ฐ์ง ๋ฐฐ์ด์ ์ฌํ์์ํจ๋ค. ์ด๋ฅผ resize๋ผ๊ณ ํ๋ค.
resizing์ ํ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์๋๋ฐ, ๋ํ์ ์ผ๋ก ๊ธฐ์กด Array size์ 2๋ฐฐ๋ฅผ ํ ๋นํ๋ doubling์ด ์๋ค.
Doubling
resize์ ๋ํ์ ์ธ ๋ฐฉ๋ฒ์ผ๋ก Doubling์ด ์๋ค. ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐ(O(1)) ํ๋ค๊ฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ด๊ณผํ๊ฒ ๋๋ฉด ๊ธฐ์กด ๋ฐฐ์ด์ size๋ณด๋ค ๋ ๋ฐฐ ํฐ ๋ฐฐ์ด์ ์ ์ธํ๊ณ ๋ฐ์ดํฐ๋ฅผ ์ผ์ผ์ด ์ฎ๊ธฐ๋ ๋ฐฉ๋ฒ์ด๋ค.
n๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ผ์ผ์ด ์ฎ๊ฒจ์ผ ํ๋ฏ๋ก O(n) ๋ฐฉ๋ฒ์ด๋ค.
๊ธฐํ๊ธ์์ (geometric expansion) ์ฆ๊ฐ ๋ฐฉ์์ผ๋ก ์ฆ๊ฐํด ๊ธฐ์กด ํฌ๊ธฐ์ 2๋ฐฐ๋ก ์ฆ๊ฐํ๋ฉฐ, ์ฌ์ฉ ๊ณต๊ฐ์ด ์ค์ด๋ค๋ฉด ์๋์ผ๋ก ๊ฐ์ํ๋ค.
๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐํ ๋ ์๊ฐ ๋ณต์ก๋
๋ถํ ์ํ ์๊ฐ๋ณต์๋ Amortized time complexity
Dynamic array์ ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐํ ๋๋ง๋ค O(1)์ ์๊ฐ์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
์ถ๊ฐ๋ฅผ ํ๋ค๊ฐ ๋ฏธ๋ฆฌ ์ ์ธ๋ size๋ฅผ ๋์ด์๋ ์๊ฐ์ resize๋ฅผ ํ๊ฒ ๋๋ค.
์ด๋๋ ์ผ์ผ์ด ๋ฐ์ดํฐ๋ฅผ ๋ชจ๋ ์ฎ๊ฒจ์ผ ๋๊ธฐ ๋๋ฌธ์ ์ด ๋ ๋งํผ์ O(n)์ ์๊ฐ์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
→ ๊ทธ๋ ๋ค๋ฉด ๊ฒฐ๊ณผ์ ์ผ๋ก ๋ฐ์ดํฐ ์ถ๊ฐ์ ์๊ฐ๋ณต์ก๋๋ O(1) ์ผ๊น? O(n) ์ผ๊น?
append์ ์ด ๊ณผ์ ์ ์ดํด๋ณด๋ฉด ๋ฐ์ดํฐ๋ฅผ ๋ง์ง๋ง ์ธ๋ฑ์ค์ ์ถ๊ฐํ๋(O(1)) ์์ ์ด ๋๋ค์์ด๊ณ ,
size๋ฅผ ๋์ด์ค ๋๋ size๋ฅผ ๋ ๋ฐฐ ๋๋ฆฌ๊ณ ๋ฐ์ดํฐ๋ฅผ ์ผ์ผ์ด ์ฎ๊ธฐ๋ ๊ณผ์ (resize O(n))์ด ์์ฃผ ๊ฐ๋ ๋ฐ์ํ๋ค.
๊ฒฐ๋ก ๋ถํฐ ๋งํ์๋ฉด append์ ์ ์ฒด์ ์ธ ์๊ฐ๋ณต์ก๋๋ O(1)์ด๋ค. ์ข ๋ ์ ํํ๋ amortized O(1)์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค.
์ฆ, ๊ฐ๋ ๋ฐ์ํ๋ O(n)์ resizeํ๋ ์๊ฐ์ ์์ฃผ ๋ฐ์ํ๋ O(1)์ ์์ ๋ค์ด ๋ถ๋ดํด์ ๋๋ ๊ฐ์ง์ผ๋ก์จ ์ ์ฒด์ ์ผ๋ก O(1)์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค๊ณ ์๊ฐํ๋ฉด ๋๋ค.
Dynamic Array์ Linked list ๋น๊ต ์ฅ๋จ์
Linked List์ ๋น๊ตํ์ ๋, Dynamic Array์ ์ฅ์ ์
- ๋ฐ์ดํฐ ์ ๊ทผ๊ณผ ํ ๋น์ด O(1)๋ก ๊ต์ฅํ ๋น ๋ฅด๋ค.
์ด๋ index ์ ๊ทผํ๋ ๋ฐฉ๋ฒ์ด๋ ์ฐ์ ์ ์ธ ์ฐ์ฐ [๋ฐฐ์ด ์ฒซ data์ ์ฃผ์๊ฐ] + [offset]์ผ๋ก ์ด๋ฃจ์ด์ ธ ์๊ธฐ ๋๋ฌธ์ด๋ค. (random access) - Dynamic Array์ ๋งจ ๋ค์ ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐํ๊ฑฐ๋ ์ญ์ ํ๋ ๊ฒ์ด ์๋์ ์ผ๋ก ๋น ๋ฅด๋ค. O(1)
Linked List์ ๋น๊ตํ์ ๋, Dynamic Array์ ๋จ์ ์
- Dynamic Array์ ๋งจ ๋์ด ์๋ ๊ณณ์ data๋ฅผ insert or removeํ ๋, ๋๋ฆฐํธ์ด๋ค.(O(n))
๋๋ฆฐ ์ด์ ๋ ๋ฉ๋ชจ๋ฆฌ ์์์ ์ฐ์์ผ๋ก ๋ฐ์ดํฐ๋ค์ด ์ ์ฅ๋์ด ์๊ธฐ ๋๋ฌธ์, ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐ ์ญ์ ํ ๋ ๋ค์ ์๋ data๋ค์ ๋ชจ๋ ํ์นธ์ฉ shift ํด์ผ๋๊ธฐ ๋๋ฌธ์ด๋ค. - resize๋ฅผ ํด์ผํ ๋, ์์์น ๋ชปํ๊ฒ ํ์ ํ ๋ฎ์ performance๊ฐ ๋ฐ์ํ๋ค.
- resize์ ์๊ฐ์ด ๋ง์ด ๊ฑธ๋ฆฌ๋ฉฐ ํ์ํ ๊ฒ ์ด์์ผ๋ก memory ๊ณต๊ฐ์ ํ ๋น ๋ฐ๋๋ค.
๋ฐ๋ผ์ ์ฌ์ฉํ์ง ์๊ณ ๋ญ๋น๋๋ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ด ๋ฐ์ํ๋ค.
Linked List ๋?
Linked List๋ Node๋ผ๋ ๊ตฌ์กฐ์ฒด๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. Node๋ ๋ฐ์ดํฐ ๊ฐ๊ณผ ๋ค์ Node์ address๋ฅผ ์ ์ฅํ๋ค. Linked List๋ ๋ฌผ๋ฆฌ์ ์ธ ๋ฉ๋ชจ๋ฆฌ์์์๋ ๋น์ฐ์์ ์ผ๋ก ์ ์ฅ์ด ๋์ง๋ง Linked list๋ฅผ ๊ตฌ์ฑํ๋ ๊ฐ๊ฐ์ Node๊ฐ next Node์ address๋ฅผ ๊ฐ๋ฆฌํด์ผ๋ก์จ ๋ ผ๋ฆฌ์ ์ธ ์ฐ์์ฑ์ ๊ฐ์ง ์๋ฃ๊ตฌ์กฐ์ด๋ค.
Linked List๋ tree, graph๋ฑ ๋ค๋ฅธ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๊ตฌํํ ๋ ์์ฃผ ์ฐ์ด๋ ๊ธฐ๋ณธ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
Linked list๋ ๋ฉ๋ชจ๋ฆฌ์์์ ๋ถ์ฐ์์ ์ผ๋ก ๋ฐ์ดํฐ๊ฐ ์ ์ฅ๋๋ ์ ๊ณผ Node์ next address๋ฅผ ํตํด ๋ถ์ฐ์์ ์ธ ๋ฐ์ดํฐ๋ฅผ ์ฐ๊ฒฐํ์ฌ ๋ ผ๋ฆฌ์ ์ฐ์์ฑ์ ๋ณด์ฅํ๋ค๋ ์ ์ด ํต์ฌ์ด๋ค.
๋ฐ์ดํฐ๊ฐ ์ถ๊ฐ๋๋ ์์ ์์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํ๊ธฐ ๋๋ฌธ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ข ๋ ํจ์จ์ ์ผ๋ก ์ฌ์ฉํ ์ ์๋ค.
๋ ผ๋ฆฌ์ ์ฐ์์ฑ
๊ฐ Node๋ค์ next address ์ ๋ณด๋ฅผ ๊ฐ์ง๊ณ ์๊ธฐ ๋๋ฌธ์ ๋ ผ๋ฆฌ์ ์ผ๋ก ์ฐ์์ฑ์ ์ ์งํ๋ฉด์ ์ฐ๊ฒฐ๋์ด ์๋ค.
Array์ ๊ฒฝ์ฐ ์ฐ์์ฑ์ ์ ์งํ๊ธฐ ์ํด ๋ฌผ๋ฆฌ์ ๋ฉ๋ชจ๋ฆฌ ์์์ ์์ฐจ์ ์ผ๋ก ์ ์ฅํ๋ ๋ฐฉ๋ฒ์ ์ฌ์ฉํ์๊ณ ,
Linked list๋ ๋ฉ๋ชจ๋ฆฌ์์ ์ฐ์์ฑ์ ์ ์งํ์ง ์์๋ ๋๊ธฐ ๋๋ฌธ์ ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ์ด ์ข ๋ ์์ ๋ก์ด ๋์ , Next address๋ฅผ ์ถ๊ฐ์ ์ผ๋ก ์ ์ฅํด์ผ ํ๊ธฐ ๋๋ฌธ์ ๋ฐ์ดํฐ ํ๋๋น ์ฐจ์งํ๋ ๋ฉ๋ชจ๋ฆฌ๊ฐ ๋ ์ปค์ง๊ฒ ๋๋ค.
Linked List๊ฐ ์ฐ์์ ์ผ๋ก ์ ์ฅ๋ ๊ฒ์ฒ๋ผ ๋ณด์ด์ง๋ง ์ค์ ๋ก ๋ฉ๋ชจ๋ฆฌ์์์๋ ๋ถ์ฐ์์ ์ด๋ค.
์๊ฐ๋ณต์ก๋
Array์ ๊ฒฝ์ฐ ์ค๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ /์ญ์ ํ๊ฒ ๋๋ฉด ํด๋น ์ธ๋ฑ์ค ๋ค์ ์๋ ๋ชจ๋ ์์๋ค์ shift๋ฅผ ํด์ผ๋ง ํ๋ค.
๊ทธ๋ฌ๋ค ๋ณด๋ O(n)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ๊ฒ ๋์๋ค. ํ์ง๋ง Linked list๋ฅผ ๋ฌผ๋ฆฌ์ ์ผ๋ก ์ฎ๊ธธ ํ์์์ด next address๊ฐ ๊ฐ๋ฆฌํค๋ ์ฃผ์๊ฐ๋ง ๋ณ๊ฒฝํ๋ฉด ๋๊ธฐ ๋๋ฌธ์ O(1)์ ์๊ฐ๋ณต์ก๋๋ก ์ฝ์ /์ญ์ ๊ฐ ๊ฐ๋ฅํ๋ค.
Linked list | |
access | O(n) |
search | O(n) |
insertion | O(1) |
deletion | O(1) |
๐Array vs Linked list ๋น๊ต ๋ฐ ์ค๋ช
Array๋ ๋ฉ๋ชจ๋ฆฌ ์์์ ์ฐ์์ ์ผ๋ก ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
Linked List๋ ๋ฉ๋ชจ๋ฆฌ์์์๋ ์ฐ์์ ์ด์ง ์์ง๋ง, ๊ฐ๊ฐ์ ์์๊ฐ ๋ค์ ์์์ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๊ฐ์ ์ ์ฅํด ๋์์ผ๋ก์จ ๋ ผ๋ฆฌ์ ์ฐ์์ฑ์ ์ ์งํ๋ค.
์๊ฐ๋ณต์ก๋ ๋น๊ต
Array | Linked list | |
๋ฐ์ดํฐ ์กฐํ | O(1) | O(n) |
์ฝ์ / ์ญ์ | O(n) | O(1) |
์ฆ, ์ผ๋ง๋งํผ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ์ง ๋ฏธ๋ฆฌ ์๊ณ ์๊ณ , ์กฐํ๋ฅผ ๋ง์ด ํ๋ค๋ฉด Array๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด ์ข๋ค.
๋ฐ๋ฉด, ๋ช ๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ์ง ๋ถํ์คํ๊ณ ์ฝ์ ์ญ์ ๊ฐ ์ฆ๋ค๋ฉด Linked list๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด ์ ๋ฆฌํ๋ค.
๋ฉ๋ชจ๋ฆฌ ๊ตฌ์กฐ
Array์ Linked list์ ์ฃผ๋ ์ฐจ์ด์ ๋ค์ ๋ฉ๋ชจ๋ฆฌ ๊ตฌ์กฐ์ ๊ธฐ์ธํ๋ค.
Array๋ ๋ฉ๋ชจ๋ฆฌ์์์ ์ฐ์์ ์ผ๋ก ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๊ณ ,
Linked list๋ ๋ถ์ฐ์์ ์ผ๋ก ์ ์ฅํ๋ค.
๋ฉ๋ชจ๋ฆฌ ๊ตฌ์กฐ์ ์ฐจ์ด๋ก ์ธํด operation ๊ตฌํ ๋ฐฉ๋ฒ์ด ๋ค๋ฅด๊ณ ์๊ฐ๋ณต์ก๋๋ ๋ค๋ฅด๋ฉฐ ๋ฉ๋ชจ๋ฆฌ ํ์ฉ๋์์๋ ์ฐจ์ด๊ฐ ์๋ค.
์ํฉ์ ๋ฐ๋ผ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํจ์จ์ ์ผ๋ก ์ฌ์ฉํ ์ ์๋ ์๋ฃ๊ตฌ์กฐ๊ฐ ๋ฌ๋ผ์ง๋ค.
์กฐํ (lookup)
Array | ๋ฉ๋ชจ๋ฆฌ์์์ ์ฐ์์ ์ผ๋ก ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๊ธฐ ๋๋ฌธ์ ์ ์ฅ๋ ๋ฐ์ดํฐ์ ์ฆ์ ์ ๊ทผ(random access O(1)) |
Linked list | ๋ฉ๋ชจ๋ฆฌ์์์ ๋ถ์ฐ์์ ์ผ๋ก ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๊ธฐ ๋๋ฌธ์ ์์ฐจ ์ ๊ทผ(Sequential Access)๋ง ๊ฐ๋ฅ ์ฆ, ํน์ index์ ๋ฐ์ดํฐ๋ฅผ ์กฐํํ๊ธฐ ์ํด O(n)์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค. |
์ฝ์ / ์ญ์ (insert / delete)
Array | ๋งจ ๋ง์ง๋ง ์์๋ฅผ ์ถ๊ฐ/์ญ์ ํ๋ฉด ์๊ฐ๋ณต์ก๋๊ฐ O(1)์ด๋ค. ํ์ง๋ง ๋งจ ๋ง์ง๋ง ์์๊ฐ ์๋ ์ค๊ฐ์ ์๋ ์์๋ฅผ ์ฝ์ /์ญ์ ํ๋ฉด ํด๋น ์์๋ณด๋ค ํฐ ์ธ๋ฑ์ค์ ์์๋ค์ ํ ์นธ์ฉ shift ํด์ค์ผ ํ๋ ๋น์ฉ์ด ๋ฐ์ํ๋ค. ๋ฐ๋ผ์ ์ด ๊ฒฝ์ฐ์๋ ์๊ฐ๋ณต์ก๋๊ฐ O(n)์ด ๋๋ค. |
Linked list | ์ด๋ ์์๋ฅผ ์ถ๊ฐ/์ญ์ ํ๋๋ผ๋ node์์ ๋ค์ ์ฃผ์๋ฅผ ๊ฐ๋ฆฌํค๋ ๋ถ๋ถ๋ง ๋ค๋ฅธ ์ฃผ์ ๊ฐ์ผ๋ก ๋ณ๊ฒฝํ๋ฉด ๋๊ธฐ ๋๋ฌธ์ shiftํ ํ์ ์์ด ์๊ฐ๋ณต์ก๋๊ฐ O(1)์ด๋ค. ํ์ง๋ง Linked list์ ๊ฒฝ์ฐ ์ถ๊ฐ/์ญ์ ๋ฅผ ํ๋ ค๋ index๊น์ง ๋๋ฌํ๋๋ฐ O(n)์ ์๊ฐ์ด ๊ฑธ๋ฆฌ๊ธฐ ๋๋ฌธ์, ์ค์ง์ ์ผ๋ก Linked List๋ ์ถ๊ฐ/์ญ์ ์์ O(n)์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค๊ณ ๋ณผ ์ ์๋ค. |
memory
Array | Array์ ์ฃผ๋ ์ฅ์ ์ ๋ฐ์ดํฐ ์ ๊ทผ๊ณผ append๊ฐ ๋น ๋ฅด๋ค๋ ๊ฒ์ด๋ค. ํ์ง๋ง ๋ฉ๋ชจ๋ฆฌ ๋ญ๋น๋ผ๋ ๋จ์ ์ด ์๋ค. ๋ฐฐ์ด์ ์ ์ธ์์ fixed size๋ฅผ ์ค์ ํ์ฌ ๋ฉ๋ชจ๋ฆฌ ํ ๋น์ ํ๋ค. ์ฆ, ๋ฐ์ดํฐ๊ฐ ์ ์ฅ๋์ด ์์ง ์๋๋ผ๋ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฐจ์งํ๊ณ ์๊ธฐ ๋๋ฌธ์ ๋ฉ๋ชจ๋ฆฌ ๋ญ๋น๊ฐ ๋ฐ์ํ๋ค. |
Linked list | Linked list๋ runtime์ค์์๋ size๋ฅผ ๋๋ฆฌ๊ณ ์ค์ผ ์ ์๋ค. initial size๋ฅผ ๊ณ ๋ฏผํ ํ์ ์๊ณ , ํ์ํ ๋งํผ memory allocation์ ํ์ฌ ๋ฉ๋ชจ๋ฆฌ ๋ญ๋น๊ฐ ์๋ค. |
์ ๋ฆฌ
์ด๋ ์ํฉ์ Linked list๋ฅผ ์ฐ๋๊ฒ Array๋ณด๋ค ๋ ๋์๊น?
- O(1)์ผ๋ก ์ฝ์ /์ญ์ ๋ฅผ ์์ฃผ ํด์ผ ๋ ๋
- ๋ฐ์ดํฐ ์์ ์์ธก ํ ์ ์์ ๋
- ์กฐํ ์์ ์ ๋ณ๋ก ํ์ง ์์ ๋
์ด๋ ์ํฉ์ Array๋ฅผ ์ฐ๋๊ฒ Linked list๋ณด๋ค ๋ ๋์๊น?
- ์กฐํ(์ฆ์ ์ ๊ทผ) ์์ ์ ์์ฃผ ํด์ผ๋ ๋
- Array๋ฅผ ์ ์ธํ ๋น์์ ๋ฐ์ดํฐ์ ๊ฐ์๋ฅผ ๋ฏธ๋ฆฌ ์๊ณ ์์ ๋
- ๋ฐ์ดํฐ๋ฅผ ๋ฐ๋ณต๋ฌธ์ ํตํด์ ๋น ๋ฅด๊ฒ ์ํํ ๋
- ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ ๊ฒ ์ฐ๋๊ฒ ์ค์ํ ์ํฉ์ผ ๋
Linked list ๋ณด๋จ Array๊ฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ ๊ฒ ์ฐจ์ง ํ๊ธฐ ๋๋ฌธ์ ๋ฏธ๋ฆฌ ๋ค์ด์ฌ ์์ ์๊ณ ๋ง ์๋ค๋ฉด Array๊ฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ ํจ์จ์ ์ผ๋ก ์ฌ์ฉํ ์ ์๋ค.
Array์ Linked list์ memory allocation์ ์ธ์ ์ผ์ด๋๋ฉฐ, ๋ฉ๋ชจ๋ฆฌ์ ์ด๋ ์์ญ์ ํ ๋น ๋ฐ์๊น?
Array | compile ๋จ๊ณ์์ memory allocation์ด ์ผ์ด๋๋ค. ์ด๋ฅผ Static Memory Allocation์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค. ์ด ๊ฒฝ์ฐ Stack memory ์์ญ์ ํ ๋น ๋๋ค. |
Linked list | runtime ๋จ๊ณ์์ ์๋ก์ด node๊ฐ ์ถ๊ฐ๋ ๋๋ง๋ค memory allocation์ด ์ผ์ด๋๋ค. Dynamic Memory Allocation์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค. Heap ๋ฉ๋ชจ๋ฆฌ ์์ญ์ ํ ๋น๋๋ค. |
์ฐธ๊ณ
https://media.geeksforgeeks.org/wp-content/uploads/20220829110944/LLdrawio.png
'๐ป Computer Science > ์๋ฃ๊ตฌ์กฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์ธ์(Argument)์ ํ๋ผ๋ฏธํฐ(Parameter) ์ฐจ์ด (0) | 2024.02.16 |
---|---|
Hash table & BST(Binary Search Tree) ๋? (0) | 2023.05.25 |
[์๋ฃ๊ตฌ์กฐ] ํ Queue & ์คํ Stack & ์ฐ์ ์์ํ priority queue & ํ Heap ์ด๋? (0) | 2023.05.25 |