💡 ArrayList

✅ List 인터페이스를 구현한 동적 배열(Resizable array)

• 쉽게 말하면 '늘어나는 배열' → 내부적으로 배열을 가지고 있고, 필요할 때 자동으로 크기를 키워가며 요소를 저장한다.
• ArrayList와 달리 Vector는 자체적으로 동기화처리가 되어 있다.
• List 인터페이스를 구현하므로, 저장순서가 유지되고 중복을 허용한다.
• 인덱스로 빠르게 접근 가능하다.

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializale {
	...
    protected Object[] elementData; // 객체를 담기 위한 배열
	...
}

📍 특징:

• 조회 빠름 (index 접근)
• 삽입/삭제 느림 (중간에 끼워 넣으면 뒤 요소들을 다 밀어야 함)
• 크기를 초과하면 내부 배열을 더 큰 배열로 새로 만들어서 복사함

List<String> list = new ArrayList<>();
list.add("A");              // 맨 뒤에 추가
list.add(0, "B");           // index 0에 삽입 (중간 삽입)
String s = list.get(1);     // 인덱스로 조회
list.remove(0);             // 인덱스나 객체로 삭제
int size = list.size();     // 현재 요소 개수

---

📌 어떻게 동작할까?

1. 처음에는 작은 배열을 하나 만든다.
2. 요소를 add() 해서 채워 넣는다.
3. 만약 다 찼는데 더 넣어야 하면?
   • 더 큰 배열을 새로 만들어서 기존 값을 복사해 넣는다.
   • 그래서 크기가 계속 "자동으로" 늘어난다.

---

📌 장점 & 단점

✅ 장점

• 인덱스로 바로 접근 가능 → 빠름 (O(1))
• 자동으로 크기 늘려줌 → 편리함
• 순차 탐색에 빠름 (캐시 효율 좋음)

❌ 단점

• 중간 삽입/삭제 느림 (O(n)) → 뒤에 있는 요소들을 다 밀어야 해서
• 크기 늘릴 때마다 배열 복사 비용 발생
• 기본형(int, double 등)은 바로 못 넣고 Wrapper 클래스(Integer, Double 등)로 감싸야 함

---

📌 언제 쓰면 좋을까?

• 데이터 조회가 많고 삽입/삭제는 주로 끝에만 일어나는 경우 → ArrayList 최적
• 예: 게시판 글 목록, 쇼핑몰 상품 리스트 등

---

✏️ ArrayList 생성자

✔️ String class / Collection_List의 생성자, 메서드의 기능이 유사하기 때문에 간단요약함.

❗️ initialCapacity: 배열의 용량

✏️ ArrayList 메서드

📎 추가

❗️ int index: 저장위치

📎 삭제

❗️ void clear(): 모든 객체 삭제

📎 검색

❗️ 못찾으면 -1 반환
❗️ Object set(int index, Object element): 변경

📎 그 외

❗️ int size(): 저장된 객체의 갯수

---

💡 LinkedList

✅ LinkedList는 노드(Node)들을 포인터(참조)로 연결한 자료구조를 기반으로 한 List 구현체

• ArrayList는 배열 기반이라 연속된 공간에 저장되지만, LinkedList는 떨어져 있는 노드들이 서로 앞/뒤 주소를 알고 연결돼 있다.
• 자바의 LinkedList는 이중 연결 리스트(doubly linked list) 로 구현돼 있어서, 앞/뒤로 모두 탐색 가능하다.

---

📌 내부 구조

각 노드는 다음과 같은 구조를 가짐:

[prev] <- [data] -> [next]

즉,

• data : 실제 값 저장
• prev : 이전 노드 주소
• next : 다음 노드 주소

자바 LinkedList 는 첫 번째 노드(head)와 마지막 노드(tail) 참조를 관리한다.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        list.add("제니");           // 맨 뒤에 추가
        list.addFirst("철수");       // 맨 앞에 추가
        list.addLast("영희");        // 맨 뒤에 추가

        System.out.println(list.get(1)); // index 1 탐색 (느림)

        list.remove("철수");         // 값으로 삭제
        list.removeFirst();          // 첫 요소 삭제
        list.removeLast();           // 마지막 요소 삭제
    }
}

---

📌 성능 분석 (빅오)

• 맨 앞/뒤 삽입/삭제 → O(1) (노드 참조만 바꾸면 됨)
• 중간 삽입/삭제 → O(n) (중간 노드를 찾는 데 시간이 걸림)
• 인덱스 접근(get(i)) → O(n) (앞이나 뒤에서부터 차례대로 이동해야 함)

👉 조회 성능은 ArrayList보다 훨씬 느리지만, 삽입/삭제는 특정 상황에서 더 빠름.

