Amenable
Amenable's Blog
Amenable
  • λΆ„λ₯˜ 전체보기 (189)
    • πŸ“‚ JAVA (87)
      • μ΄νŽ™ν‹°λΈŒ μžλ°” (65)
      • μ£Όμš” κ°œλ… (22)
    • πŸ“‚ 개발 μ„œμ  (22)
      • μ‹€μš©μ£Όμ˜ ν”„λ‘œκ·Έλž˜λ¨Έ (1)
      • 객체지ν–₯의 사싀과 μ˜€ν•΄ (2)
      • 클린 μ½”λ“œ (8)
      • ν•¨κ»˜ 자라기 (1)
      • 그림으둜 λ°°μš°λŠ” HTTP&Network Basic (10)
    • πŸ“‚ λ°μ΄ν„°λ² μ΄μŠ€ (8)
      • κ°œλ… (8)
      • λ¬Έμ œν’€μ΄ (0)
    • πŸ“‚ λ„€νŠΈμ›Œν¬ (14)
      • κ°œλ… (6)
      • 성곡과 μ‹€νŒ¨λ₯Ό κ²°μ •ν•˜λŠ” 1%의 λ„€νŠΈμ›Œν¬ 원리 (8)
    • πŸ“‚ μŠ€ν”„λ§ (13)
      • κΈ°λ³Έ κ°œλ… (13)
    • πŸ“‚ WEB (5)
    • πŸ“‚ 자료ꡬ쑰 (12)
      • κ°œλ… (2)
      • μ •λ ¬ (8)
      • 트리 (2)
    • πŸ“‚ μ•Œκ³ λ¦¬μ¦˜ (10)
      • μ΅œμ†Œμ‹ μž₯트리 (2)
      • μ΅œλ‹¨ 경둜 (2)
      • λ¬Έμžμ—΄ (2)
      • ETC (4)
    • πŸ“‚ μ•Œκ³ λ¦¬μ¦˜_λ¬Έμ œν’€μ΄ (4)
      • BOJ_λ°±μ€€ (4)
    • πŸ“‚ ν”„λ‘œκ·Έλž˜λ° (3)
    • πŸ“‚ DevOps (2)
      • 배포 (2)
    • πŸ“‚ ν›„κΈ° (8)
      • μš°μ•„ν•œ ν…Œν¬μ½”μŠ€(ν”„λ¦¬μ½”μŠ€) (4)
      • 2023λ…„ (3)
      • 2024λ…„ (1)
    • πŸ“‚ 회고 (1)
      • 2023λ…„ (1)

λΈ”λ‘œκ·Έ 메뉴

  • πŸš€ GitHub

ν‹°μŠ€ν† λ¦¬

hELLO Β· Designed By μ •μƒμš°.
Amenable
πŸ“‚ 자료ꡬ쑰/κ°œλ…

λ°°μ—΄(Array) VS λ°°μ—΄ 리슀트(ArrayList) VS μ—°κ²° 리슀트(LinkedList)

λ°°μ—΄(Array) VS λ°°μ—΄ 리슀트(ArrayList) VS μ—°κ²° 리슀트(LinkedList)
πŸ“‚ 자료ꡬ쑰/κ°œλ…

λ°°μ—΄(Array) VS λ°°μ—΄ 리슀트(ArrayList) VS μ—°κ²° 리슀트(LinkedList)

2023. 6. 11. 11:48

πŸ“™ 1. λ°°μ—΄

