์ฐ๊ฒฐ ๋ฆฌ์คํธ๋?
์ฐ๊ฒฐ ๋ฆฌ์คํธ(Linked Lists)๋ ๋ฐ์ดํฐ์ ์งํฉ์ ์ ์ฅํ๊ธฐ ์ํด ์ฌ์ฉ๋๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ์ด๋ฉฐ, ์๋์ ๊ฐ์ ์์ฑ์ ๊ฐ๋๋ค.
- ์ฐ์๋๋ ํญ๋ชฉ๋ค์ด ํฌ์ธํฐ๋ก ์ฐ๊ฒฐ๋๋ค.
- ๋ง์ง๋ง ํญ๋ชฉ์ NULL์ ํฌ์ธํธ ํ๋ค.
- ํ๋ก๊ทธ๋จ์ด ์ํ๋๋ ๋์ ํฌ๊ธฐ๊ฐ ์ปค์ง๊ฑฐ๋ ์์์ง ์ ์๋ค.
- ์์คํ ๋ฉ๋ชจ๋ฆฌ๊ฐ ํ์ฉํ๋ ํ ํ์ํ ๋งํผ ๊ธธ์ด์ง ์ ์๋ค.
- ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ๋ญ๋นํ์ง ์๋๋ค.
(ํ์ง๋ง, ํฌ์ธํฐ๋ฅผ ์ํ ์ถ๊ฐ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ์๋ก ํ๋ค.)
์ฐ๊ฒฐ ๋ฆฌ์คํธ ADT
๋ค์์ ์ฐ์ฐ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ถ์ ๋ฐ์ดํฐํ,
์ฆ, ADT(Abstract Data Type)๊ฐ ๋๋๋ก ํ๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์ฃผ์ ์ฐ์ฐ๋ค
- ์ฝ์ : ํญ๋ชฉ์ ๋ฆฌ์คํธ์ ์ถ๊ฐํ๋ค.
- ์ญ์ : ์ง์ ๋ ์์น์ ํญ๋ชฉ์ ๋ฆฌ์คํธ๋ก๋ถํฐ ์ญ์ ํ๋ฉฐ ๋ฆฌํดํ๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋ณด์กฐ์ ์ฐ์ฐ๋ค
- ๋ฆฌ์คํธ ์ญ์ : ๋ฆฌ์คํธ์ ๋ชจ๋ ํญ๋ชฉ์ ์ญ์ ํ๋ค.(๋ฆฌ์คํธ๋ ์ญ์ )
- ๊ฐ์ ์ธ๊ธฐ: ๋ฆฌ์คํธ์ ํญ๋ชฉ์ ๊ฐ์๋ฅผ ๋ฆฌํดํ๋ค.
- ๋ฆฌ์คํธ์ ๋์ผ๋ก๋ถํฐ n๋ฒ์งธ ํญ๋ชฉ ์ฐพ๊ธฐ ๋ฑ
์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ๋๊ฐ?
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๊ฐ์ ๊ธฐ๋ฅ์ ํ๋ ๋ง์ ๋ค๋ฅธ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ค์ด ์๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋ํ์ฌ ๋ ผ์ํ๊ธฐ ์ ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋ฐฐ์ด์ ์ฐจ์ด์ ์ ์ดํดํ๋ ๊ฒ์ด ์ค์ํ๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋ฐฐ์ด ๋ชจ๋ ๋ฐ์ดํฐ ์งํฉ์ ์ ์ฅํ๊ธฐ ์ํด ์ฌ์ฉ๋๋ค.
์ด ๋์ด ๊ฐ์ ๋ชฉ์ ์ผ๋ก ์ฌ์ฉ๋๋ฏ๋ก ๋์ ์ฉ๋๋ฅผ ๊ตฌ๋ถํด์ผ ํ ํ์๊ฐ ์๋ค.
์ฆ, ์ด๋ค ๊ฒฝ์ฐ์ ๋ฐฐ์ด์ด ์ ํฉํ๊ณ ์ด๋ค ๊ฒฝ์ฐ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๊ฐ ์ ํฉํ๊ฐ ํ๋ ๊ฒ์ด๋ค.
๋ฐฐ์ด ๊ฐ์
๋ฐฐ์ด์ ํญ๋ชฉ์ ์ ์ฅํ๊ธฐ ์ํด ๋ฉ๋ชจ๋ฆฌ ๋ธ๋ก ํ๋๊ฐ ํ ๋น๋๋ค.
๋ฐฐ์ด์ ํญ๋ชฉ์ ํน์ ํญ๋ชฉ์ ์ธ๋ฑ์ค๋ฅผ ์ฒจ์๋ก ์ฌ์ฉํ์ฌ ์ผ์ ํ ์๊ฐ์ผ๋ก ์ ๊ทผํ ์ ์๋ค.
๋ฐฐ์ด์ ํญ๋ชฉ์ ์ ๊ทผํ๋๋ฐ ์ ์ผ์ ํ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋๊ฐ?
๋ฐฐ์ด์ ํญ๋ชฉ์ ์ ๊ทผํ๊ธฐ ์ํด์๋ ํญ๋ชฉ์ ์ฃผ์๊ฐ ๋ฐฐ์ด์ ๊ธฐ๋ณธ ์ฃผ์๋ก๋ถํฐ์ ์คํ์ ์ผ๋ก ๊ณ์ฐ๋๊ณ ํ ๋ฒ์ ๊ณฑ์ ์ฐ์ฐ์ผ๋ก ํญ๋ชฉ์ ์ฃผ์๋ฅผ ๊ตฌํ๊ธฐ ์ํด ๊ธฐ๋ณธ ์ฃผ์์ ๋ํด์ ธ์ผ ํ ๊ฐ์ด ๊ณ์ฐ๋๋ค.
์ฒ์์ ๋ฐ์ดํฐํ์ ๋ฐ๋ฅธ ํญ๋ชฉ์ ํฌ๊ธฐ๊ฐ ๊ณ์ฐ๋๊ณ , ๊ทธ๊ฒ์ด ํญ๋ชฉ์ ์ธ๋ฑ์ค์ ๊ณฑํด์ ธ์ ๊ธฐ๋ณธ ์ฃผ์์ ๋ํด์ง ๊ฐ์ด ๋๋ค.
์ด ๊ณผ์ ์์ ํ ๋ฒ์ ๊ณฑ์ ๊ณผ ํ ๋ฒ์ ๋ง์ ์ด ํ์ํ๋ค.
์ด ๋ ์ฐ ์ฐ์ด ์ผ์ ํ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋ฏ๋ก ๋ฐฐ์ด ์ ๊ทผ์ ์ผ์ ํ ์๊ฐ์ผ๋ก ์ํ๋๋ค๊ณ ํ ์ ์๋ค.
๋ฐฐ์ด์ ์ฅ์
- ๊ฐ๋จํ๊ณ ์ฌ์ฉํ๊ธฐ ์ฝ๋ค.
- ํญ๋ชฉ์์์ ์ ๊ทผ์ด ๋ ๋น ๋ฅด๋ค.(์ผ์ ํ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋ ์ ๊ทผ)
- ๋ฉ๋ชจ๋ฆฌ ์์์์ ํน์ํ ์ง์ญ์ฑ
- ์ฐ์๋ ๋ฉ๋ชจ๋ฆฌ ๋ธ๋ก์ผ๋ก ์ ์๋๋ฏ๋ก ๋ฐฐ์ด์ ํญ๋ชฉ๋ค์ ๋ฌผ๋ฆฌ์ ์ผ๋ก ๊ทผ์ฒ์ ์์นํ๋ค.
์ด๊ฒ์ ํ๋์ CPU ์บ์ฑ ๊ธฐ๋ฒ์ ๋งค์ฐ ์ ๋ฆฌํ๋ค.
๋ฐฐ์ด์ ๋จ์
- ๊ณ ์ ๋ ํฌ๊ธฐ: ์ฌ์ฉํ๊ธฐ ์ ์ ๋ฐฐ์ด์ ํฌ๊ธฐ๋ฅผ ์ง์ ํด์ค์ผ ํ๊ธฐ ๋๋ฌธ์ ๋ฐฐ์ด์ ํฌ๊ธฐ๋ ์ ์ ์ด๋ค.
- ํ ๋ธ๋ก์ ํ ๋น: ๋ฐฐ์ด ํฌ๊ธฐ๊ฐ ํด ๊ฒฝ์ฐ ์ฒ์ ๋ฐฐ์ด์ ํ ๋นํ ๋ ์ ์ฒด ๋ฐฐ์ด์ ์ํ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ป์ง ๋ชปํ ๋๋ ์๋ค.
- ๋ณต์กํ ์์น ๊ธฐ๋ฐ์ ์ฝ์
: ์ฃผ์ด์ง ์์น์ ํญ๋ชฉ์ ์ฝ์
ํ๋ ค๋ฉด ์ ํญ๋ชฉ ์ถ๊ฐํ ์๋ฆฌ ๋ง๋ จ์ ์ํด ๊ธฐ์กด์ ํญ๋ชฉ๋ค์ ์ด๋ํด์ผ ํ ์ ์๋ค.
๋ง์ฝ ์ ํญ๋ชฉ์ ์ถ๊ฐํ ์๋ฆฌ๊ฐ ๊ฐ์ฅ ์์ด๋ฉด ๋ค๋ฅธ ํญ๋ชฉ๋ค์ ์ด๋ ์ฐ์ฐ์ด ๋์ฑ ์ค๋ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
๋์ ๋ฐฐ์ด
๋์ ๋ฐฐ์ด(๋๋ ํ์ฅ ๊ฐ๋ฅ ๋ฐฐ์ด, ํฌ๊ธฐ ๋ณ๊ฒฝ ๊ฐ๋ฅ ๋ฐฐ์ด, ๋์ ํ ์ด๋ธ, ๋ฐฐ์ด ๋ฆฌ์คํธ ๋ฑ์ผ๋ก ๋ถ๋ฆฐ๋ค)์ ๋๋ค ์ ๊ทผํ๋ ํฌ๊ธฐ๊ฐ ๋ณํ๋ ๋ฆฌ์คํธ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ก ์๋ก์ด ํญ๋ชฉ๋ค์ด ์ถ๊ฐ๋๊ฑฐ๋ ์ญ์ ๋ ์ ์๋ค.
๋์ ๋ฐฐ์ด์ ๊ตฌํํ๋ ํ ๊ฐ์ง ๊ฐ๋จํ ๋ฐฉ๋ฒ์ ์ฒ์์ ์ผ์ ํ ๊ณ ์ ๋ ํฌ๊ธฐ์ ๋ฐฐ์ด๋ก ์์ํ๋ ๊ฒ์ด๋ค.
์ด ๋ฐฐ์ด์ด ๊ฐ๋ ์ฐจ๋ฉด, ์๋ ๋ฐฐ์ด์ ๋ ๋ฐฐ ํฌ๊ธฐ์ ์ ๋ฐฐ์ด์ ๋ง๋ ๋ค.
๋ง์ฐฌ๊ฐ์ง๋ก, ๋ฐฐ์ด์ ํญ๋ชฉ์ ์๊ฐ ์ ๋ฐ ์ดํ๊ฐ ๋๋ฉด ๋ฐฐ์ด ํฌ๊ธฐ๋ฅผ ๋ฐ์ผ๋ก ์ค์ธ๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์ฅ์
- ์ผ์ ํ ์๊ฐ์ผ๋ก ํ์ฅ ๊ฐ๋ฅํ๋ค.
- ํ๋์ ํญ๋ชฉ์ ์ํ ๊ณต๊ฐ์ผ๋ก ์์ํด์ ๋ณต์ฌ๋ ์ฌํ ๋น ์์ด ์ ํญ๋ชฉ์ ์ฝ๊ฒ ์ถ๊ฐํ ์ ์๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋จ์
- ๊ฐ๋ณ ํญ๋ชฉ์ ์ ๊ทผํ๋ ์ ๊ทผ ์๊ฐ์ด ๊ธธ๋ค.
- ๋ฐฐ์ด์ ๋๋ค ์ ๊ทผ์ด ๊ฐ๋ฅํ๋ฏ๋ก ๋ฐฐ์ด์ ํญ๋ชฉ์ ์ ๊ทผํ๋๋ฐ O(1)์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ๋ฆฌ์คํธ์ ํญ๋ชฉ์ ์ ๊ทผํ๋๋ฐ ์ต์ ์ ๊ฒฝ์ฐ O(n)์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค. - ์ ์ฅ ๊ณต๊ฐ์ ๋์ ํ ๋น์ด ํฐ ์ฅ์ ์ด๊ธด ํ์ง๋ง ๋ฐ์ดํฐ์ ์ ์ฅ๊ณผ ์ธ์ถ์ ๋ํด์ง๋ ๋ถ๋ด์ด ํฐ ์ฐจ์ด๋ฅผ ๋ง๋ ๋ค.
- ๋ง์ง๋ง ํญ๋ชฉ์ด ์ญ์ ๋๋ฉด, ๊ฐ์ฅ ๋์์ ํ๋ ์ ์ ํญ๋ชฉ์ ์ฐพ์ ๊ทธ ํฌ์ธํฐ๊ฐ NULL์ ๊ฐ๋ฆฌํค๊ฒ ํ๊ธฐ ์ํด ๋ฆฌ์คํธ๊ฐ ํ์๋์ด์ผ ํ๋ค.
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ์์๋ ์ถ๊ฐ์ ์ธ ์ฐธ์กฐ ํฌ์ธํฐ๋ฅผ ์ํ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ด ๋ญ๋น๋๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋ฐฐ์ด ๊ทธ๋ฆฌ๊ณ ๋์ ๋ฐฐ์ด์ ๋น๊ต
์ฐธ๊ณ
๋ค์ํ ์์ ๋ก ํ์ตํ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ for Java
'IT' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[JAVA] ์ ์ ํฉํฐ๋ฆฌ ๋ฉ์๋(static factory method) ๋? (0) | 2022.11.03 |
---|---|
[JAVA] How to install openJDK 8 on Mac (0) | 2022.11.03 |
[DATABASE] ํธ๋์ญ์ ์ ๊ฒฉ๋ฆฌ ์์ค์ด๋? (0) | 2022.11.03 |
[Github] SSH ๋ฅผ ํ์ฉํ์ฌ ์ฌ๋ฌ ๊ณ์ ๊ด๋ฆฌ ๋ฐฉ๋ฒ (0) | 2022.11.03 |
[๋ฐ์ดํฐ ๊ตฌ์กฐ] ์ฌ๊ท(recursive) ๋? (0) | 2022.11.03 |
๋๊ธ