자료구조 - List

📦 1. ArrayList

1) ArrayList의 특징과 동작 원리

• ArrayList는 기본 배열과 달리 동적 배열 기반의 자료구조임
• 내부적으로 연속된 메모리 공간에 데이터를 저장함
• 기본 생성 시 내부 배열 크기는 10으로 생성하여 데이터를 저장함

✅ 장점

• 인덱스를 통한 접근 속도가 빠름
• 구조가 단순하고 사용이 직관적임
• Java 컬렉션 프레임워크와 호환성이 뛰어남

---

2) 동적 배열 크기 조정 원리

• 용량이 부족해지면 다음과 같은 과정으로 배열 크기를 늘림

1. 새 배열 생성
   • 기존 배열보다 약 1.5배 큰 배열을 새로 생성함
     • 이 때 찰나의 순간이지만 새로운 배열을 생성하기 때문에 메모리가 할당 됨
2. 데이터 복사
   • 기존 배열의 데이터를 새 배열에 깊은 복사함
     • ✔ 깊은 복사 : 객체 자체를 복제하는 방식
     • ✖ 얕은 복사 : 주소값만 복사하여 동일한 객체를 가리킴 → 원본 변경 시 함께 변경됨
3. 참조 변경
   • 내부 배열의 참조를 새 배열로 교체하여 확장된 구조로 유지

⚠️ 이 과정은 add() 연산 중 비정기적인 성능 저하(spike) 를 발생시킬 수 있고, 특히 대용량 데이터를 처리할 경우 고려가 필요함

🔗 2. LinkedList

1) LinkedList의 특징

• LinkedList는 노드(Node) 를 기반으로 데이터를 관리하는 자료구조
• 각 노드는 다음과 같은 두 가지 정보를 가짐
  • data: 실제 저장할 값
  • link: 다음(또는 이전) 노드를 가리키는 참조 포인터

https://akcoding.medium.com/data-structure-visualization-with-animations-b8a38d0a4708

🧱 연결 방식에 따른 분류

구분	설명
단방향 연결 리스트 (Singly Linked List)	각 노드가 다음 노드만 가리킴
양방향 연결 리스트 (Doubly Linked List)	각 노드가 이전 노드와 다음 노드 모두 가리킴

Java의 LinkedList 클래스는 기본적으로 양방향 연결 리스트로 구현되어 있음

---

2) 메모리 구조의 특성

• LinkedList는 비연속적인 메모리 공간에 노드를 저장함
• 삽입/삭제 시 메모리를 이동할 필요 없이 참조만 변경하므로 효율적임
• 다만, 각 노드마다 링크 포인터를 추가로 저장해야 하므로, ArrayList에 비해 메모리 사용량이 더 많음

---

3) 삽입/삭제 연산 동작 방식

📥 삽입 과정

1. 삽입 위치의 앞/뒤 노드를 탐색
2. 새로운 노드를 생성
3. 양쪽 노드의 참조 포인터를 새 노드에 연결

🗑️ 삭제 과정

1. 삭제할 노드를 탐색
2. 삭제할 노드의 앞/뒤 노드를 서로 연결하여 해당 노드를 리스트에서 제거
3. 제거된 노드는 GC(Garbage Collector)에 의해 메모리에서 해제됨

⚠️ LinkedList는 탐색 시 O(n) 의 시간이 소요되므로, 검색이 빈번한 경우엔 ArrayList보다 비효율적일 수 있음

---

🔍 정리: ArrayList vs LinkedList 비교

항목	ArrayList	LinkedList
내부 구조	동적 배열	노드 기반 연결 리스트
접근 속도	빠름 (O(1))	느림 (O(n))
삽입/삭제	중간 삽입/삭제 시 비용 큼 (O(n))	빠름 (O(1); 위치만 찾으면 됨)
메모리 효율	메모리 연속, 공간 활용 효율적	링크를 위한 추가 메모리 필요
메모리 구조	연속적	비연속적
적합한 상황	탐색이 빈번한 경우	삽입/삭제가 빈번한 경우

---

해당 게시글은 학습한 내용을 정리하고 복습하며 정리한 글이므로 틀린 부분이 있을 수 있음.