[CS/자료구조] 02. 배열(Array)과 리스트(List)

⚡ 한 줄 요약: 데이터가 메모리에 연속적으로 배치되느냐, 포인터로 연결되느냐에 따른 성능 차이를 이해하고 상황에 맞는 최적의 자료구조를 선택하는 방법을 배웁니다.

1. 👋 들어가며: 자료구조의 기초 체력 기르기

모든 자료구조의 시작은 결국 "데이터를 메모리에 어떻게 배치할 것인가?"에서 출발합니다.

개발을 하며 무심코 사용했던 Array 메서드들이 내부적으로 어떻게 동작하는지,
왜 어떤 작업은 빠르고 어떤 작업은 느린지 그 근본적인 이유를 파헤쳐 봅니다.

• 🧐 Why:

  • 하드웨어(캐시) 효율성과 시간 복잡도의 관계를 이해하여 성능 병목을 방지하고,
    CS 면접의 단골 질문인 "배열과 리스트의 차이"에 완벽히 대비하기 위함입니다.

• 🎯 Goal:

  • 배열의 물리적 특성(연속성), ArrayList의 동적 확장 원리, 연결 리스트의 노드 구조를
    명확히 구분하여 설명할 수 있습니다.

---

📂 2. 배열

배열은 같은 종류의 데이터를 연속된 메모리 공간에 저장하여 하드웨어 성능을 극대화하는 고정 크기 자료구조입니다.

📌 2-1. 핵심 개념

배열의 가장 큰 특징은 데이터가 메모리 상에서 연속된 위치에 나란히 저장된다는 점입니다.
단순히 "데이터가 붙어 있다"는 사실보다 중요한 것은, 이 구조가 컴퓨터의 캐시 메모리와 만났을 때 폭발적인 속도를 낸다는 것입니다.

• 연속된 메모리 배치와 캐시 효율성

  • 컴퓨터는 메인 메모리보다 훨씬 빠른 캐시 메모리를 사용합니다.
  • 배열은 모든 요소가 연속적으로 붙어 있기 때문에, CPU가 데이터를 처리할 때 한 번에 여러 데이터를 캐시에 불러오기가 훨씬 수월합니다.

• 지역성(Locality)의 원리

  • 예를 들어, 배열의 첫 번째 요소에 접근하면 컴퓨터는 "주변 데이터도 곧 쓰이겠구나"라고 판단하여 그 주변의 요소들도 함께 캐시에 적재합니다.
  • 덕분에 데이터를 순차적으로 읽는 연산이 많을수록 배열은 압도적인 속도를 낼 수 있습니다.

• 고정 크기의 제약

  • 배열은 선언 시 고정된 크기를 가집니다.
  • 이 때문에 정해진 크기를 초과하는 데이터를 중간에 삽입할 수도 없고, 크기 자체가 줄어들도록 데이터를 삭제하는 것도 불가능합니다.

• 값의 변경(대입)

  • 구조적인 삽입과 삭제는 불가능하지만, 이미 존재하는 인덱스에 새로운 값을 넣는 대입 연산은 자유롭게 가능합니다.

📌 2-3. 헷갈리기 쉬운 포인트 / 오해 정리

• 배열에서 '삽입'이 불가능하다는 말이 무슨 의미인가요?
  • 배열은 한 번 크기가 정해지면 물리적인 메모리 공간이 고정됩니다.
  • 따라서 길이를 늘려 새로운 칸을 만들거나(삽입), 칸 자체를 없애서 길이는 줄이는(삭제) 식의 구조적 변화가 안 된다는 뜻입니다.
  • 우리가 흔히 하는 삽입 작업은 사실 기존 배열의 값을 덮어쓰거나, 아예 새로운 배열을 만드는 방식으로 처리합니다.

📌 2-4. 한 줄 정리

배열은 연속된 메모리 배치를 통해 캐시 효율성을 극대화하며,
빠른 인덱스 접근을 보장하지만 크기 변경이 불가능한 자료구조입니다.

💻 참고

자바스크립트의 Array는 내부적으로 전통적인 배열(Typed Array)과 달리 해시 맵처럼 동작할 때가 많습니다.

하지만 성능 최적화가 필요한 대량의 데이터 처리나 그래픽스 연산 시에는 Int32Array 같은 Typed Array를 사용해 실제 연속된 메모리 공간을 확보함으로써 배열 본연의 캐시 성능을 끌어올리기도 합니다.

---

📂 3. 리스트 (1)

📌 3-1. ArrayList: 배열 기반 리스트의 동적 동작 원리

1. 초기 할당과 데이터 적재
   ArrayList를 처음 생성하면 시스템은 내부적으로 임의의 크기를 가진 배열을 메모리에 할당합니다.

   • 공간이 남았을 때

     • 리스트에 요소를 추가할 때 기존 배열에 빈 공간이 있다면, 해당 위치에 데이터를 즉시 적재하므로 매우 빠르게 추가가 완료됩니다.

   • 공간이 부족할 때(Dynamic Resizing)

     • 배열이 가득 찬 상태에서 데이터를 추가하려 하면, 기존보다 더 큰 크기를 가진 새로운 배열을 생성합니다.
     • 예를 들어 크기가 4였던 배열이 꽉 찼다면, 크기가 8인 새 배열을 만든 뒤 기존 데이터를 모두 복사해오고 새 데이터를 추가하는 과정을 거칩니다.

