[Java] Collection | ์ž๋ฃŒ๊ตฌ์กฐ(data structure)

Jeiniยท2022๋…„ 12์›” 4์ผ
0

โ˜•๏ธย  Java

๋ชฉ๋ก ๋ณด๊ธฐ
36/72
post-thumbnail

๐Ÿ“Œ Collection Framework๋ž€?

โœ… ์ž๋ฃŒ๋ฅผ ์ €์žฅํ•˜๊ณ  ๊ด€๋ฆฌํ•˜๋Š” ํ‘œ์ค€ํ™”๋œ ํด๋ž˜์Šค์™€ ์ธํ„ฐํŽ˜์ด์Šค์˜ ์ง‘ํ•ฉ

  • "๋ฐ์ดํ„ฐ๋ฅผ ๋‹ด์„ ๊ทธ๋ฆ‡ + ๋‹ค๋ฃจ๋Š” ๊ธฐ๋Šฅ"์„ ์ฒด๊ณ„์ ์œผ๋กœ ์ œ๊ณตํ•ด์คŒ.
  • ๋ฐฐ์—ด(Array)์€ ํฌ๊ธฐ๊ฐ€ ๊ณ ์ •์ด๊ณ , ๋ณต์žกํ•œ ๊ธฐ๋Šฅ์ด ๋ถ€์กฑํ•œ๋ฐ,
    ์ปฌ๋ ‰์…˜ ํ”„๋ ˆ์ž„์›Œํฌ๋Š” ๋™์  ํฌ๊ธฐ, ๊ฒ€์ƒ‰, ์ •๋ ฌ, ์ถ”๊ฐ€/์‚ญ์ œ ๊ฐ™์€ ๊ธฐ๋Šฅ์„ ์ œ๊ณตํ•จ.
  • java.util ํŒจํ‚ค์ง€์— ํฌํ•จ
  • Collection: ์—ฌ๋Ÿฌ ๊ฐ์ฒด(๋ฐ์ดํ„ฐ)๋ฅผ ๋ชจ์•„ ๋†“์€ ๊ฒƒ์„ ์˜๋ฏธ
  • framework: ํ‘œ์ค€ํ™”, ์ •ํ˜•ํ™”๋œ ์ฒด๊ณ„์ ์ธ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋ฐฉ์‹

๐Ÿ“Œ ์ž๋ฃŒ๊ตฌ์กฐ(data structure)๋ž€?

โœ… ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๊ณ , ํšจ์œจ์ ์œผ๋กœ ๊บผ๋‚ด๊ณ , ์กฐ์ž‘ํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•

  • "๋ฐ์ดํ„ฐ๋ฅผ ์–ด๋–ค ๋ชจ์–‘์œผ๋กœ ์Œ“์•„๋‘˜๊นŒ?" ํ•˜๋Š” ๋ฌธ์ œ์ 
  • CPU๋Š” ์—ฐ์‚ฐ์„ ํ•˜์ง€๋งŒ, RAM(๋ฉ”๋ชจ๋ฆฌ) ์€ ๊ทธ ์—ฐ์‚ฐ์— ํ•„์š”ํ•œ ๋ฐ์ดํ„ฐ๋ฅผ ์–ด๋–ค ๊ตฌ์กฐ๋กœ ๋‹ด์•„๋‘˜์ง€๊ฐ€ ์ค‘์š”ํ•˜๋‹ค.

๐Ÿ“Œ ๋‘ ๊ฐ€์ง€ ๊ทผ๋ณธ ๊ตฌ์กฐ (Foundation Structures)


์ž๋ฃŒ๊ตฌ์กฐ์˜ ๋ฟŒ๋ฆฌ๋ฅผ ๋ณด๋ฉด ํฌ๊ฒŒ ๋‘ ๊ฐ€์ง€๋กœ ๋‚˜๋ˆ ์ง„๋‹ค ๐Ÿ‘‡

