๐Ÿšง

์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ (Linked List)

purpplee 2021. 11. 21. 17:22

์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ž€?

Singly Linked List

๋ฐฐ์—ด์ด ๋ฉ”๋ชจ๋ฆฌ์˜ ๊ณต๊ฐ„์„ ์—ฐ์†์ ์œผ๋กœ ํ• ๋‹น๋ฐ›์€ ํ˜•ํƒœ๋ผ๋ฉด, ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋Š” ์—ฐ์†์ ์ด์ง€ ์•Š๊ณ  ๋นˆ ๊ณต๊ฐ„ ์–ด๋””๋“  ํ• ๋‹น๋ฐ›๋Š” ํ˜•ํƒœ๋‹ค. ๋ฐ์ดํ„ฐ๊ฐ€ ์—ฌ๊ธฐ์ €๊ธฐ ์‚ฐ์žฌํ•ด์žˆ์œผ๋‹ˆ ๊ฐ ๋ฐ์ดํ„ฐ๋Š” ์ž์‹ ์˜ ๋‹ค์Œ ๋ฐ์ดํ„ฐ๊ฐ€ ์–ด๋””์— ์žˆ๋Š”์ง€ ์•Œ์•„์•ผ ํ•œ๋‹ค. ๊ทธ๋ž˜์„œ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ๋ฐ์ดํ„ฐ๋Š” ๊ฐ’ ๋ฟ๋งŒ ์•„๋‹ˆ๋ผ ๋‹ค์Œ ๋ฐ์ดํ„ฐ์˜ ์ฃผ์†Œ๊ฐ’๋„ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.

 

์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ํ•œ ๋ฐ์ดํ„ฐ(๋ฐ์ดํ„ฐ์™€ ์ฃผ์†Œ๊ฐ’)์„ ๋…ธ๋“œ(Node) ๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. ๋…ธ๋“œ๋“ค์€ ๋‹ค์Œ ๋…ธ๋“œ์˜ ์ฃผ์†Œ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์Œ์œผ๋กœ์จ ์—ฐ๊ฒฐ๋œ๋‹ค. ๋งจ ๋์˜ ๋…ธ๋“œ๋Š” ์ž์‹ ์ด ๋์ด๋ผ๋Š” ๊ฑธ ์•Œ๋ฆฌ๊ธฐ ์œ„ํ•ด Null ๊ฐ’์„ ๊ฐ€์ง„๋‹ค.

Doubly Linked List

๊ธฐ๋ณธ์ ์ธ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๋‹จ๋ฐฉํ–ฅ์œผ๋กœ๋งŒ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์–ด ํ˜„์žฌ ๋…ธ๋“œ์˜ ์ด์ „ ๋…ธ๋“œ๋ฅผ ์•Œ ์ˆ˜ ์—†๋‹ค. ์ด๋ฅผ ๊ฐœ์„ ํ•œ ๊ฒƒ์ด ์ด์ค‘ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ (Doubly Linked List) ์ด๋‹ค. ํ˜„์žฌ ๋…ธ๋“œ๊ฐ€ ์ด์ „/๋‹ค์Œ ๋…ธ๋“œ์˜ ์ฃผ์†Œ๊ฐ’์„ ๋ชจ๋‘ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํ˜•ํƒœ๋‹ค.

 

๋˜ ๋งจ ๋์— Null ์„ ๋‘์ง€ ์•Š๊ณ  ์ฒซ๋ฒˆ์งธ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌ์ผœ ๋งˆ์น˜ ์›ํ˜•์ฒ˜๋Ÿผ ๋งŒ๋“  ์›ํ˜• ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (Circular Linked List) ๋„ ์žˆ๋‹ค.

 

์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์—ฐ์‚ฐ

READ

๋ฐฐ์—ด์€ ์—ฐ์†์ ์œผ๋กœ ๊ณต๊ฐ„์„ ์ฐจ์ง€ํ•˜๊ณ  ์žˆ์–ด์„œ ์ธ๋ฑ์Šค๋ฅผ ์ด์šฉํ•ด ์›ํ•˜๋Š” ์œ„์น˜๋ฅผ ๋ฐ”๋กœ ์ฝ์„ ์ˆ˜ ์žˆ์—ˆ๋‹ค. ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋Š” ์ฒซ ๋…ธ๋“œ(Head)์˜ ์ •๋ณด๋งŒ ์•Œ ์ˆ˜ ์žˆ๊ธฐ์— Head ์˜ ์—ฐ๊ฒฐ๊ณ ๋ฆฌ๋ฅผ ํƒ€๊ณ  ํƒ€๊ณ  ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ์ฐพ์•„๊ฐ€๋Š” ์‹์œผ๋กœ ์ฝ๋Š”๋‹ค. ์ตœ์•…์˜ ๊ฒฝ์šฐ ์ „๋ถ€ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ์ด๋ฏ€๋กœ O(n) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

SEARCH

READ์™€ ๊ฐ™๋‹ค. Head ์˜ ์—ฐ๊ฒฐ๊ณ ๋ฆฌ๋ฅผ ํƒ€๊ณ ํƒ€๊ณ  ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ์ฐพ์•„ ๊ฐ’์„ ๋น„๊ตํ•ด ๊ฒ€์ƒ‰ํ•˜๋Š” ๋ฐฉ์‹์ด๋ผ ๊ฒ€์ƒ‰ ์†๋„๊ฐ€ ๋А๋ฆฌ๋‹ค. Best๋Š” Head๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๊ฒฝ์šฐ๊ณ , ์ตœ์•…์˜ ๊ฒฝ์šฐ๋Š” ๋งจ ๋์— ์žˆ๋Š” ๊ฒƒ์ด๋‹ค. ๋”ฐ๋ผ์„œ O(n) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

 

