๐Ÿš‚ ๋ฐฐ์—ด(Array) ยท ๋™์  ๋ฐฐ์—ด(Dynamic Array) ยท ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List) ๋น„๊ต ์ •๋ฆฌ

๊ฐ€์žฅ ๊ธฐ๋ณธ์ ์ด๋ฉด์„œ๋„ ์ž์ฃผ ๋“ฑ์žฅํ•˜๋Š” ์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ 3๊ฐ€์ง€ ๋ฐฐ์—ด, ๋ฆฌ์ŠคํŠธ, ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด์ž.
 

1. ๋ฐฐ์—ด (Array) 

๋ฐฐ์—ด์ด๋ž€ ๊ฐ™์€ ํƒ€์ž…์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์—ฐ์†๋œ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์— ์ €์žฅํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. 

๋ฐฐ์—ด ์ด๋ฏธ์ง€

๊ฐ ์š”์†Œ๋Š” ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•ด ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ ์ธ๋ฑ์Šค๋Š” 0๋ถ€ํ„ฐ ์‹œ์ž‘ํ•œ๋‹ค.
 

ํŠน์ง• 

  • ๊ณ ์ •๋œ ํฌ๊ธฐ

    ๋ฐฐ์—ด์€ ์ƒ์„ฑ ์‹œ ํฌ๊ธฐ๋ฅผ ์ง€์ •ํ•ด์•ผ ํ•˜๋ฉฐ ํ•œ ๋ฒˆ ์ •ํ•ด์ง„ ํฌ๊ธฐ๋Š” ๋ณ€๊ฒฝํ•  ์ˆ˜ ์—†๋‹ค.

  • ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•œ ๋น ๋ฅธ ์ ‘๊ทผ

    ๋ฐฐ์—ด์€ ์ธ๋ฑ์Šค๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ํŠน์ • ์œ„์น˜์˜ ๊ฐ’์„ O(1) ์‹œ๊ฐ„์— ๋ฐ”๋กœ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋‹ค.

  • ์—ฐ์†๋œ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ์‚ฌ์šฉ

    ๋ฐฐ์—ด์€ ๋ฉ”๋ชจ๋ฆฌ์ƒ์— ๋ฐ์ดํ„ฐ๊ฐ€ ์—ฐ์†์ ์œผ๋กœ ๋ฐฐ์น˜๋˜์–ด ์žˆ์–ด ์บ์‹œ ์ ์ค‘๋ฅ ์ด ๋†’๊ณ  ํผํฌ๋จผ์Šค๊ฐ€ ์ข‹๋‹ค.

  • ์‚ฝ์ž…/์‚ญ์ œ์— ๋น„ํšจ์œจ์ 

    ์ค‘๊ฐ„์— ๋ฐ์ดํ„ฐ๋ฅผ ์‚ฝ์ž…ํ•˜๊ฑฐ๋‚˜ ์‚ญ์ œํ•˜๋ฉด ๋’ค์˜ ์š”์†Œ๋“ค์„ ๋ชจ๋‘ ์ด๋™์‹œ์ผœ์•ผ ํ•˜๋ฏ€๋กœ ์„ฑ๋Šฅ์ด ๋–จ์–ด์งˆ ์ˆ˜ ์žˆ๋‹ค.
     

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

    ๋ฐฐ์—ด ์‹œ๊ฐ„ ๋ณต์žก๋„ ์ด๋ฏธ์ง€

     



๋™์  ๋ฐฐ์—ด(Dynamic Array)๊ณผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List)๋ฅผ ์•Œ์•„๋ณด๊ธฐ ์ „์— ๋ฆฌ์ŠคํŠธ๊ฐ€ ๋ฌด์—‡์ธ์ง€ ์•Œ์•„๋ณด์ž.
 

๋ฆฌ์ŠคํŠธ(List)๋ž€?

๋ฆฌ์ŠคํŠธ๋Š” ์ˆœ์„œ๊ฐ€ ์žˆ๋Š” ์›์†Œ๋“ค์˜ ๋ชจ์Œ์ด๋ฉฐ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์—ฐ์‚ฐ์„ ์ง€์›ํ•˜๋Š” ์ถ”์ƒ ์ž๋ฃŒํ˜•(ADT)์ด๋‹ค.
 

  • get(i) - i ๋ฒˆ์งธ ์š”์†Œ ์กฐํšŒ
  • insert(i, x) - i ๋ฒˆ์งธ ์œ„์น˜์— x ์‚ฝ์ž…
  • delete(i) - i ๋ฒˆ์งธ ์š”์†Œ ์‚ญ์ œ
  • append(x) - ๋งจ ๋’ค์— x ์ถ”๊ฐ€
  • length() - ์ „์ฒด ๊ธธ์ด ๋ฐ˜ํ™˜


์ฆ‰ ๋™์  ๋ฐฐ์—ด๊ณผ ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ๋Š” ๋ชจ๋‘ ์ด ๋ฆฌ์ŠคํŠธ๋ž€ ์ถ”์ƒ ๊ฐœ๋…์„ ์„œ๋กœ ๋‹ค๋ฅธ ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ•œ ๊ฒƒ์ด๋‹ค.
 

2. ๋™์  ๋ฐฐ์—ด (Dynamic Array)