1. ๋ฐฐ์—ด(Array) ๊ธฐ๋ฐ˜ ๊ตฌ์กฐ

  • ๋ฐ์ดํ„ฐ๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์ƒ์—์„œ ์—ฐ์†์ ์œผ๋กœ ์ €์žฅ๋จ.
  • ์ธ๋ฑ์Šค๋กœ ๋ฐ”๋กœ ์ ‘๊ทผ ๊ฐ€๋Šฅ (๋žœ๋ค ์ ‘๊ทผ O(1))
  • ํ•˜์ง€๋งŒ ์ค‘๊ฐ„ ์‚ฝ์ž…/์‚ญ์ œ๊ฐ€ ๋น„ํšจ์œจ์  (O(n))

๐Ÿ“ ์˜ˆ:

  • Array, Matrix(ํ–‰๋ ฌ), HashTable(ํ•ด์‹œ ํ…Œ์ด๋ธ”์˜ ๋‚ด๋ถ€ ๋ฒ„ํ‚ท)
  • CPU ์บ์‹œ ์นœํ™”์  โ†’ ์—ฐ์† ๋ฉ”๋ชจ๋ฆฌ ์ ‘๊ทผ์ด๋ผ ๋น ๋ฆ„

๐Ÿ”น Array

[10][20][30][40][50]
 โ†‘   โ†‘   โ†‘   โ†‘   โ†‘
์ฃผ์†Œ+0 ์ฃผ์†Œ+1 ...
  • ์—ฐ์†๋œ ๋ฉ”๋ชจ๋ฆฌ ๋ธ”๋ก
  • ์ธ๋ฑ์Šค ๊ณ„์‚ฐ = ์‹œ์ž‘์ฃผ์†Œ + (index ร— ์ž๋ฃŒํ˜• ํฌ๊ธฐ)

2. ๋…ธ๋“œ(Node, Pointer) ๊ธฐ๋ฐ˜ ๊ตฌ์กฐ

  • ๋ฐ์ดํ„ฐ๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์ƒ์—์„œ ํฉ์–ด์ ธ ์žˆ๊ณ , ํฌ์ธํ„ฐ(์ฐธ์กฐ)๋ฅผ ํ†ตํ•ด ์—ฐ๊ฒฐ๋จ.
  • ์‚ฝ์ž…/์‚ญ์ œ๊ฐ€ ๋น ๋ฆ„ (ํฌ์ธํ„ฐ๋งŒ ๋ฐ”๊ฟ”์ฃผ๋ฉด ๋จ) โžก๏ธ ๊ตฌ์กฐ ๋ณ€๊ฒฝ์ด ์šฉ์ด
  • ํ•˜์ง€๋งŒ ์ธ๋ฑ์Šค ์ ‘๊ทผ์ด ๋น„ํšจ์œจ์  (O(n))

๐Ÿ“ ์˜ˆ:

  • Linked List, Tree, Graph
  • ๋ฉ”๋ชจ๋ฆฌ์— ํฉ์–ด์ ธ ์žˆ์œผ๋‹ˆ ์บ์‹œ ์นœํ™”์„ฑ ๋‚ฎ์Œ

๐Ÿ”น Node (Linked List ์˜ˆ์‹œ)

[Data:10 | Next:์ฃผ์†Œ200] โ†’ [Data:20 | Next:์ฃผ์†Œ340] โ†’ [Data:30 | Next:null]
  • ํฉ์–ด์ ธ ์žˆ์ง€๋งŒ ํฌ์ธํ„ฐ(์ฃผ์†Œ)๋กœ ์ด์–ด์ง
  • CPU๊ฐ€ ๋ฐ์ดํ„ฐ๋ฅผ ์ฝ์œผ๋ ค๋ฉด "๋‹ค์Œ ์ฃผ์†Œ"๋ฅผ ๋”ฐ๋ผ๊ฐ€์•ผ ํ•จ โ†’ ์บ์‹œ ๋น„ํšจ์œจ



