어레이와 링크드 리스트

프로그래밍에서는 데이터를 어떻게 저장하고 다루느냐에 따라 선택해야 할 자료구조가 달라진다. 특히 배열과 링크드 리스트는 기본 구조는 비슷해 보이지만 내부 동작 방식은 크게 다르다.

이 글에서는 어레이(Array)와 링크드 리스트(Linked List)의 차이를 직관적으로 이해할 수 있도록, 간단한 예시와 함께 핵심 개념을 정리해본다.

어레이: 연속된 공간에 데이터를 저장하는 구조

어레이는 정해진 크기의 연속된 메모리 공간에 데이터를 저장한다.
각 요소는 인덱스로 접근할 수 있고, 접근 속도는 항상 O(1)이다.

예를 들어, 길이가 5인 배열이 있다면 내부적으로는 이렇게 붙어 있는 상태다.

[0][1][2][3][4]

이 덕분에 인덱스로 접근하는 연산은 매우 빠르다. CPU가 연속된 메모리를 잘 캐싱하기 때문에 실제 성능도 좋다.

하지만 이런 ‘연속된 공간’ 덕분에 발생하는 단점도 있다.

❗ 중간에 삽입/삭제가 어렵다

배열 중간에 새로운 원소를 넣기 위해서는, 뒤에 있는 데이터를 모두 한 칸씩 이동시켜야 한다.

예를 들어 [A, B, C, D] 사이에 새로운 값 X를 넣는다면,

[A, B, C, D]
 → C, D를 뒤로 민다 → [A, B, X, C, D]

이 과정에서 최악의 경우 전체 배열을 이동해야 한다. → O(N)

❗ 공간이 가득 차면 새로운 배열을 통째로 만들어야 한다

배열은 크기가 고정되어 있기 때문에, 만약 더 많은 데이터를 넣어야 한다면
아예 더 큰 배열을 새로 만들고 기존 데이터를 복사해야 한다.

---

링크드 리스트: 포인터로 이어 붙인 유연한 구조

링크드 리스트는 데이터를 연속된 공간에 두지 않는다.
각 요소(Node)는 다음 노드를 가리키는 포인터(Link)를 가지고 있다.

[Node1] → [Node2] → [Node3] → [Node4]

❗ 삽입/삭제가 쉽다

중간에 새로운 노드를 넣고 싶다면 포인터만 바꿔주면 된다.

[Node1] → [Node2] 
               ↓
           [NewNode] 
               ↓
          [Node3]

이 작업은 포인터만 수정하면 되므로 O(1)에 처리할 수 있다.
삭제도 동일하게, 앞뒤 노드의 포인터를 바꿔주면 된다.

❗ 특정 원소 접근은 느리다

링크드 리스트는 인덱스가 없기 때문에, 특정 노드를 찾으려면
앞에서부터 하나씩 따라가야 한다.

Head → 1 → 2 → 3 → …  

따라서 접근은 O(N)이다.
또한 메모리가 연속적이지 않아 CPU 캐시 효율도 낮다.

어레이 vs 링크드 리스트 — 어떻게 선택하면 좋을까?

다음 표는 두 자료구조의 핵심 차이를 정리한 것이다.

경우	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간 삽입/삭제	O(N)	O(1)
데이터 추가	새로운 메모리 재할당 필요	뒤에 노드 추가로 충분
특징	접근이 빠르고 캐시 효율이 좋음	삽입/삭제가 빠르고 크기 유연

🔎 어떤 상황에서 어떤 구조를 쓰면 좋을까?

• 조회가 많다 → Array

• 중간 삽입/삭제가 많다 → LinkedList

• 메모리 연속성 혹은 캐시 효율이 중요하다 → Array

• 데이터 크기가 유동적으로 늘어난다 → LinkedList