[์๋ฃ๊ตฌ์กฐ] ๋ฐฐ์ด(Array) vs ์ฐ๊ฒฐ ๋ฆฌ์คํธ(LinkedList) ํต์ฌ ๋น๊ต
2025. 9. 18. 01:08ใ์๋ฃ๊ตฌ์กฐ
๋ฐฐ์ด (Array)
- ์ฐ์ ๊ณต๊ฐ์ ๊ฐ์ด ์ฑ์์ ธ ์๋ ํํ์ ์๋ฃ๊ตฌ์กฐ์ ๋๋ค.
- ์ธ๋ฑ์ค๋ฅผ ํตํด ์ฐธ์กฐํ ์ ์์ผ๋ฉฐ, ์ ์ธํ ์๋ฃ ๊ฐ๋ง ์ ์ฅ ๊ฐ๋ฅํฉ๋๋ค.
- ๋ฐฐ์ด ์ ์ธ ์ ํฌ๊ธฐ๋ฅผ ์ง์ ํ๊ณ ์ดํ ํฌ๊ธฐ๋ฅผ ์กฐ์ ํ ์ ์์ต๋๋ค.
- ์กฐํ ๋ฐ ์์ ์๋ O(1), ์ฝ์ ๋ฐ ์ญ์ ์๋ O(n)์ผ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋๋ค.


๋ฆฌ์คํธ (Lincked List)
- ๊ฐ๊ณผ ํฌ์ธํฐ๋ค์ ๋ฌถ์ ๋ ธ๋๋ผ๋ ๊ฒ์ ํฌ์ธํฐ๋ก ์ฐ๊ฒฐํ ๊ตฌ์กฐ์ ๋๋ค.
- ์ ์ธ ์ ํฌ๊ธฐ๋ฅผ ๋ณ๋๋ก ์ง์ ํ์ง ์์๋ ๋ฉ๋๋ค. (๊ฐ๋ณ์ )
- ํฌ์ธํฐ๋ฅผ ์ ์ฅํ ๊ณต๊ฐ์ด ํ์ํ๋ฏ๋ก ๋ฐฐ์ด๋ณด๋ค ๊ตฌ์กฐ๊ฐ ๋ณต์กํฉ๋๋ค.
- ๊ฐ์ ์ ๊ทผ์ ์ํด์๋ Head(์ฒ์)๋ถํฐ ์์๋๋ก ์ ๊ทผํด์ผ ํ๋ฏ๋ก O(n) ๋ณต์ก๋๊ฐ ๊ฑธ๋ฆฝ๋๋ค.
- ํฌ์ธํฐ๋ก ์ฐ๊ฒฐ์ด ๋์ด ์์ด ๋ฐ์ดํฐ๋ฅผ ์ฝ์ ํ๊ฑฐ๋ ์ญ์ ํ๋ ๋ฐ์๋ O(1) ๋ณต์ก๋๊ฐ ๊ฑธ๋ฆฝ๋๋ค.


๋ฐฐ์ด๊ณผ ๋ฆฌ์คํธ๋ฅผ ๋ค์ ์ ๋ฆฌํด ๋ณด๋, ์์ผ๋ก๋ ์ฝ๋๋ฅผ ์์ฑํ๊ธฐ ์ ์ '์ด ๋ฐ์ดํฐ๋ ์ด๋ป๊ฒ ์ฌ์ฉ๋ ๊น?'๋ผ๋ ์ง๋ฌธ์ ๋จผ์ ๋์ ธ์ผ๊ฒ ๋ค๋ ์๊ฐ์ด ๋ค์์ต๋๋ค. ๊ฒฐ๊ตญ ์ข์ ์ฑ๋ฅ์ ๋ด๋ ์ฝ๋๋ ๋ฐ์ดํฐ์ ํน์ฑ์ ๋ง๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ํํ๋ ์์ ๋ํ ์ผ์์๋ถํฐ ์์๋๋ค๋ ๊ฒ์ ๋๊ผ์ต๋๋ค.