INSERT

์ถ”๊ฐ€ํ•  ์œ„์น˜์˜ ์ด์ „ ๋…ธ๋“œ๋Š” ์ถ”๊ฐ€ํ•˜๋Š” ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ฒŒ ํ•˜๊ณ , ์ถ”๊ฐ€ํ•˜๋Š” ๋…ธ๋“œ๋Š” ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ฒŒ ํ•˜๋ฉด ๋œ๋‹ค. ์ด ๊ฒฝ์šฐ์—๋„ ์ถ”๊ฐ€ํ•  ์œ„์น˜๋ฅผ ์ฐพ์•„๊ฐ€์•ผ ํ•˜๋ฏ€๋กœ O(n) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

 

DELETE

์‚ญ์ œํ•˜๋Š” ๋…ธ๋“œ์˜ ์ด์ „ ๋…ธ๋“œ๊ฐ€ ์‚ญ์ œํ•˜๋Š” ๋…ธ๋“œ์˜ ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ฒŒ ํ•˜๋ฉด ๋œ๋‹ค. ์‚ญ์ œํ•œ ๋…ธ๋“œ๋Š” ์—ฐ๊ฒฐ ๊ณ ๋ฆฌ๋ฅผ ์žƒ์—ˆ์œผ๋‹ˆ ์•„๋ฌด๋Ÿฐ ์ฒ˜๋ฆฌ๋ฅผ ํ•˜์ง€ ์•Š์•„๋„ ๋˜์ง€๋งŒ, ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ฐจ์ง€ํ•˜๊ณ  ์žˆ์œผ๋‹ˆ ์ž๋™์œผ๋กœ ๋ฉ”๋ชจ๋ฆฌ ์ •๋ฆฌ๋ฅผ ํ•˜์ง€ ์•Š๋Š” ์–ธ์–ด์—์„œ๋Š” ํ• ๋‹น์„ ํ•ด์ œํ•ด์ค˜์•ผ ํ•œ๋‹ค. ์ด ๊ฒฝ์šฐ์—๋„ ์œ„์น˜๋ฅผ ์ฐพ์•„๊ฐ€์•ผ ํ•˜๋ฏ€๋กœ O(n) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

์ •๋ฆฌ

์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋Š” ๋ฐฐ์—ด๊ณผ ๋‹ฌ๋ฆฌ ๋ฏธ๋ฆฌ ๊ณต๊ฐ„์„ ํ• ๋‹น๋ฐ›์ง€ ์•Š๊ณ  ๋ถˆ์—ฐ์†์ ์ธ ๊ณต๊ฐ„์— ์ €์žฅํ•œ๋‹ค. ๋นˆ ๊ณต๊ฐ„์„ ๊ด€๋ฆฌํ•˜์ง€ ์•Š์•„๋„ ๋˜๊ณ , ๊ธธ์ด๋ฅผ ์‹ ๊ฒฝ์“ธ ํ•„์š”๊ฐ€ ์—†์œผ๋‹ˆ ํ™•์žฅํ•˜๊ธฐ๋„ ์šฉ์ดํ•˜๋‹ค. ์ถ”๊ฐ€/์‚ญ์ œ๋Š” ๊ฐ™์€ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€์ง€๋งŒ, ๋ฐ์ดํ„ฐ๋ฅผ ์ „๋ถ€ ํ•˜๋‚˜ํ•˜๋‚˜ ์ด๋™์‹œํ‚ค๋Š” ์ž‘์—…์„ ํ•˜์ง€ ์•Š์•„๋„ ๋˜๋‹ˆ ๋ฐฐ์—ด๋ณด๋‹ค ์‰ฝ๊ฒŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

 

๊ทธ๋Ÿฌ๋‚˜ ์ฝ๊ณ  ๊ฒ€์ƒ‰ํ•˜๋Š” ๋ฐ๋Š” Head ๋ถ€ํ„ฐ ํ•˜๋‚˜ํ•˜๋‚˜ ๊ฑฐ์Šฌ๋Ÿฌ ์˜ฌ๋ผ๊ฐ€์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์†๋„๊ฐ€ ๋А๋ฆฌ๋‹ค. ๊ฒŒ๋‹ค๊ฐ€ ์ด์ „/๋‹ค์Œ ๋…ธ๋“œ์˜ ์ฃผ์†Œ๊ฐ’๊นŒ์ง€ ๊ฐ€์ง€๊ณ  ์žˆ์–ด์•ผ ํ•˜๋‹ˆ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ๋ฐฐ์—ด๋ณด๋‹ค ๋” ์ฐจ์ง€ํ•œ๋‹ค. ๋ฐฐ์—ด๋ณด๋‹ค ํ™•์žฅ์ด ์šฉ์ดํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํ™•์žฅ์˜ ์šฉ์ด์„ฑ์ด ์ค‘์š”ํ•œ ๊ฒฝ์šฐ์— ์‚ฌ์šฉํ•˜๋ฉด ์ข‹๋‹ค. ํŠนํžˆ ์ดํ›„ ์–ธ๊ธ‰๋˜๋Š” ๐Ÿ‘‰ ํŠธ๋ฆฌ๋ผ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ํ‘œํ˜„ํ•˜๊ธฐ ๊ฐ€์žฅ ์ ๋‹นํ•ด ์ฃผ๋กœ ์‚ฌ์šฉ๋œ๋‹ค.

๋ฐ˜์‘ํ˜•