Arrays & Linked Lists

1. 배열(Array)이란?

배열은 같은 타입의 데이터를 연속적으로 나열한 자료구조다.
각 칸에는 인덱스(0, 1, 2…)가 붙어 있어서 A[i]처럼 바로 접근할 수 있다.

Python에서는 array 클래스와 list 클래스가 별개로 존재하는데, 편의상 같은 타입의 list를 배열처럼 사용하는 방식으로 진행한다.

---

2. 배열의 3가지 핵심 연산

배열에서 수행하는 연산은 크게 세 가지다.

• Search (Find): 특정 값 찾기
• Insert (Add): 새 원소 추가
• Delete (Remove): 원소 제거

여기서 중요한 점은, 배열이 정렬되어 있느냐 아니냐에 따라 각 연산의 시간복잡도가 완전히 달라진다는 것이다.

---

3. Sorted vs Unsorted: Trade-off

Unsorted Array

순서를 신경 쓰지 않아도 되니까 삽입/삭제가 자유롭다.

• Search: 처음부터 끝까지 다 봐야 함 → O(n)
• Insert: 맨 뒤에 그냥 붙이면 됨 → O(1)
• Delete: 지우고 싶은 원소와 마지막 원소를 swap한 뒤, 마지막 원소 제거 → O(1)

여기서 swap이 왜 O(1)이냐고 할 수 있는데, swap은 n이 얼마든
"temp에 저장 → A에 B 넣기 → B에 temp 넣기" 딱 3번으로 끝난다.
연산 횟수가 n에 비례해서 늘어나지 않으니까 O(1)이다.

Sorted Array

순서를 유지해야 하니까 삽입/삭제가 까다로운 대신, 탐색이 빠르다.

• Search: 이진 탐색(Binary Search) 사용 가능 → O(log n)
• Insert: 자리를 찾고 뒤 원소들을 전부 한 칸씩 밀어야 함 → O(n)
• Delete: 구멍을 메우기 위해 뒤 원소들을 당겨야 함 → O(n)

연산	Sorted Array	Unsorted Array
Search	O(log n)	O(n)
Insert	O(n)	O(1)
Delete	O(n)	O(1)
Sorting	O(n log n)	X

결론: 어떤 자료구조도 모든 연산에서 최고일 수는 없다. 상황에 맞게 골라 써야 한다.

---

4. Binary Search가 왜 O(log n)인가?

이진 탐색은 매 단계마다 탐색 범위를 절반씩 줄여나간다.

n = 8이라고 하면:

• 1번째 루프: 8개 → 4개
• 2번째 루프: 4개 → 2개
• 3번째 루프: 2개 → 1개

딱 3번 만에 끝난다. 그런데 8 = 2³이므로 루프 횟수 = log₂8 = 3이다.
n개짜리 배열이면 log₂n번 만에 끝나니까 O(log n)이다.

---

5. 배열의 한계(Drawbacks)

배열에는 두 가지 구조적 약점이 있다.

① 크기가 고정되어 있음 (Dynamic Resizing)

배열이 꽉 차면 더 큰 배열을 새로 만들고, 기존 데이터를 전부 복사해야 한다.
이 복사 작업은 O(n)이다.

그런데 배열 크기를 2배씩 늘리면, resize가 아주 가끔만 일어난다.
(1칸씩 늘리면 매번 resize가 일어나서 총 비용이 O(n²)이 된다.)

2배씩 늘릴 때 총 복사 비용을 계산하면:
1 + 2 + 4 + 8 + … + n = 약 2n

n번 append하는 동안 총 비용이 2n이니까, append 한 번당 평균 비용은 2, 즉 O(1)이다.
이를 Amortized O(1) 이라고 한다 — 가끔 O(n)이 발생하더라도, 장기적으로 평균 내면 O(1)로 수렴한다.

② 메모리가 연속적이어야 함

배열은 메모리에 연속으로 붙어있어야 한다.
그래서 두 배열을 이어붙이려면 새 배열을 만들어야 하는 불편함이 있다.

이 두 가지 한계 때문에 등장한 것이 연결 리스트(Linked List) 다.

---

6. 연결 리스트(Linked List)

메모리가 연속적이지 않아도 되고, 각 노드(Node)가 포인터로 다음 노드를 직접 가리키는 방식으로 연결된다.

Singly Linked List ⭐

각 노드는 element와 next 포인터를 가진다.

head → [A|•] → [B|•] → [C|•] → [D|∅] ← tail

핵심 메서드 3가지:

addFirst(e)

• 빈 리스트일 때: head = newest, tail = newest (같은 노드를 둘 다 가리킴)
• 원소가 있을 때: newest.next = head → head = newest
• → O(1)

addLast(e)

• 빈 리스트일 때: head = newest, tail = newest
• 원소가 있을 때: tail.next = newest → tail = newest
• → O(1)

removeFirst()

• head = head.next로 head를 옮기면 됨
• 삭제 후 빈 리스트가 되면 → tail = None (안 하면 tail이 삭제된 노드를 계속 가리킴)
• → O(1)

문제점: tail 삭제가 O(n)

tail을 삭제하려면 새로운 tail, 즉 기존 tail 바로 앞 노드를 알아야 한다.
그런데 Singly Linked List는 next로만 이동할 수 있어서 앞으로 거슬러 올라갈 방법이 없다. 결국 head부터 끝까지 다시 순회해야 하므로 O(n)이 된다.

Doubly Linked List

이 문제를 해결하기 위해 각 노드에 prev 포인터를 추가한다.

header ↔ [A] ↔ [B] ↔ [C] ↔ [D] ↔ trailer

header와 trailer라는 더미 노드를 양 끝에 두면, 모든 삽입/삭제가
동일한 패턴으로 처리되어 엣지 케이스(head/tail 예외처리)가 사라진다.

tail 삭제도 tail._prev로 바로 접근 가능 → O(1)

---

7. 최종 시간복잡도 비교

연산	Sorted Array	Unsorted Array	Singly Linked	Doubly Linked
Access(i)	O(1)	O(1)	O(n)	O(n)
Search	O(log n)	O(n)	O(n)	O(n)
Insert	O(n)	O(1)	O(1)	O(1)
Delete	O(n)	O(1)	O(1)	O(1)
Delete at Last	O(1)	O(1)	O(n)	O(1)

배열은 인덱스로 바로 접근(O(1))할 수 있지만,
연결 리스트는 head부터 순서대로 따라가야 해서 접근이 O(n)이다.
그 대신 삽입/삭제는 포인터만 바꾸면 되니까 O(1)이다.

결론: 정답인 자료구조는 없다. 상황에 맞게 trade-off를 이해하고 골라 쓰는 것이 핵심이다.