๋™์  ๋ฐฐ์—ด์€ ํฌ๊ธฐ๊ฐ€ ๊ณ ์ •๋œ ๋ฐฐ์—ด์˜ ํ•œ๊ณ„๋ฅผ ๊ทน๋ณตํ•˜๊ธฐ ์œ„ํ•ด ๋งŒ๋“ค์–ด์ง„ ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ์ฒ˜์Œ์—๋Š” ์ผ์ •ํ•œ ํฌ๊ธฐ๋กœ ์‹œ์ž‘ํ•˜์ง€๋งŒ ์ €์žฅ ๊ณต๊ฐ„์ด ๋ถ€์กฑํ•ด์ง€๋ฉด ๋” ํฐ ๋ฐฐ์—ด์„ ์ƒˆ๋กœ ๋งŒ๋“ค๊ณ  ๊ธฐ์กด ๋ฐ์ดํ„ฐ๋ฅผ ๋ณต์‚ฌํ•˜์—ฌ ์ž๋™์œผ๋กœ ํฌ๊ธฐ๋ฅผ ํ™•์žฅํ•œ๋‹ค.

๋Œ€ํ‘œ์ ์ธ ๋™์  ๋ฐฐ์—ด๋กœ๋Š” Java์˜ ArrayList, Python์˜ list, JavaScript์˜ Array๊ฐ€ ์žˆ๋‹ค.

ํŠน์ง•

  • ๋ฐฐ์—ด๊ณผ ์œ ์‚ฌ

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

  • ๋™์ ์ธ ํฌ๊ธฐ ์กฐ์ ˆ

    ๋ฐฐ์—ด์ด ๊ฐ€๋“ ์ฐจ๋ฉด ๋” ํฐ ๋ฐฐ์—ด์„ ์ƒˆ๋กœ ๋งŒ๋“ค๊ณ  ๋ณต์‚ฌํ•˜์—ฌ์„œ ์ž๋™์œผ๋กœ ํฌ๊ธฐ๋ฅผ ํ™•์žฅํ•œ๋‹ค.
     

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

    ๋™์  ๋ฐฐ์—ด ์‹œ๊ฐ„ ๋ณต์žก๋„ ์ด๋ฏธ์ง€

     

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

์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•  ๋•Œ ๋ฐฐ์—ด์ฒ˜๋Ÿผ ์—ฐ์†๋œ ๊ณต๊ฐ„์— ์ €์žฅํ•˜์ง€ ์•Š๊ณ  ๊ฐ ์š”์†Œ(๋…ธ๋“œ)๊ฐ€ ๋‹ค์Œ ์š”์†Œ๋ฅผ ํฌ์ธํ„ฐ๋ฅผ ํ†ตํ•ด ๊ฐ€๋ฆฌํ‚ค๋Š” ๋ฐฉ์‹์œผ๋กœ ์—ฐ๊ฒฐ๋œ ์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค.

๊ฐ ๋…ธ๋“œ๋Š” ๊ฐ’๊ณผ ๋‹ค์Œ ๋…ธ๋“œ์˜ ์ฃผ์†Œ๋ฅผ ํฌํ•จํ•˜๋ฉฐ ๊ตฌ์กฐ์— ๋”ฐ๋ผ ๋‹จ์ผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Singly Linked List), ์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Doubly Linked List), ์›ํ˜• ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Circular Linked List)๋กœ ๋‚˜๋‰œ๋‹ค.
 

ํŠน์ง•

  • ๋น„์—ฐ์† ๋ฉ”๋ชจ๋ฆฌ

    ๋ฐฐ์—ด์ฒ˜๋Ÿผ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์ด ์—ฐ์†๋  ํ•„์š” ์—†์ด ๋…ธ๋“œ๋ผ๋ฆฌ ํฌ์ธํ„ฐ๋กœ ์—ฐ๊ฒฐ๋œ๋‹ค.

  • ์‚ฝ์ž…/์‚ญ์ œ์— ํšจ์œจ์ 

    ์ค‘๊ฐ„ ์‚ฝ์ž…/์‚ญ์ œ ์‹œ ํฌ์ธํ„ฐ๋งŒ ์กฐ์ •ํ•˜๋ฉด ๋˜๋ฏ€๋กœ ์œ„์น˜๋ฅผ ์•Œ๊ณ  ์žˆ์„ ๊ฒฝ์šฐ ๋น„์šฉ์ด ๋‚ฎ๋‹ค.

  • ์ ‘๊ทผ์— ๋น„ํšจ์œจ์ 

    ์ž„์˜์˜ ์œ„์น˜์— ์ ‘๊ทผํ•˜๋ ค๋ฉด ์ฒ˜์Œ๋ถ€ํ„ฐ ์ˆœ์ฐจ ํƒ์ƒ‰ํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋น„ํšจ์œจ์ ์ด๋‹ค.

  • ๋ฉ”๋ชจ๋ฆฌ ์˜ค๋ฒ„ํ—ค๋“œ

    ๊ฐ ๋…ธ๋“œ๋งˆ๋‹ค ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋Š” ๊ณต๊ฐ„ ์™ธ์— ํฌ์ธํ„ฐ ๊ณต๊ฐ„์ด ์ถ”๊ฐ€๋กœ ํ•„์š”ํ•˜๋‹ค.
     

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

์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์‹œ๊ฐ„ ๋ณต์žก๋„ ์ด๋ฏธ์ง€
์žฅ์‹์šฉ ๋กœ๊ณ 
๐Ÿš‚ ๋ฐฐ์—ด(Array) ยท ๋™์  ๋ฐฐ์—ด(Dynamic Array) ยท ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List) ๋น„๊ต ์ •๋ฆฌ | BlueCool