자료구조 - 배열(Array) vs 연결 리스트(Linked List)

1. 자료구조를 배우는 이유 (냉장고 정리의 법칙)

개발자가 하는 일은 요리사와 비슷하다고 보면 된다.

• 알고리즘: 요리 레시피 (어떻게 조리를 할 것인가?)
• 자료구조: 냉장고 정리법 (재료를 어디에다가 어떻게 보관할 것인가?)

아무리 칼질(알고리즘)을 잘해도, 냉장고가 엉망이라 파 하나를 찾는데에 10분 이상이 걸리면 그 요리는 망한다.

반대로 재료를 넣고 꺼내기 좋은 위치에 정리를 해두면(자료구조), 그 요리의 속도는 매우 빨라져 효율적으로 요리를 할 수 있다.

 

코딩테스트 레벨 3, 4의 문제는 이런 상황을 제시한다고 한다.

데이터가 100만 개가 쏟아질 때, 1초 안에 가장 큰 숫자를 찾으시오.

 

그냥 아무 데나 마구잡이로 넣어두면, 찾는 데에는 1시간이 걸리지만, 특정한 형태로 정리를 해두면 0.1초만에 찾을 수 있는 이 방식을 배우는 것이 목표다.

---

2. 컴퓨터의 땅, 메모리(RAM) 이해하기

자료구조를 이해하려면 RAM(메모리)이라는 땅을 먼저 이해해야 한다. 컴퓨터는 아주 멍청해서 아주 정직한 규칙만을 따른다.

• 메모리는 거대한 모눈종이(엑셀 시트)다.
• 각 칸(셀)에는 고유 번호(주소)가 붙어있다.
• 데이터는 이 칸에 한 칸씩 들어간다.

이 모눈종이 위에 데이터를 올리는 가장 기초적인 두 가지 방법이 있다. 이 두가지만 완벽하게 이해하면 자료구조의 50%는 이해했다고 볼 수 있다.

---

3. 배열(Array) vs 연결 리스트(Linked List)

데이터 3개(A, B, C)를 저장한다고 가정해보자.

 

(1) 배열(Array) : "우리는 깐부잖아, 딱 붙어 있자!"

배열은 데이터를 연속된 빈칸에 다닥다닥 붙여서 저장한다.

• 특징: A가 100번지 주소에 저장되어 있다면, B는 무조건 101번지, C는 102번지에 존재한다.
• 장점 (조회 속도 최강)
  • 컴퓨터에게 "야, 3번째 놈 가져와!"라고 하면, 컴퓨터는 계산 한 번에(시작 주소 + 2칸) 바로 찾아간다. (엄청나게 빠르다.)
• 단점 (이사 가기 힘듦)
  • 만약 A와 B 사이에 Z를 끼워 넣고 싶다면?
  • B랑 C가 한 칸씩 뒤로 비켜줘야 한다. 데이터가 100만 개라면 100만 번의 이동이 일어난다. (최악)
  • 처음에 3칸만 빌렸는데 데이터가 4개가 되면? 자리가 없어서 더 큰 사이즈의 땅을 찾아 이사 가야한다.

(2) 연결 리스트 (Linked List): "보물찾기 쪽지"

연결 리스트는 데이터를 메모리 아무 곳에나 흩뿌려 놓는다. 대신에 다음 데이터가 어디 있는지 쪽지(주소)를 함께 저장한다.

• 특징: A(다음은 500번지에) ... (저 멀리 500번지에) B (다음은 12번지에) ... (12번지에) C(끝)
• 장점 (수정 속도 최강)
  • A와 B 사이에 Z를 넣고 싶으면?
  • A가 들고 있던 쪽지만 Z를 가리키게 바꾸면 끝. 데이터가 100만 개여도 딱 한 번만 작업하면 된다.
• 단점 (조회 속도 최악)
  • "3번째 놈 가져와!"라고 하면? 한 번에 못찾는다.
  • A가서 쪽지 보고, B가서 쪽지 보고, C를 찾아야 한다. (보물찾기처럼 처음부터 다 뒤져야 함)