๐Ÿ“Œ Array vs Node ๊ธฐ๋ฐ˜ ๋น„๊ต

ํŠน์ง•Array ๊ธฐ๋ฐ˜Node ๊ธฐ๋ฐ˜
๋ฉ”๋ชจ๋ฆฌ ๋ฐฐ์น˜์—ฐ์†์ ๋น„์—ฐ์†์ 
์ ‘๊ทผ ์†๋„๋น ๋ฆ„ (O(1), ์ธ๋ฑ์Šค)๋А๋ฆผ (O(n), ํƒ์ƒ‰ ํ•„์š”)
์‚ฝ์ž…/์‚ญ์ œ๋А๋ฆผ (๋ฐ์ดํ„ฐ ์ด๋™ ํ•„์š”)๋น ๋ฆ„ (ํฌ์ธํ„ฐ๋งŒ ๋ณ€๊ฒฝ)
์บ์‹œ ํšจ์œจ์ข‹์Œ๋‚˜์จ
์‚ฌ์šฉ ์˜ˆ์‹œ๋ฐฐ์—ด, ํ•ด์‹œ ํ…Œ์ด๋ธ”์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ, ํŠธ๋ฆฌ, ๊ทธ๋ž˜ํ”„

๐Ÿ’ก Collection ํ•ต์‹ฌ ์ธํ„ฐํŽ˜์ด์Šค

โ—๏ธ List์™€ Set์˜ ๊ณตํ†ต์ ์ธ ๋ถ€๋ถ„๋งŒ ๋ฝ‘์•„์„œ Collection์˜ ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ๋งŒ๋“ค์—ˆ๋‹ค.

๐Ÿ“Ž List

  • ์ˆœ์„œ๊ฐ€ ์žˆ๋Š” ๋ฐ์ดํ„ฐ์˜ ์ง‘ํ•ฉ
  • ๋ฐ์ดํ„ฐ์˜ ์ค‘๋ณต์„ ํ—ˆ์šฉ
  • ๋Œ€๊ธฐ์ž ๋ช…๋‹จ

ArrayList, LinkedList, Stack, Vector ...

โ—๏ธList ๋ฉ”์„œ๋“œ


๐Ÿ“Ž Set

  • ์ˆœ์„œ๋ฅผ ์œ ์ง€ํ•˜์ง€ ์•Š๋Š” ๋ฐ์ดํ„ฐ์˜ ์ง‘ํ•ฉ.
  • ๋ฐ์ดํ„ฐ์˜ ์ค‘๋ณต์„ ํ—ˆ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค.
  • ์–‘์˜ ์ •์ˆ˜์ง‘ํ•ฉ, ์†Œ์ˆ˜์˜ ์ง‘ํ•ฉ

HashSet, TreeSet ...

โ—๏ธ Set์ธํ„ฐํŽ˜์ด์Šค ๋ฉ”์„œ๋“œ - Collection์ธํ„ฐํŽ˜์ด์Šค์™€ ๋™์ผ

โ—๏ธ ์ง‘ํ•ฉ๊ณผ ๊ด€๋ จ๋œ ๋ฉ”์„œ๋“œ

  • (Collection์— ๋ณ€ํ™”๊ฐ€ ์žˆ์œผ๋ฉด true, ์•„๋‹ˆ๋ฉด false๋ฅผ ๋ฐ˜ํ™˜)