πŸ“Œ 1. κ°œλ… 및 νŠΉμ§•

  • λ°°μ—΄(Array)μ΄λž€ 같은 νƒ€μž…μ˜ μ—¬λŸ¬ λ³€μˆ˜λ₯Ό ν•˜λ‚˜μ˜ 묢음으둜 λ‹€λ£¨λŠ” 것을 λ§ν•œλ‹€.
  • 배열을 κ΅¬μ„±ν•˜λŠ” 각각의 값을 λ°°μ—΄ μš”μ†Œ(Element), λ°°μ—΄μ—μ„œμ˜ μœ„μΉ˜λ₯Ό κ°€λ¦¬ν‚€λŠ” 숫자λ₯Ό 인덱슀(Index)라고 ν•œλ‹€.
  • 배열은 μ°Έμ‘° κ°μ²΄μ΄λ―€λ‘œ 배열을 κ°€λ¦¬ν‚€λŠ” μ°Έμ‘° λ³€μˆ˜λŠ” μŠ€νƒ μ˜μ˜μ— ν• λ‹Ήλ˜λ©°, 이 μ°Έμ‘° λ³€μˆ˜κ°€ 가리킀고 μžˆλŠ” μ£Όμ†Œκ°’μ€ μ‹€μ œ νž™ μ˜μ—­μ— μƒμ„±λ˜λŠ” λ°°μ—΄μ˜ μ£Όμ†Œκ°’μ΄λ‹€.
  • λ°°μ—΄μ˜ ν¬κΈ°λŠ” 고정적이닀.
  • λ©”λͺ¨λ¦¬ κ³΅κ°„이 μ—°μ†μ μœΌλ‘œ κ΅¬μ„±λœλ‹€.

πŸ“Œ 2. μž₯점

  • 인덱슀λ₯Ό ν™œμš©ν•  수 있기 λ•Œλ¬Έμ—, νŠΉμ • μœ„μΉ˜μ— μžˆλŠ” μ›μ†Œμ— λŒ€ν•œ μ ‘κ·Όμ˜ μ‹œκ°„λ³΅μž‘λ„κ°€ O(1)이닀.
  • 인덱슀λ₯Ό ν™œμš©ν•  μˆ˜ μžˆκΈ° λ•Œλ¬Έμ—, νŠΉμ • μœ„μΉ˜μ— μžˆλŠ” μ›μ†Œμ— λŒ€ν•œ μˆ˜μ •μ˜ μ‹œκ°„λ³΅μž‘도가 O(1)이닀.

πŸ“Œ 3. λ‹¨μ 

  • 크기가 고정적이기 λ•Œλ¬Έμ— 더 λ§Žμ€ 데이터λ₯Ό μ €μž₯ν•˜κΈ° μœ„ν•΄μ„œλŠ” 더 큰 배열을 λ§Œλ“€κ³  이전 λ°°μ—΄μ˜ 데이터λ₯Ό μƒˆλ‘œ λ§Œλ“  λ°°μ—΄λ‘œ 볡사해야 ν•œλ‹€. μ΄λ•Œ, O(n)의 μ‹œκ°„λ³΅μž‘λ„κ°€ μ†Œμš”λœλ‹€.
  • λ°°μ—΄ 쀑간에 μžˆλŠ” μ›μ†Œλ₯Ό μ œκ±°ν•΄μ•Ό ν•˜λŠ” 경우, μ‚­μ œν•˜κ³ μž ν•˜λŠ” μœ„μΉ˜μ˜ 인덱슀 뒀에 μžˆλŠ” μ›μ†ŒλΆ€ν„° λ°°μ—΄μ˜ 맨 끝에 μžˆλŠ” μ›μ†ŒκΉŒμ§€ μ•žμœΌλ‘œ ν•œ μΉΈμ”© μ΄λ™ν•΄μ€˜μ•Ό ν•œλ‹€. μ΄λ•Œ, O(n)의 μ‹œκ°„λ³΅μž‘λ„κ°€ μ†Œμš”λœλ‹€.
  • λ°°μ—΄ μ€‘간에 μ›μ†Œλ₯Ό μ‚½μž…ν•΄μ•Ό ν•˜λŠ” κ²½μš°μ—λ„ μœ„와 λ™μΌν•˜κ²Œ O(n)의 μ‹œκ°„이 μ†Œμš”λœλ‹€.

 

 

πŸ“™ 2. λ°°μ—΄λ¦¬μŠ€νŠΈ(ArrayList)

