[์ž๋ฃŒ๊ตฌ์กฐ] Arrays vs LinkedList

Array ๋ฐฐ์—ด - ๋…ผ๋ฆฌ์  ์ €์žฅ์ˆœ์„œ์™€ ๋ฌผ๋ฆฌ์  ์ €์žฅ์ˆœ์„œ๊ฐ€ ์ผ์น˜ - ํŠน์ • ์ž๋ฃŒํ˜•๋“ค์ด ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„ ์ƒ์—์„œ ์—ฐ์†์ ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Œ - Immutable ( ๋ณ€๊ฒฝ ๋ถˆ๊ฐ€๋Šฅ ) : ๊ฐ์ฒด๊ฐ€ ์ƒ์„ฑ๋œ ์ดํ›„ ๊ทธ ์ƒํƒœ๋ฅผ ๋ณ€๊ฒฝํ•  ์ˆ˜ ์—†๋Š” ๋””์ž์ธ ํŒจํ„ด - ์ธ๋ฑ์Šค๋กœ ์›์†Œ์— ์ ‘๊ทผํ•จ : Random Access -> O(1)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ์›์†Œ์— ์ ‘๊ทผ์ด ๊ฐ€๋Šฅํ•จ : ์‚ญ์ œ ๋˜๋Š” ์‚ฝ์ž… ๊ณผ์ •์—์„œ๋Š” ํ•ด๋‹น ์›์†Œ์— ์ ‘๊ทผํ•˜๊ณ  Shift๋ฅผ ํ•ด์„œ O(n) : ๋ฐ์ดํ„ฐ๊ฐ€ ๋งŽ์€ ๊ฒฝ์šฐ ๋น„ํšจ์œจ์  - ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„ ํ™œ์šฉ์ด ์ œ์•ฝ์  LinkedList - ๋…ผ๋ฆฌ์  ์ €์žฅ์ˆœ์„œ์™€ ๋ฌผ๋ฆฌ์  ์ €์žฅ ์ˆœ์„œ๊ฐ€ ๋‹ค๋ฅด๋‹ค : ๋ฐ์ดํ„ฐ ๊ฒ€์ƒ‰ ์‹œ ์ฒ˜์Œ ๋…ธ๋“œ๋ถ€ํ„ฐ ์ˆœํ™˜ O(n) - ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์ƒ์— ๋…ธ๋“œ๋“ค์ด ํฉ์–ด์ ธ ์กด์žฌํ•จ, ๊ฐ๊ฐ์˜ ๋…ธ๋“œ๊ฐ€ ์ž์‹ ์˜ ๋‹ค์Œ ๋…ธ๋“œ์˜ ์œ„์น˜๋ฅผ ์•Œ๊ณ  ์žˆ์Œ : ์‚ฌ์šฉ์ž๋Š” ์ œ์ผ ์ฒซ ..

CS/Data Structure 2022. 3. 28. 22:08