2. 중간 삽입과 삭제의 비용
   ArrayList는 데이터의 연속성을 유지해야 하기 때문에 인덱스 중간에 데이터를 넣거나 뺄 때 '이동(Shifting)'의 비용이 발생합니다.

   • 중간 삽입

     • 만약 [10, 20, 30, 40, 50] 상태에서 20과 30 사이에서 새로운 값을 넣고 싶다면, 뒤에 있는 30, 40, 50을 각각 한 칸씩 오른쪽으로 밀어낸 뒤 자리를 만들어야 합니다.

   • 중간 삭제

     • 데이터를 삭제할 때도 빈자리를 채우기 위해 뒤에 있는 요소들을 앞으로 당겨야 합니다.
     • 이 과정 때문에 중간 삽입/삭제 연산은 $O(n)$의 시간 복잡도가 소요됩니다.

📌 3-2. 헷갈리기 쉬운 포인트 / 오해 정리

• 크기가 무한하다?

  • 아닙니다. ArrayList도 결국 내부적으로는 고정 크기 배열을 사용합니다.
  • 단지 공간이 부족할 때 우리가 모르게 더 큰 배열로 이사를 가는 과정을 반복하며 가변적인 것처럼 보일 뿐입니다.

• 이사(Resize)의 빈도

  • 매번 요소를 추가할 때마다 배열 크기를 키우면 성능이 매우 나빠지므로, 보통 기존 크기의 1.5배나 2배 정도로 넉넉하게 확장하여 '이사' 횟수를 최소화합니다.

📌 3-3. 한 줄 정리

• ArrayList는 인덱스 접근이 매우 빠르지만($O(1)$), 공간이 찰 때 발생하는 배열 복사와 중간 삽입/삭제 시의 데이터 이동($O(n)$) 비용을 고려해야 하는 자료구조입니다.

💻 참고

자바스크립트의 Array는 내부적으로 이 ArrayList와 유사한 동적 배열 방식으로 동작합니다.

실무에서 아주 큰 배열을 다룰 때 unshift()나 splice() 같은 메서드가 왜 push()보다 느린지 이해하고 있다면, 데이터가 많아질 때 발생할 수 있는 렌더링 병목 현상을 미리 방지할 수 있습니다.

---

📂 4. 리스트 (2)

📌 4-1. 연결 리스트(Linked List)의 구현 원리

연결 리스트는 각 데이터 요소인 노드(Node)가 포인터를 이용해 다음 요소와 연결되는 구조입니다.
배열처럼 메모리에 다닥다닥 붙어있지 않아도 되기 때문에 삽입과 삭제가 매우 자유롭다는 특징이 있습니다.

• 구현의 핵심, 노드(Node)

  • 노드는 저장할 값(val)과 다음 노드의 주소를 가리키는 포인터(next)로 구성됩니다.

• 삽입과 삭제 ($O(1)$)

  • 중간에 데이터를 추가할 때, 기존 요소들을 밀어낼 필요 없이 포인터가 가리키는 방향만 바꿔주면 끝납니다.

• 탐색 ($O(n)$)

  • 하지만 인덱스가 없기 때문에, 원하는 값을 찾으려면 Head(첫 노드)부터 하나씩 기차 놀이 하듯 찾아가야 해서 조회가 느립니다.

💡 비유로 이해하기

배열이 번호표가 붙은 좌석제 열차라면, 연결 리스트는 앞사람이 뒷사람의 손을 잡고 있는 '강강술래'와 같습니다.

중간에 누군가 새로 들어오려면 잡고 있던 손만 놓고 새 사람의 손을 잡으면 되지만,
10번째 사람을 찾으려면 첫 번째 사람부터 차례대로 세어가며 확인해야 합니다.

📌 4-2. 연결 리스트의 종류

상황에 따라 단방향 연결만으로는 부족할 때가 있습니다.
그래서 연결 리스트는 크게 세 가지 형태로 발전했습니다.

1. 단일 연결 리스트

   • 각 노드가 다음 노드만 가리키는 가장 기본적인 형태입니다.

2. 이중 연결 리스트

   • 각 노드가 이전(prev) 노드와 다음(next) 노드를 모두 가리킵니다.
   • 뒤로 돌아가는 탐색이 가능해져서 단일 연결 리스트보다 유연하지만, 메모리를 조금 더 사용합니다.

3. 원형 연결 리스트

   • 마지막 노드의 포인터가 None이 아니라 다시 첫 번째 노드(Head)를 가리키는 구조입니다.
   • 끝이 없이 순환하기 때문에 마지막 노드에서도 다음 노드로 자연스럽게 넘어갈 수 있습니다.

📌 4-3. 헷갈리기 쉬운 포인트 / 오해 정리

• 삭제는 무조건 $O(1)$인가요?

  • 엄밀히 말하면 '삭제 작업 자체'는 $O(1)$이지만, 삭제할 노드의 위치를 찾는 과정은 조회가 필요하므로 $O(n)$이 걸릴 수 있습니다.

• 메모리 효율

  • 연결 리스트는 배열과 달리 데이터를 담는 공간 외에 주소(포인터)를 담는 공간이 추가로 필요합니다.
  • 따라서 데이터가 아주 작은 경우라면 오히려 배열보다 메모리를 더 많이 쓸 수도 있습니다.

📌 4-4. 한 줄 정리

• 연결 리스트는 노드 간의 포인터 연결을 통해 삽입과 삭제를 최적화한 자료구조로, 탐색 효율보다 구조적 유연성이 필요할 때 사용합니다.

---

🎁 5. 정리

🔑 요약

특징	배열 (Array)	동적 배열 (Array List)	연결 리스트(Linked List)
메모리 배치	연속적	연속적	불연속적
사이즈	고정	동적	동적
인덱스 접근	$O(1)$ (매우 빠름)	$O(1)$ (매우 빠름)	$O(n)$ (순차 탐색 필요)
삽입/삭제	불가 (새 배열 필요)	$O(n)$ (데이터 이동 발생)	$O(1)$ (포인터 변경)
장점	캐시 효율성 최고	인덱스 접근 + 동적 크기	삽입/삭제의 유연성