πŸ“Œ 1. κ°œλ… 및 νŠΉμ§•

  • λ°°μ—΄λ¦¬μŠ€νŠΈ(ArrayList)λž€ λ‚΄λΆ€μ μœΌλ‘œ λ°°μ—΄(Array)을 μ΄μš©ν•˜μ—¬ μš”μ†Œλ₯Ό μ €μž₯ν•˜λŠ” μžλ£Œκ΅¬μ‘°μ΄λ‹€.
  • ArrayList ν΄λž˜μŠ€λŠ” λ‚΄λΆ€μ μœΌλ‘œ Object [] 배열을 μ΄μš©ν•˜μ—¬ μš”μ†Œλ₯Ό μ €μž₯ν•œλ‹€.
  • 크기가 κ³ μ •λ˜μ–΄ μžˆλŠ” λ°°μ—΄κ³Ό 달리 데이터 μ μž¬λŸ‰μ— 따라 κ°€λ³€μ μœΌλ‘œ 곡간을 λŠ˜λ¦¬κ±°λ‚˜ 쀄인닀.
  • List μΈν„°νŽ˜μ΄μŠ€μ—μ„œ μ •μ˜ν•œ λ‹€μ–‘ν•œ λ©”μ„œλ“œλ₯Ό μ‚¬μš©ν•  수 μžˆλ‹€.
  • λ°μ΄ν„°λŠ” μ—°μ†μ μœΌλ‘œ λ¦¬μŠ€νŠΈμ— λ“€μ–΄μžˆμ–΄μ•Ό ν•˜λ―€λ‘œ μ€‘간에 λΉˆ κ³΅κ°„이 μžˆμœΌλ©΄ μ•ˆ λœλ‹€.

πŸ“Œ 2. μž₯점

  • 인덱슀λ₯Ό ν™œμš©ν•  수 있기 λ•Œλ¬Έμ— νŠΉμ • μœ„μΉ˜μ— μžˆλŠ” μ›μ†Œμ— λŒ€ν•œ μ ‘κ·Όκ³Ό μˆ˜μ •μ— λŒ€ν•΄μ„œ O(1)의 μ‹œκ°„λ³΅μž‘λ„κ°€ μ†Œμš”λœλ‹€.
  • μ €μž₯ κ³΅κ°„μ˜ 크기가 κ°€λ³€μ μœΌλ‘œ λ³€ν•˜κΈ° λ•Œλ¬Έμ— λ”°λ‘œ 신경을 μ“°μ§€ μ•Šμ•„λ„ λœλ‹€.
  • λ°°μ—΄ λ¦¬μŠ€νŠΈμ˜ μ€‘간에 λΉˆ κ³΅κ°„을 ν—ˆμš©ν•˜μ§€ μ•ŠκΈ° λ•Œλ¬Έμ— λ°°μ—΄μ— λΉ„ν•΄ λ©”λͺ¨λ¦¬ κ³΅κ°„μ˜ λ‚­λΉ„κ°€ μ—†λ‹€.

πŸ“Œ 3. λ‹¨μ 

  • λ©”μ„œλ“œλ₯Ό ν™œμš©ν•΄μ„œ κ°„νŽΈν•˜κ²Œ 쀑간에 μ›μ†Œλ₯Ό μ‚½μž…/μ‚­μ œν•  수 μžˆμ§€λ§Œ μ‹œκ°„λ³΅μž‘λ„λŠ” μ—¬μ „νžˆ O(n)이닀.
  • λ˜ν•œ, μ €μž₯ κ³΅κ°„을 ν™•μž₯ λ° λ³΅μ‚¬ν•˜λŠ” κ³Όμ •μ—μ„œλ„ μ‹œκ°„λ³΅μž‘도가 O(n)이닀.

 

 

πŸ“™ 3. μ—°κ²°λ¦¬μŠ€νŠΈ(LinkedList)

