๐Ÿ‘‰Linked List

ArrayList์™€ ๋‹ค๋ฅด๊ฒŒ element๊ฐ„์˜ ์—ฐ๊ฒฐ์„ ์ด์šฉํ•ด์„œ List๋ฅผ ๊ตฌํ˜„ํ•œ ๊ฒƒ

linked list์—์„œ ๊ฐ€์žฅ ์ค‘์š”ํ•œ ๊ฒƒ์€ ์—ฐ๊ฒฐ์ด ๋ฌด์—‡์ธ๊ฐ€๋ฅผ ํŒŒ์•…ํ•˜๋Š” ๊ฒƒ!!

ArryaList์—์„œ๋Š” element๋ผ๋Š” ์ด๋ฆ„์„ ์‚ฌ์šฉํ–ˆ์ง€๋งŒ, Linked List์™€ ๊ฐ™์ด ์—ฐ๊ฒฐ๋œ element๋“ค์€ Node, ๋งˆ๋”” ํ˜น์€ Vertex, ์ •์ ์ด๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค.

Node๋Š” ์‹ค์ œ ์ •๋ณด๋ฅผ ๋‹ด๊ณ  ์žˆ๋Š” ํ•˜๋‚˜์˜ ๋‹จ์œ„์ด๋ฉฐ, Link๋Š” ๋…ธ๋“œ๊ฐ„์˜ ์œ„์น˜์ •๋ณด๋ฅผ ์ €์žฅํ•˜์—ฌ ์„œ๋กœ ์—ฐ๊ฒฐํ•ด์ค„ ์ˆ˜ ์žˆ๋Š” ์—ฐ๊ฒฐ๊ณ ๋ฆฌ

Linked List๊ฐ€ ์‹คํ–‰๋  ๋•Œ ์ด๋ฏธ์ง€

list.PNG
list2.PNG

์ด๋ฏธ์ง€ ์ถœ์ฒ˜ : wikipedia

Arraylist vs Linkedlist

list3.png

Arraylist์™€ Linkedlist ๋น„๊ต ์ด๋ฏธ์ง€
< ์ด๋ฏธ์ง€ ์ถœ์ฒ˜ : https://opentutorials.org/module/1335/8821 >

Node

๋…ธ๋“œ๋Š” ์ž๋ฃŒ์™€ ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ์ฐธ์กฐ๊ฐ’์œผ๋กœ ๊ตฌ์„ฑ

Linked List ๊ตฌํ˜„

์ดˆ๊ธฐํ™”(init) / ์‚ฝ์ž…(insert) / ์‚ญ์ œ(Remove) ์ž‘์—… ํ•„์š”

ex) ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ์—์„œ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๋Š” Linked List๋Š” array๊ฐ€ ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ array ๋ฉ”์„œ๋“œ๋ฅผ ์ด์šฉํ•ด์„œ array.push()๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ฐ์ดํ„ฐ๋ฅผ ์ถ”๊ฐ€ํ•  ์ˆ˜ ์žˆ๊ณ , array.splice()๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ฐ์ดํ„ฐ๋ฅผ ์ œ๊ฑฐํ•  ์ˆ˜ ์žˆ๋‹ค.

Linked List ์ดˆ๊ธฐํ™”

๋…ธ๋“œ๋ฅผ ์ ‘๊ทผํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋งจ ์ฒ˜์Œ ๋…ธ๋“œ์˜ ์ฃผ์†Œ๋ฅผ ๊ฐ€๋ฆฌํ‚ฌ ๋…ธ๋“œ๊ฐ€ ํ•„์š”

์ฒซ๋ฒˆ์งธ ๋…ธ๋“œ๋ฅผ Head ํ‘œํ˜„ / ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ๋ฅผ Tail ํ‘œํ˜„

  • ์ดˆ๊ธฐํ™” ๊ณผ์ •์—์„œ ๋‹ค์Œ ์ฃผ์†Œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ๋ฅผ null๋กœ ์„ค์ •

Linked List ๋ฉ”์„œ๋“œ

  • find() : head๋…ธ๋“œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ํ•ด๋‹น item์„ ๊ฒ€์ƒ‰ํ•˜๋ฉด์„œ ์ฐพ๊ณ  ์ฐพ์œผ๋ฉด ํ•ด๋‹น ๋…ธ๋“œ ๋ฐ˜ํ™˜

  • insert() : find()๋ฉ”์„œ๋“œ๋กœ ์ฐพ์€ ๋…ธ๋“œ ๋’ค์— ์ƒˆ๋กœ์šด ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐ

    insert.PNG

    < ์ด๋ฏธ์ง€ ์ถœ์ฒ˜ : https://untitledtblog.tistory.com/82?category=689662 >
    But ์ค‘๋ณต๊ฐ’์„ ํ—ˆ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ค‘๋ณต๋œ ๊ฐ’์„ ๋„ฃ๋‹ค๋ณด๋ฉด ์ฒ˜์Œ ์ฐพ์•„๋‚ธ ๋…ธ๋“œ ๋’ค์— ์—ฐ๊ฒฐํ•˜๋Š” ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋‹ค.
  • first() : head๋…ธ๋“œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ํ•ด๋‹น item์„ ๊ฒ€์ƒ‰ํ•˜๋ฉด์„œ ์ฐพ๊ณ  ์ฐพ์œผ๋ฉด ํ•ด๋‹น ๋…ธ๋“œ ๋ฐ˜ํ™˜

  • append() : ๋งจ ๋’ค์— ๋…ธ๋“œ๋ฅผ ์ถ”๊ฐ€

    append.PNG

    < ์ด๋ฏธ์ง€ ์ถœ์ฒ˜ : https://untitledtblog.tistory.com/82?category=689662 >
  • next() : ๋‹ค์Œ์— ์—ฐ๊ฒฐํ•  ๋…ธ๋“œ ๊ฒ€์ƒ‰

  • delete() : ํ˜„์žฌ ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ์‚ญ์ œ

    delete.PNG

    < ์ด๋ฏธ์ง€ ์ถœ์ฒ˜ : https://untitledtblog.tistory.com/82?category=689662 >
  • remove() : ์‚ญ์ œํ•  ๋…ธ๋“œ ๋ฐ”๋กœ ์ง์ „์— ์žˆ๋Š” ๋…ธ๋“œ๋ฅผ ์ฐพ์•„ ์—ฐ๊ฒฐ์„ ๋Š์–ด๋ฒ„๋ฆฌ๋Š” ๊ฒƒ์œผ๋กœ ์‚ญ์ œ์ฒ˜๋ฆฌ

์žฅ์ : ๋…ธ๋“œ์˜ ํฌ์ธํ„ฐ๋ฅผ ํ†ตํ•ด์„œ ๋ชจ๋“  ๋ฐ์ดํ„ฐ์˜ ์ฐธ์กฐ๊ฐ€ ๊ฐ€๋Šฅ, ๋งํฌ ์ด๋™์„ ํ†ตํ•œ ์œ ์—ฐํ•œ ๋ณ€๊ฒฝ์ด ๊ฐ€๋Šฅ

๋‹จ์  : ๋ฐ์ดํ„ฐ์˜ ์œ„์น˜๋ฅผ ์•Œ์•„๋„ ๋ฐ”๋กœ ์ ‘๊ทผ ๋ถˆ๊ฐ€, ์ •๋ ฌ์†๋„๊ฐ€ ๋Š๋ฆฌ๋‹ค.