๐Ÿ“Ž Map

  • LinkedHashMap์€ ์ˆœ์„œ๊ฐ€ ์žˆ๋‹ค.
  • ํ‚ค(key)์™€ ๊ฐ’(value)์˜ ์Œ(pair)์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฐ์ดํ„ฐ์˜ ์ง‘ํ•ฉ ์ˆœ์„œ๋Š” ์œ ์ง€๋˜์ง€ ์•Š์œผ๋ฉฐ, ํ‚ค๋Š” ์ค‘๋ณต์„ ํ—ˆ์šฉํ•˜์ง€ ์•Š๊ณ , ๊ฐ’์€ ์ค‘๋ณต์„ ํ—ˆ์šฉํ•œ๋‹ค.
  • ์šฐํŽธ๋ฒˆํ˜ธ, ์ง€์—ญ๋ฒˆํ˜ธ(์ „ํ™”๋ฒˆํ˜ธ)

HashMap, TreeMap, Hashable, Properties ...

โ—๏ธ Map ๋ฉ”์„œ๋“œ


๐Ÿ’ก Collection ์ธํ„ฐํŽ˜์ด์Šค ๋ฉ”์„œ๋“œ

โœ๏ธ int size()

  • Collection์— ์ €์žฅ๋œ ๊ฐ์ฒด์˜ ๊ฐœ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

โœ๏ธ Object[] toArray()

  • Collection์— ์ €์žฅ๋œ ๊ฐ์ฒด๋ฅผ ๊ฐ์ฒด๋ฐฐ์—ด(Object[])๋กœ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

โœ๏ธ Object[] toArray(Object a)

  • ์ง€์ •๋œ ๋ฐฐ์—ด์— Collection์˜ ๊ฐ์ฒด๋ฅผ ์ €์žฅํ•ด์„œ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

๐Ÿ“Ž ์ถ”๊ฐ€

โœ๏ธ boolean add(Object o) / boolean addAll(Collection c)

  • ์ง€์ •๋œ ๊ฐ์ฒด(o) ๋˜๋Š” Collection(c)์˜ ๊ฐ์ฒด๋“ค์„ Collection์— ์ถ”๊ฐ€ํ•œ๋‹ค.

๐Ÿ“Ž ๊ฒ€์ƒ‰

โœ๏ธ boolean contains(Object o) / boolean containsAll(Collection c)

  • ์ง€์ •๋œ ๊ฐ์ฒด(o) ๋˜๋Š” Collection(c)์˜ ๊ฐ์ฒด๋“ค์„ Collection์— ํฌํ•จ๋˜์–ด ์žˆ๋Š”์ง€ ํ™•์ธํ•œ๋‹ค.

โœ๏ธ boolean isEmpty()

  • Collection์ด ๋น„์–ด์žˆ๋Š”์ง€ ํ™•์ธํ•œ๋‹ค.

โœ๏ธ lterator iterator()

  • Collection์˜ lterator๋ฅผ ์–ป์–ด์„œ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

๐Ÿ“Ž ์‚ญ์ œ

โœ๏ธ void clear()

  • Collection์˜ ๋ชจ๋“  ๊ฐ์ฒด๋ฅผ ์‚ญ์ œํ•œ๋‹ค.

โœ๏ธ boolean remove / removeAll()

  • ์ง€์ •๋œ Collection์— ํฌํ•จ๋œ ๊ฐ์ฒด๋“ค์„ ์‚ญ์ œํ•œ๋‹ค.

โœ๏ธ boolen retainAll(C)

  • ์ง€์ •๋œ Collection์— ํฌํ•จ๋œ ๊ฐ์ฒด๋งŒ์„ ๋‚จ๊ธฐ๊ณ  ๋‹ค๋ฅธ ๊ฐ์ฒด๋“ค์€ Collection์—์„œ ์‚ญ์ œํ•œ๋‹ค.
  • ์ด ์ž‘์—…์œผ๋กœ ์ธํ•ด Collection์— ๋ณ€ํ™”๊ฐ€ ์žˆ์œผ๋ฉด true๋ฅผ ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด false๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

References
: https://cafe.naver.com/javachobostudy
: https://techvidvan.com/tutorials/java-collection-framework/

profile
Fill in my own colorful colors๐ŸŽจ

0๊ฐœ์˜ ๋Œ“๊ธ€