πŸ“Œ 1. κ°œλ… 및 νŠΉμ§•

  • λ°°μ—΄λ¦¬μŠ€νŠΈ(ArrayList)κ°€ λ‚΄λΆ€μ μœΌλ‘œ 배열을 μ΄μš©ν•˜μ—¬ λ©”μ„œλ“œλ‘œ μ‘°μž‘μ΄ κ°€λŠ₯ν•˜κ²Œ λ§Œλ“  μ»¬λ ‰μ…˜μ΄λΌλ©΄, μ—°κ²°λ¦¬μŠ€νŠΈ(LinkedList)λŠ” λ…Έλ“œ(객체)끼리의 μ£Όμ†Œ 포인터λ₯Ό μ„œλ‘œ 가리킀며 μ°Έμ‘°(링크)ν•¨μœΌλ‘œμ¨ μ΄μ–΄μ§€λŠ” ꡬ쑰이닀.
  • μ—°κ²°λ¦¬μŠ€νŠΈμ˜ μ’…λ₯˜λ‘œλŠ” 단방ν–₯ μ—°κ²° 리슀트(Singly Linked List), μ–‘λ°©ν–₯ μ—°κ²° 리슀트(Doubly Linked List), μ–‘λ°©ν–₯ μ›ν˜• μ—°κ²° 리슀트(Doubly Circular Linked List)κ°€ μžˆλ‹€.
  • μžλ°”μ—μ„œ LinkedList μ»¬λ ‰μ…˜ ν΄λž˜μŠ€λŠ” μ–‘λ°©ν–₯ μ—°κ²° 리슀트둜 λ§Œλ“€μ–΄μ Έ μžˆλ‹€.
  • μ—°κ²°λ¦¬μŠ€νŠΈ λ˜ν•œ μ €μž₯ κ³΅κ°„μ˜ ν¬κΈ°λŠ” κ°€λ³€μ μ΄λ‹€.

πŸ“Œ 2. μž₯점

  • 맨 μ•žμ— μ›μ†Œλ₯Ό μ‚½μž…ν•˜λŠ” 경우 κΈ°μ‘΄ μ›μ†Œλ“€μ„ ν•œ μΉΈμ”© 이동해쀄 ν•„μš”κ°€ μ—†μœΌλ―€λ‘œ O(1)의 μ‹œκ°„λ³΅μž‘λ„λ₯Ό κ°€μ§„λ‹€.
  • μ–‘λ°©ν–₯ μ—°κ²° 리슀트의 경우 맨 뒀에 μ›μ†Œλ₯Ό μ‚½μž…ν•  λ•Œ O(1)의 μ‹œκ°„λ³΅μž‘λ„λ₯Ό κ°€μ§„λ‹€.
  • λ°°μ—΄μ΄λ‚˜ λ°°μ—΄ λ¦¬μŠ€νŠΈμ™€ λ‹¬λ¦¬ μ €μž₯ κ³΅κ°„에 μƒˆλ‘œμš΄ μ›μ†Œκ°€ μ‚½μž…λ˜κ±°λ‚˜ μ‚­μ œλ  λ•Œ, μ €μž₯ κ³΅κ°„을 ν™•μž₯ν•˜κ±°λ‚˜ μΆ•μ†Œν•˜μ—¬ μž¬ν• λ‹Ήν•΄ 쀄 ν•„μš”κ°€ μ—†λ‹€.

πŸ“Œ 3. λ‹¨μ 

  • 인덱슀λ₯Ό ν™œμš©ν•  수 μ—†κΈ° λ•Œλ¬Έμ— νŠΉμ • μœ„μΉ˜μ— μžˆλŠ” μ›μ†Œμ— μ ‘κ·Όν•˜κΈ° μœ„ν•΄μ„œλŠ” λ…Έλ“œλ“€μ„ λ”°λΌκ°€λ©΄μ„œ 탐색해야 ν•œλ‹€. κ·Έλž˜μ„œ O(n)의 μ‹œκ°„λ³΅μž‘λ„λ₯Ό κ°€μ§„λ‹€.
  • νŠΉμ • μœ„μΉ˜μ— μžˆλŠ” μ›μ†Œμ— λŒ€ν•œ μˆ˜μ •λ„ μœ„μ™€ 같은 이유둜 O(n)의 μ‹œκ°„λ³΅μž‘λ„λ₯Ό κ°€μ§„λ‹€.
  • 쀑간에 μ›μ†Œλ₯Ό μ‚½μž…ν•˜κ±°λ‚˜ μ‚­μ œν•˜λŠ” κ²½μš°μ—λ„ ν•΄λ‹Ή μœ„μΉ˜λ₯Ό μ°Ύμ•„μ•Ό ν•˜κΈ° λ•Œλ¬Έμ— O(n)의 μ‹œκ°„λ³΅μž‘도λ₯Ό κ°€μ§„λ‹€.

 

 

πŸ“™ 4. 비ꡐ

  λ°°μ—΄(Array) λ°°μ—΄ 리슀트(ArrayList) μ—°κ²° 리슀트(LinkedList)
