Skip to content

Latest commit

ย 

History

History
26 lines (19 loc) ยท 1.09 KB

LinkedList.md

File metadata and controls

26 lines (19 loc) ยท 1.09 KB

๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ (Linked List)

๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ (Linked List) ๊ตฌ์กฐ

  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ผ๊ณ ๋„ ํ•จ

  • ๋ฐฐ์—ด์€ ์ˆœ์ฐจ์ ์œผ๋กœ ์—ฐ๊ฒฐ๋œ ๊ณต๊ฐ„์— ๋ฐ์ดํ„ฐ๋ฅผ ๋‚˜์—ดํ•˜๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ

  • ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ๋Š” ๋–จ์–ด์ง„ ๊ณณ์— ์กด์žฌํ•˜๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ํ™”์‚ดํ‘œ๋กœ ์—ฐ๊ฒฐํ•ด์„œ ๊ด€๋ฆฌํ•˜๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ

  • ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ ๊ธฐ๋ณธ ๊ตฌ์กฐ์™€ ์šฉ์–ด

    • ๋…ธ๋“œ(Node): ๋ฐ์ดํ„ฐ ์ €์žฅ ๋‹จ์œ„ (๋ฐ์ดํ„ฐ๊ฐ’, ํฌ์ธํ„ฐ) ๋กœ ๊ตฌ์„ฑ
    • ํฌ์ธํ„ฐ(pointer): ๊ฐ ๋…ธ๋“œ ์•ˆ์—์„œ, ๋‹ค์Œ์ด๋‚˜ ์ด์ „์˜ ๋…ธ๋“œ์™€์˜ ์—ฐ๊ฒฐ ์ •๋ณด๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๊ณต๊ฐ„

๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์˜ ์žฅ๋‹จ์ 

  • ์žฅ์ 
    • ๋ฏธ๋ฆฌ ๋ฐ์ดํ„ฐ ๊ณต๊ฐ„์„ ๋ฏธ๋ฆฌ ํ• ๋‹นํ•˜์ง€ ์•Š์•„๋„ ๋จ
      • ๋ฐฐ์—ด์€ ๋ฏธ๋ฆฌ ๋ฐ์ดํ„ฐ ๊ณต๊ฐ„์„ ํ• ๋‹นํ•ด์•ผ ํ•จ
  • ๋‹จ์ 
    • ์—ฐ๊ฒฐ์„ ์œ„ํ•œ ๋ณ„๋„ ๋ฐ์ดํ„ฐ ๊ณต๊ฐ„์ด ํ•„์š”ํ•˜๋ฏ€๋กœ, ์ €์žฅ๊ณต๊ฐ„ ํšจ์œจ์ด ๋†’์ง€ ์•Š์Œ
    • ์—ฐ๊ฒฐ ์ •๋ณด๋ฅผ ์ฐพ๋Š” ์‹œ๊ฐ„์ด ํ•„์š”ํ•˜๋ฏ€๋กœ ์ ‘๊ทผ ์†๋„๊ฐ€ ๋Š๋ฆผ
    • ์ค‘๊ฐ„ ๋ฐ์ดํ„ฐ ์‚ญ์ œ์‹œ, ์•ž๋’ค ๋ฐ์ดํ„ฐ์˜ ์—ฐ๊ฒฐ์„ ์žฌ๊ตฌ์„ฑํ•ด์•ผ ํ•˜๋Š” ๋ถ€๊ฐ€์ ์ธ ์ž‘์—… ํ•„์š”

์‹œ๊ฐ„๋ณต์žก๋„

  • ๊ฒ€์ƒ‰ O(n)
  • ์‚ฝ์ž… O(1)