Array
- ์ฐ๊ด๋ data๋ฅผ ๋ฉ๋ชจ๋ฆฌ ์์ ์ฐ์์ ์ด๋ฉฐ ์์ฐจ์ ์ผ๋ก ๋ฏธ๋ฆฌ ํ ๋น๋ ํฌ๊ธฐ๋งํผ ์ ์ฅํ๋ ์๋ฃ๊ตฌ์กฐ
- Linked List์ ๋น๊ต๊ฐ ๋๋ ํน์ฑ๋ค์ ์์ฃผ๋ก ์๊ฐํ๋ฉด ๊ธฐ์ตํ๊ธฐ ํธํ๋ค.
- ๋ฉ๋ชจ๋ฆฌ์ ์ ์ฅ๋๋ ๋ฐฉ์๊ณผ ๊ทธ์ ๋ฐ๋ฅธ ์ฝ์
/์ญ์ /์กฐํ ๋ฑ์ ์๊ฐ๋ณต์ก๋
- ํน์ง
- ๊ณ ์ ๋ ์ ์ฅ ๊ณต๊ฐ(fixed-size) → ๊ณต๊ฐ๋ ํจ๊ป ์ ์ธ
- ์์ฐจ์ ์ธ ๋ฐ์ดํฐ ์ ์ฅ(order) → ๊ฐ์ ๋ฐฐ์ด ๋ด์ ๋ฐ์ดํฐ๋ ์์ฐจ์ ์ผ๋ก ๋ฉ๋ชจ๋ฆฌ์ ์ ์ฅ๋จ
- ์ฐ์ฐ๋ค์ ์๊ฐ ๋ณต์ก๋
- access : O(1) → index๋ฅผ ํตํด ๋ฐ๋ก ์ ๊ทผ ; Random Access
- append : O(1) → ๊ฐ์ฅ ์ค๋ฅธ์ชฝ(๋) ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐํ๋ ๊ฒฝ์ฐ
- pop : O(1) → ๊ฐ์ฅ ์ค๋ฅธ์ชฝ(๋) ๋ฐ์ดํฐ๋ฅผ ์ ๊ฑฐํ๋ ๊ฒฝ์ฐ
- insertion : O(n) → ์ฝ์
ํ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ์นธ์ฉ ๋ฐ์ด์ค์ผํ๋ฏ๋ก
- deletion : O(n) → ์ ๊ฑฐ ํ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ์นธ์ฉ ๋น๊ฒจ์ค์ผํ๋ฏ๋ก
- search : O(n) → ํ๋ํ๋ ๊ฐ์ ํ์ธํด์ผํ๊ธฐ ๋๋ฌธ์
- ๋จ, ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ์ด์งํ์์ ์ด์ฉํ์ฌ O(logn)์ ์๊ฐ๋ณต์ก๋๊ฐ ๊ฐ๋ฅํ๋ค!!!
๊ถ๊ธ์ฆ
- ์์ํ ๊ฒ๋ณด๋ค ๋ ๋ง์ data๊ฐ ๋์ด์จ ๊ฒฝ์ฐ์ Array์ ์ด๋ป๊ฒ ์ ์ฅํด์ผํ ๊น?
- ๊ธฐ์กด size๋ณด๋ค ๋ ํฐ Array๋ฅผ ์ ์ธํ์ฌ ๋ฐ์ดํฐ๋ฅผ ์ฎ๊ธด ํ ๊ธฐ์กด Array๋ ๋ฉ๋ชจ๋ฆฌ์์ ์ญ์ → Dynamic Array(๋์ ๋ฐฐ์ด)
- Linked List๋ฅผ ์ฌ์ฉํ์ฌ ๋ฐ์ดํฐ๊ฐ ์ถ๊ฐ๋ ๋๋ง๋ค ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋น๋ฐ๋ ๋ฐฉ์ ์ฌ์ฉ