---

📌 장점 & 단점

✅ 장점

• 삽입/삭제가 빠름 (특히 앞이나 뒤에서)
• 크기를 미리 정할 필요 없음 (배열처럼 확장 복사 비용 없음)

❌ 단점

• 인덱스 조회가 느림 (O(n))
• 노드마다 prev, next 참조를 저장해야 해서 메모리 사용량 많음
• 캐시 효율이 낮아 순차 탐색도 ArrayList보다 느린 경우가 많음

---

📌 언제 쓰면 좋을까?

• 중간 삽입/삭제가 많을 때 → LinkedList 유리
• 앞/뒤에서만 삽입/삭제할 때 → LinkedList 매우 유리 (addFirst, removeFirst 등)
• 조회가 많을 때 → ArrayList 훨씬 유리

👉 그래서 실무에서는 LinkedList를 특수한 상황에서만 쓰고, 일반적으로는 ArrayList가 더 많이 쓰인다.

---

📎 Singly linkedList

class Node { // 요소 하나하나가 Node를 의미한다.
	Node next; //  다음노드가 어딘지 참조노드를 가르키게 된다.
    Object obj; // 데이터
}

class SinglyLinkedNode {
    int val;
    SinglyLinkedNode next = null;
    SinglyLinkedNode(int v) {
        val = v;
    }
}

✔️ 단일 연결 리스트(singly linkedList)
: 다음 요소를 가르키는 참조만을 가지는 연결 리스트

• 요소의 저장과 삭제 작업이 다음 요소를 가리키는 참조만 변경하면 되므로, 아주 빠르게 처리될 수 있다.
• 연결리스트, 데이터 접근성 낮음
  : 현재 요소에서 이전 요소로 접근하기가 매우 어렵다.

📎 doubly linkedList

class Node {
	Node next; // 다음요소
    Node previous; // 이전요소
    Object obj; // 데이터
}

class DoublyListNode {
    int val;
    DoublyListNode next;
    DoublyListNode prev;
    DoublyListNode(int x) {
    	val = x;
    }
}

✔️ 이중 연결 리스트(doubly linked list)
: 이전 요소를 가리키는 참조도 가지는 연결 리스트

• 이중 연결리스트, 접근성 향상
  : 연결이 2개 ➡️ 다음요소와 이전요소 총 참조를 2개 가지고 있다.

• 추가 삭제할 때에는 2개의 연결을 끊어줘야하기 때문에 시간이 좀 더 걸린다.

• 하지만 여전히 한번에 2개 3개 건너뛰는것은 불가능하다.

📎 doubly circular linkedList

✔️ 이중 원형 연결리스트(doubly circular linkedList)

• 마지막 요소를 맨 처음 요소에, 맨 처음 요소를 맨 끝의 요소로 연결할 수 있다.

  맨 처음요소에서 맨 끝의 요소를 이동할 때 하나하나 다음 노드로 이동해야 하는 것을 앞에서 바로 맨 끝으로 이동 할 수 있다.

  예를 들어, 채널 1에서 리모컨으로 채널을 감소시킬 때, 채널0이 되는 것이 아니라 채널 999인 젤 마지막 채널로 향한다. 이런 원리와 마찬가지이다.

💡 ArrayList VS LinkedList

---

항목	ArrayList	LinkedList
내부 구조	배열 기반	노드 기반 (이중 연결 리스트)
접근 속도	인덱스 O(1) (빠름)	인덱스 O(n) (느림)
삽입/삭제 (중간)	O(n) (뒤 요소 이동 필요)	O(n) (노드 탐색 후 O(1) 연결 변경)
삽입/삭제 (앞/뒤)	앞: O(n), 뒤: amortized O(1)	앞/뒤: O(1)
메모리 효율	낮음(추가 참조 없음)	높음(노드마다 prev/next 저장)
캐시 친화도	좋음	나쁨

1. 순차적으로 추가하기

• ArrayList: 406
• LinkedList: 606

LinkedList는 새로운 객체를 하나하나다 만들기 때문에 배열보다는 추가가 느리다.

2. 순차적으로 삭제하기

• ArrayList: 11
• LinkedList: 46

3. 중간에 추가하기

• ArrayList: 7382
• LinkedList: 31

4. 중간에서 삭제하기

• ArrayList: 6694
• LinkedList: 380

5. 접근시간테스트

• ArrayList: 1
• LinkedList: 432

• 순차적으로 데이터를 추가 / 삭제: ArryaList가 빠름
• 비순차적으로 데이터를 추가 / 삭제: LinkedList가 빠름
• 접근시간(access time): ArrayList가 빠름
  index가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

---

References
: https://cafe.naver.com/javachobostudy