๐ ๋ฐฐ์ด(Array) ยท ๋์ ๋ฐฐ์ด(Dynamic Array) ยท ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Linked List) ๋น๊ต ์ ๋ฆฌ
๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ด๋ฉด์๋ ์์ฃผ ๋ฑ์ฅํ๋ ์ ํ ์๋ฃ๊ตฌ์กฐ 3๊ฐ์ง ๋ฐฐ์ด, ๋ฆฌ์คํธ, ๋งํฌ๋ ๋ฆฌ์คํธ์ ๋ํด ์์๋ณด์.
1. ๋ฐฐ์ด (Array)
๋ฐฐ์ด์ด๋ ๊ฐ์ ํ์ ์ ๋ฐ์ดํฐ๋ฅผ ์ฐ์๋ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ์ ์ฅํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.

๊ฐ ์์๋ ์ธ๋ฑ์ค๋ฅผ ํตํด ์ ๊ทผํ ์ ์์ผ๋ฉฐ ์ธ๋ฑ์ค๋ 0๋ถํฐ ์์ํ๋ค.
ํน์ง
๊ณ ์ ๋ ํฌ๊ธฐ
๋ฐฐ์ด์ ์์ฑ ์ ํฌ๊ธฐ๋ฅผ ์ง์ ํด์ผ ํ๋ฉฐ ํ ๋ฒ ์ ํด์ง ํฌ๊ธฐ๋ ๋ณ๊ฒฝํ ์ ์๋ค.
์ธ๋ฑ์ค๋ฅผ ํตํ ๋น ๋ฅธ ์ ๊ทผ
๋ฐฐ์ด์ ์ธ๋ฑ์ค๋ฅผ ์ฌ์ฉํ์ฌ ํน์ ์์น์ ๊ฐ์ O(1) ์๊ฐ์ ๋ฐ๋ก ์ ๊ทผํ ์ ์๋ค.
์ฐ์๋ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ์ฌ์ฉ
๋ฐฐ์ด์ ๋ฉ๋ชจ๋ฆฌ์์ ๋ฐ์ดํฐ๊ฐ ์ฐ์์ ์ผ๋ก ๋ฐฐ์น๋์ด ์์ด ์บ์ ์ ์ค๋ฅ ์ด ๋๊ณ ํผํฌ๋จผ์ค๊ฐ ์ข๋ค.
์ฝ์ /์ญ์ ์ ๋นํจ์จ์
์ค๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ ํ๊ฑฐ๋ ์ญ์ ํ๋ฉด ๋ค์ ์์๋ค์ ๋ชจ๋ ์ด๋์์ผ์ผ ํ๋ฏ๋ก ์ฑ๋ฅ์ด ๋จ์ด์ง ์ ์๋ค.
์๊ฐ ๋ณต์ก๋
๋์ ๋ฐฐ์ด(Dynamic Array)๊ณผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Linked List)๋ฅผ ์์๋ณด๊ธฐ ์ ์ ๋ฆฌ์คํธ๊ฐ ๋ฌด์์ธ์ง ์์๋ณด์.
๋ฆฌ์คํธ(List)๋?
๋ฆฌ์คํธ๋ ์์๊ฐ ์๋ ์์๋ค์ ๋ชจ์์ด๋ฉฐ ๋ค์๊ณผ ๊ฐ์ ์ฐ์ฐ์ ์ง์ํ๋ ์ถ์ ์๋ฃํ(ADT)์ด๋ค.
- get(i) - i ๋ฒ์งธ ์์ ์กฐํ
- insert(i, x) - i ๋ฒ์งธ ์์น์ x ์ฝ์
- delete(i) - i ๋ฒ์งธ ์์ ์ญ์
- append(x) - ๋งจ ๋ค์ x ์ถ๊ฐ
- length() - ์ ์ฒด ๊ธธ์ด ๋ฐํ
์ฆ ๋์ ๋ฐฐ์ด๊ณผ ๋งํฌ๋ ๋ฆฌ์คํธ๋ ๋ชจ๋ ์ด ๋ฆฌ์คํธ๋ ์ถ์ ๊ฐ๋
์ ์๋ก ๋ค๋ฅธ ๋ฐฉ์์ผ๋ก ๊ตฌํํ ๊ฒ์ด๋ค.
2. ๋์ ๋ฐฐ์ด (Dynamic Array)
๋์ ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ ๊ณ ์ ๋ ๋ฐฐ์ด์ ํ๊ณ๋ฅผ ๊ทน๋ณตํ๊ธฐ ์ํด ๋ง๋ค์ด์ง ์๋ฃ๊ตฌ์กฐ์ด๋ค. ์ฒ์์๋ ์ผ์ ํ ํฌ๊ธฐ๋ก ์์ํ์ง๋ง ์ ์ฅ ๊ณต๊ฐ์ด ๋ถ์กฑํด์ง๋ฉด ๋ ํฐ ๋ฐฐ์ด์ ์๋ก ๋ง๋ค๊ณ ๊ธฐ์กด ๋ฐ์ดํฐ๋ฅผ ๋ณต์ฌํ์ฌ ์๋์ผ๋ก ํฌ๊ธฐ๋ฅผ ํ์ฅํ๋ค.
๋ํ์ ์ธ ๋์ ๋ฐฐ์ด๋ก๋ Java์ ArrayList, Python์ list, JavaScript์ Array๊ฐ ์๋ค.
ํน์ง
๋ฐฐ์ด๊ณผ ์ ์ฌ
๊ธฐ๋ณธ์ ์ผ๋ก๋ ๋ฐฐ์ด์ด๊ธฐ ๋๋ฌธ์ ์ธ๋ฑ์ค๋ฅผ ํตํ ๋น ๋ฅธ ์ ๊ทผ, ์ฝ์ /์ญ์ ์ ๋นํจ์จ์ ์ด๋ผ๋ ๋ถ๋ถ์ ๋์ผํ๋ค.
๋์ ์ธ ํฌ๊ธฐ ์กฐ์
๋ฐฐ์ด์ด ๊ฐ๋ ์ฐจ๋ฉด ๋ ํฐ ๋ฐฐ์ด์ ์๋ก ๋ง๋ค๊ณ ๋ณต์ฌํ์ฌ์ ์๋์ผ๋ก ํฌ๊ธฐ๋ฅผ ํ์ฅํ๋ค.
์๊ฐ ๋ณต์ก๋
3. ์ฐ๊ฒฐ ๋ฆฌ์คํธ (Linked List)
์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ๋ ๋ฐฐ์ด์ฒ๋ผ ์ฐ์๋ ๊ณต๊ฐ์ ์ ์ฅํ์ง ์๊ณ ๊ฐ ์์(๋
ธ๋)๊ฐ ๋ค์ ์์๋ฅผ ํฌ์ธํฐ๋ฅผ ํตํด ๊ฐ๋ฆฌํค๋ ๋ฐฉ์์ผ๋ก ์ฐ๊ฒฐ๋ ์ ํ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
๊ฐ ๋
ธ๋๋ ๊ฐ๊ณผ ๋ค์ ๋
ธ๋์ ์ฃผ์๋ฅผ ํฌํจํ๋ฉฐ ๊ตฌ์กฐ์ ๋ฐ๋ผ ๋จ์ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Singly Linked List), ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Doubly Linked List), ์ํ ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Circular Linked List)๋ก ๋๋๋ค.
ํน์ง
๋น์ฐ์ ๋ฉ๋ชจ๋ฆฌ
๋ฐฐ์ด์ฒ๋ผ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ด ์ฐ์๋ ํ์ ์์ด ๋ ธ๋๋ผ๋ฆฌ ํฌ์ธํฐ๋ก ์ฐ๊ฒฐ๋๋ค.
์ฝ์ /์ญ์ ์ ํจ์จ์
์ค๊ฐ ์ฝ์ /์ญ์ ์ ํฌ์ธํฐ๋ง ์กฐ์ ํ๋ฉด ๋๋ฏ๋ก ์์น๋ฅผ ์๊ณ ์์ ๊ฒฝ์ฐ ๋น์ฉ์ด ๋ฎ๋ค.
์ ๊ทผ์ ๋นํจ์จ์
์์์ ์์น์ ์ ๊ทผํ๋ ค๋ฉด ์ฒ์๋ถํฐ ์์ฐจ ํ์ํด์ผ ํ๊ธฐ ๋๋ฌธ์ ๋นํจ์จ์ ์ด๋ค.
๋ฉ๋ชจ๋ฆฌ ์ค๋ฒํค๋
๊ฐ ๋ ธ๋๋ง๋ค ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋ ๊ณต๊ฐ ์ธ์ ํฌ์ธํฐ ๊ณต๊ฐ์ด ์ถ๊ฐ๋ก ํ์ํ๋ค.
์๊ฐ ๋ณต์ก๋
