- ๋ ธ๋Node: ์ปดํจํฐ ๋ฉ๋ชจ๋ฆฌ ๊ณณ๊ณณ์ ํฉ์ด์ ธ ์๋ ๋ฐ์ดํฐ ์กฐ๊ฐ
- ๋ ธ๋ ๊ธฐ๋ฐ ์๋ฃ๊ตฌ์กฐ๋ ๋ฐ์ดํฐ๋ฅผ ์กฐ์งํ๊ณ ์ ๊ทผํ๋ ์๋ก์ด ๋ฐฉ๋ฒ์ ์ ๊ณตํ๋๋ฐ ์ฑ๋ฅ์ ํฐ ์ด์ ์ด ๋ง๋ค.
- 14์ฅ์์๋ ๊ฐ์ฅ ๊ฐ๋จํ ๋ ธ๋ ๊ธฐ๋ฐ ์๋ฃ๊ตฌ์กฐ์ธ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ดํด๋ณธ๋ค.
1. ์ฐ๊ฒฐ ๋ฆฌ์คํธ
- ์ฐ๊ฒฐ ๋ฆฌ์คํธLinked List๋ ๋ฐฐ์ด๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ํญ๋ชฉ์ ๋ฆฌ์คํธ๋ฅผ ํํํ๋ ์๋ฃ ๊ตฌ์กฐ๋ค.
- ์ปดํจํฐ์ ๋ค์ด ์๋ ๋ฉ๋ชจ๋ฆฌ๋ ๋ฐ์ดํฐ์กฐ๊ฐ์ ์ ์ฅํ๋ ์ ๋ค์ ๊ฑฐ๋ํ ์งํฉ์ผ๋ก ๋ํ๋ผ ์ ์๋ค.
- ์ฝ๋์์ ๋ฐฐ์ด์ ์์ฑํ๋ฉด ๋ฉ๋ชจ๋ฆฌ ๋ด์ ์ฐ์๋ ๋น ์ ๊ทธ๋ฃน์ ์ฐพ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ์ ์๋๋ก ํ ๋นํ๋ค.
- ์ปดํจํฐ๋ ์ด๋ค ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ ํ ๋ฒ์ ์ ๊ทผํ ์ ์์ผ๋ฏ๋ก ๋ฐฐ์ด ๋ด ์ด๋ค ์ธ๋ฑ์ค๋ ๋ฐ๋ก ๊ฐ ์ ์๋ค.
- ๊ทธ๋ฌ๋ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ๋ด ๋ฐ์ดํฐ๋ ์ฐ์๋ ๋ฉ๋ชจ๋ฆฌ ๋ธ๋ก์ด ์๋๋ผ ์ปดํจํฐ ๋ฉ๋ชจ๋ฆฌ ์ ์ฒด์ ๊ฑธ์ณ ์ฌ๋ฌ ์ ์ ํผ์ ธ ์์ ์ ์๋ค.
- ๋ฉ๋ชจ๋ฆฌ ๊ณณ๊ณณ์ ํฉ์ด์ง ์ฐ๊ฒฐ๋ ๋ฐ์ดํฐ๋ฅผ ๋ ธ๋๋ผ๊ณ ๋ถ๋ฅธ๋ค.
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ์์ ๊ฐ ๋ ธ๋๋ ๋ฆฌ์คํธ ๋ด ํ ํญ๋ชฉ์ ๋ํ๋ธ๋ค.
- ๊ฐ ๋ ธ๋๋ ์ฝ๊ฐ์ ์ถ๊ฐ ์ ๋ณด, ์ฆ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ๋ด์ ๋ค์ ๋ ธ๋์ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ ํฌํจํ๋ค.
- ์ด ์ถ๊ฐ ๋ฐ์ดํฐ, ์ฆ ๋ค์ ๋ ธ๋์ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ก์ ํฌ์ธํฐ๋ฅผ ๋งํฌ๋ผ๊ณ ๋ถ๋ฅธ๋ค.
- ๋ฐ์ดํฐ๊ฐ ์ปดํจํฐ ๋ฉ๋ชจ๋ฆฌ ์ ์ฒด์ ํฉ์ด์ง ์ ์๋ค๋ ์ ์์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๊ฐ ๋ฐฐ์ด๋ณด๋ค ์ ๋ฆฌํ ์ ์๋ค.
2. ์ฐ๊ฒฐ ๋ฆฌ์คํธ ๊ตฌํ
- Java์ฒ๋ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๊ฐ ๋ด์ฅ๋ ํ๋ก๊ทธ๋๋ฐ ์ธ์ด๋ ์๋ค.
- ๊ทธ๋ฌ๋ ์๋ ์ธ์ด๋ ๋ง๊ณ ์๊ฐ๋ณด๋ค ์ฝ๊ฒ ๊ตฌํํ ์ ์๋ค.
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ๋ค๋ฃฐ ๋๋ ์ฒซ ๋ฒ์งธ ๋ ธ๋์๋ง ์ฆ์ ์ ๊ทผํ ์ ์๋ค.
3. ์ฝ๊ธฐ
- ์ปดํจํฐ๋ O(1)์๊ฐ์ ๋ฐฐ์ด์์ ๊ฐ์ ์ฝ์ ์ ์๋ค.
- ํ๋ก๊ทธ๋จ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์ฒซ ๋ฒ์งธ ๋ ธ๋์ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ง ์๊ณ , ๋๋จธ์ง ๋ ธ๋๊ฐ ์ด๋์ ์๋์ง ๋ฐ๋ก ์์ง ๋ชปํ๋ค.
- ๋ฆฌ์คํธ์ ๋ง์ง๋ง ๋ ธ๋๋ฅผ ์ฝ์ผ๋ ค๋ฉด ๋ฆฌ์คํธ์ ๋ ธ๋๊ฐ N๊ฐ์ผ ๋ O(N)์๊ฐ์ด ํ์ํ๋ค.
4. ๊ฒ์
- ๋ฐฐ์ด์ ๊ฒ์์ O(N)์ด๋ค.
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๊ฒ์ ๋ํ O(N)์ด๋ค.
5. ์ฝ์
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ๊ฐ ๋ฐฐ์ด์ ๋นํด ๋๋ ทํ ์ฅ์ ์ ๋ณด์ผ ์ ์๋ ์ฐ์ฐ์ด ๋ฐ๋ก ์ฝ์ ์ด๋ค.
- ๋ฐฐ์ด ์ฝ์ ์์ ์ต์ ์ ์๋๋ฆฌ์ค๋ ํ๋ก๊ทธ๋จ์ด ์ธ๋ฑ์ค 0์ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ ํ ๋๋ค. ์ด๋์ ํจ์จ์ฑ์ O(N)์ด๋ค.
- ๊ทธ๋ฌ๋ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์ฝ์ ํจ์จ์ฑ์ O(1)์ด๋ค.
6. ์ญ์
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์ญ์ ๋ ๋งค์ฐ ๋น ๋ฅธ๋ฐ, ํนํ ๋ฆฌ์คํธ ์์์ ์ญ์ ํ ๋ ๋น ๋ฅด๋ค.
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ์์ ๋ ธ๋๋ฅผ ์ญ์ ํ๋ ค๋ฉด ๋ค๋ฅธ ๋ ธ๋์์ ์ฐ๊ฒฐ๊ณ ๋ฆฌ๋ฅผ ๋์ผ๋ฉด ๋๋ค.
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ์์ ๋ค๋ฅธ ๋ ธ๋์์ ์ฐ๊ฒฐ๊ณ ๋ฆฌ๋ฅผ ๋๋ ๊ฒ์ผ๋ก ๋ฆฌ์คํธ์์ ์ ๊ฑฐํ๋ฉด, ๊ทธ ๋ ธ๋์ ์ ๋ณด๋ ๋ฉ๋ชจ๋ฆฌ ์ด๋๊ฐ์ ๊ณ์ ์กด์ฌํ์ง๋ง ๋ ์ด์ ์ ํํ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ฅผ ๋ชจ๋ฅด๋ ์ํ๊ฐ ๋๋ค.
- ์ด๋ ๊ฒ ์ญ์ ๋ ๋ ธ๋๋ฅผ ์ฒ๋ฆฌํ๋ ๋ฐฉ์์ ํ๋ก๊ทธ๋๋ฐ ์ธ์ด๋ง๋ค ๋ค๋ฅด๋ค. Java์์๋ ์ฐ์ด์ง ์๋ ๋ ธ๋๋ฅผ ์๋์ผ๋ก ๊ฐ์งํ์ฌ Garbage Collector๊ฐ ์ฒ๋ฆฌํ์ฌ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํด์ ํ๋ค.
7. ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ฐ์ฐ์ ํจ์จ์ฑ
- ๋ฐฐ์ด๊ณผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ๋น๊ตํด ๋ณด์.
- ๊ฒ์๊ณผ ์ฝ์ , ์ญ์ ๋ ๋ฐฐ์ด๊ณผ ๋น์ทํ๊ณ ์ฝ๊ธฐ๋ ํจ์ฌ ๋๋ฆฌ๋ค.
- ๊ทธ๋ฌ๋ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์ฅ์ ์ ๋ค์๊ณผ ๊ฐ๋ค: ์ค์ ์ฝ์ ๊ณผ ์ญ์ ์ฐ์ฐ์ ํจ์จ์ฑ์ด O(1)์ ๊ทผ์ฌํ๋ค.
8. ์ฐ๊ฒฐ ๋ฆฌ์คํธ ๋ค๋ฃจ๊ธฐ
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ๊ฐ ๋น์ ๋ฐํ๋ ๊ฒฝ์ฐ๋ ํ ๋ฆฌ์คํธ๋ฅผ ๊ฒ์ฌํด์ ๋ง์ ์์๋ฅผ ์ญ์ ํ ๋๋ค.
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์ฝ์ ์ด๋ ์ญ์ ์ ๋ค๋ฅธ ๋ฐ์ดํฐ์ ์์น๋ฅผ ์ฎ๊ธฐ์ง ์์๋ ๋๋ฏ๋ก ์ ์ฒด ๋ฆฌ์คํธ๋ฅผ ํ์ผ๋ฉฐ ์ฝ์ ์ด๋ ์ญ์ ๋ฅผ ์ํํ๊ธฐ์ ๋งค์ฐ ์๋ง์ ์๋ฃ๊ตฌ์กฐ๋ค.
9. ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋ณํ ์ค ํ๋๊ฐ ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ด๋ค.
- ๋ ธ๋ ์์ ์ ๋ค์ ๋ ธ๋๋ง ๊ฐ๋ฆฌ์ผฐ๋ ๊ธฐ์กด์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋ค๋ฅด๊ฒ, ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋ ธ๋๋ ๋ ธ๋ ์์ ์ ์ด์ ๋ ธ๋๋ ๊ฐ๋ฆฌํจ๋ค.
- ์ด๋ฅผ ํตํด ๋ฆฌ์คํธ ์๊ณผ ๋ค๋ก ๋ชจ๋ ์ด๋ํ ์ ์์ด ํจ์ฌ ์ ์ฐํ๋ค.
10. ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ ๊ธฐ๋ฐ ํ
- ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ๋ฆฌ์คํธ ์๊ณผ ๋ ๋ชจ๋์ ์ ๊ทผํ ์ ์์ผ๋ฏ๋ก O(1) ์๊ฐ์ ์ ๋ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ &์ญ์ ํ ์ ์๋ค.
- ๊ทธ๋ ๊ธฐ ๋๋ฌธ์ ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ํ๋ฅผ ์ํ ์๋ฒฝํ ๋ด๋ถ ์๋ฃ๊ตฌ์กฐ๋ค.
11. ๋ง๋ฌด๋ฆฌ
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์์๋ณด๋ฉฐ ๋ ธ๋์ ๊ฐ๋ ์ ๋ฐฐ์ ๋ค.
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ๊ฐ์ฅ ๋จ์ํ ๋ ธ๋ ๊ธฐ๋ฐ ์๋ฃ๊ตฌ์กฐ๋ค.
'๐๏ธ ์ฑ & ๊ฐ์ ์ ๋ฆฌ > ๐๏ธ ๋๊ตฌ๋ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
16์ฅ ํ์ผ๋ก ์ฐ์ ์์ ์ ์งํ๊ธฐ (0) | 2022.12.28 |
---|---|
15์ฅ ์ด์ง ํ์ ํธ๋ฆฌ๋ก ์๋ ํฅ์ (0) | 2022.12.26 |
13์ฅ ์๋๋ฅผ ๋์ด๋ ์ฌ๊ท ์๊ณ ๋ฆฌ์ฆ (0) | 2022.12.08 |
12์ฅ ๋์ ํ๋ก๊ทธ๋๋ฐ (0) | 2022.12.08 |
11์ฅ ์ฌ๊ท์ ์ผ๋ก ์์ฑํ๋ ๋ฒ (0) | 2022.12.07 |