μ €μž₯ κ³΅κ°„μ˜ 크기 고정적 가변적 가변적
λ©”λͺ¨λ¦¬ κ³΅κ°„μ˜ 연속성 O O X
νŠΉμ • μœ„μΉ˜μ— μžˆλŠ” μ›μ†Œμ— λŒ€ν•œ μ ‘κ·Ό O(1) O(1) O(n)
νŠΉμ • μ›μ†Œλ₯Ό 탐색 O(n) O(n) O(n)
맨 μ•žμ— μ›μ†Œ μΆ”κ°€ / μ‚­μ œ O(n) O(n) O(1)
쀑간에 μ›μ†Œ μΆ”κ°€ / μ‚­μ œ O(n) O(n) O(n)
맨 뒀에 μ›μ†Œ μΆ”κ°€ / μ‚­μ œ O(n) O(n) O(1)

 

ν•΄λ‹Ή 글은
Inpa λ‹˜μ˜ 'JAVA λ°°μ—΄(Array) μ™„λ²½ 닀루기 κ°€μ΄λ“œ', 'μžλ°” ArrayList ꡬ쑰 & μ‚¬μš©λ²• 정리', 'μžλ°” LinkedList ꡬ쑰 & μ‚¬μš©λ²• - μ •λ³΅ν•˜κΈ°', 'ArrayList vs LinkedList νŠΉμ§• & μ„±λŠ₯ 비ꡐ',
λͺ½κ΅¬ λ‹˜μ˜ '[Java] λ°°μ—΄(Array) vs. λ°°μ—΄λ¦¬μŠ€νŠΈ(ArrayList) vs. μ—°κ²°λ¦¬μŠ€νŠΈ(LinkedList)'
λ₯Ό μ°Έκ³ ν•˜μ˜€μŠ΅λ‹ˆλ‹€.

'πŸ“‚ 자료ꡬ쑰 > κ°œλ…' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

λ°°μ—΄(Array)  (0) 2023.06.11
  • πŸ“™ 1. λ°°μ—΄
  • πŸ“™ 2. λ°°μ—΄λ¦¬μŠ€νŠΈ(ArrayList)
  • πŸ“™ 3. μ—°κ²°λ¦¬μŠ€νŠΈ(LinkedList)
  • πŸ“™ 4. 비ꡐ
'πŸ“‚ 자료ꡬ쑰/κ°œλ…' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
  • λ°°μ—΄(Array)
Amenable
Amenable
CS, μžλ°”, 자료ꡬ쑰, μ•Œκ³ λ¦¬μ¦˜, μŠ€ν”„λ§, μŠ€ν”„λ§ λΆ€νŠΈμ— ν•΄λ‹Ήν•˜λŠ” κ°œλ°œμ— κ΄€ν•œ λ‚΄μš©μ„ κ³΅μœ ν•©λ‹ˆλ‹€.

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”

단좕킀

λ‚΄ λΈ”λ‘œκ·Έ

λ‚΄ λΈ”λ‘œκ·Έ - κ΄€λ¦¬μž ν™ˆ μ „ν™˜
Q
Q
μƒˆ κΈ€ μ“°κΈ°
W
W

λΈ”λ‘œκ·Έ κ²Œμ‹œκΈ€

κΈ€ μˆ˜μ • (κΆŒν•œ μžˆλŠ” 경우)
E
E
λŒ“κΈ€ μ˜μ—­μœΌλ‘œ 이동
C
C

λͺ¨λ“  μ˜μ—­

이 νŽ˜μ΄μ§€μ˜ URL 볡사
S
S
맨 μœ„λ‘œ 이동
T
T
ν‹°μŠ€ν† λ¦¬ ν™ˆ 이동
H
H
단좕킀 μ•ˆλ‚΄
Shift + /
⇧ + /

* λ‹¨μΆ•ν‚€λŠ” ν•œκΈ€/영문 λŒ€μ†Œλ¬Έμžλ‘œ 이용 κ°€λŠ₯ν•˜λ©°, ν‹°μŠ€ν† λ¦¬ κΈ°λ³Έ λ„λ©”μΈμ—μ„œλ§Œ λ™μž‘ν•©λ‹ˆλ‹€.