Array

• 고정 크기의 데이터 구조
• 동일한 데이터 타입의 값을 메모리 상에 연속적으로 저장함

장점

• 인덱스를 통해 요소에 빠르게 접근 가능 → 읽기 속도가 매우 빠름
  • index 접근하는 방법 : [배열 첫 data의 주소값] + [offset]
• 고정된 크기이므로 메모리 사용 예측 가능 → 메모리 효율성

단점

• 배열 크기가 정해지면 변경 불가
  • 메모리 낭비나 추가적인 overhead가 발생할 수 있음
• 삽입, 삭제가 비효율적 → 배열의 중간에 삽입, 삭제 시 요소를 이동시켜야 함

시간복잡도

	Array
access	$O(1)$
append	$O(1)$
마지막 원소delete	$O(1)$
insertion	$O(n)$
deletion	$O(n)$
search	$O(n)$

• 📗 Dynamic array
  • Dynamic Array는 저장공간이 가득 차게 되면 resize → 유동적으로 size를 조절하여 데이터를 저장하는 자료구조
    
  • resize의 대표적인 방법으로는 Doubling이 있음
  • 메모리를 초과하게 되면 기존 배열의 size보다 두배 큰 배열을 선언하고 데이터를 옮김

---

ArrayList

• 배열을 기반으로 동작, 크기가 자동으로 조절 - 동적 배열 사용해 요소 저장
• 배열을 사용하므로 메모리에서 연속된 공간에 데이터 저장

장점

• 동적 크기 조절
• 빠른 읽기 성능

단점

• 삽입, 삭제 비효율적
• 메모리 낭비 → 크기를 동적으로 조절하기 위해 실제 필요한 크기보다 더 많은 메모리를 사용할 수도 있음

---

LinkedList

• 이중연결리스트

• 각 요소가 노드로 구현

  • 노드는 데이터 값과 다음 노드의 주소 저장(양방향의 경우, 이전 주소도)

  
  출처 : https://poetic-code.tistory.com/81
  

• 메모리상에서는 비연속적 저장, 논리적 연속성을 가짐

장점

• 삽입, 삭제 효율적 → 요소 이동 없이 노드의 참조만 변경하면 되기 때문에 빠르게 처리
• 동적 크기 조정 → 데이터 추가 시, 자동으로 크기 증가

단점

• 느린 접근 속도 → 처음 노드부터 따라가야 함
• 메모리 오버헤드 → 데이터 외에 참조도 저장해야 해서 메모리 사용량 ↑

시간복잡도

	Linked list
access	$O(n)$
search	$O(n)$
insertion	$O(1)$
deletion	$O(1)$

---

Array vs ArrayList vs LinkedList 비교

특징	Array	ArrayList	LinkedList
구조	고정 크기의 배열 (크기 변경 불가)	동적 크기의 배열 (자동으로 크기 조정)	이중 연결 리스트 (노드 기반)
메모리 저장 방식	연속된 메모리 공간에 저장	연속된 메모리 공간에 저장	비연속적인 메모리 공간에 노드로 저장
크기	선언 시 고정, 크기 변경 불가	자동으로 크기 조정 (내부적으로 배열 복사)	동적 크기, 삽입/삭제 시 크기 조정
삽입/삭제 성능	중간 삽입/삭제 시 느림 (O(n))	중간 삽입/삭제 시 느림 (O(n))	중간 삽입/삭제가 빠름 (O(1))
읽기 성능	인덱스를 통한 빠른 액세스 (O(1))	인덱스를 통한 빠른 액세스 (O(1))	노드를 따라가며 읽어야 해서 느림 (O(n))
메모리 사용	요소만 저장	요소만 저장	각 노드에 추가로 이전/다음 노드 참조가 필요함
초기 크기 설정	필요 (크기 변경 불가)	필요 없음 (자동 크기 증가)	필요 없음
사용 사례	크기가 고정된 데이터, 빠른 접근이 필요한 경우	크기가 가변적이고, 읽기 성능이 중요한 경우	삽입/삭제가 빈번하게 발생하는 경우
멀티스레드 안전성	지원하지 않음 (수동으로 동기화 필요)	지원하지 않음 (수동으로 동기화 필요)	지원하지 않음 (수동으로 동기화 필요)
초기 성능	빠름 (고정 크기로 메모리 할당)	초기 메모리 할당 후 배열 복사 시 느려질 수 있음	초기 메모리 할당은 빠름, 이후 노드 삽입/삭제 가능