배열과 연결 리스트는 값을 끼워 넣을 때 무엇이 다를까?

주문 네 건이 접수 순서대로 놓여 있다. 두 번째와 세 번째 주문 사이에 빠졌던 주문 한 건을 넣어야 한다. 겉으로는 목록 한 칸만 바꾸는 일처럼 보인다. 컴퓨터 안에서는 어디를 얼마나 고쳐야 할까?

배열(array)은 같은 크기의 칸을 연속해서 두고 번호로 원하는 칸을 찾는 자료구조다. 연결 리스트(linked list)는 각 항목이 다음 항목의 위치를 가리키도록 이어 놓은 자료구조다. 둘 다 순서가 있는 목록을 나타낼 수 있지만, 원하는 항목에 도달하는 방식과 중간에 값을 넣는 방식이 다르다.

배열은 뒤쪽 값을 밀어 자리를 만든다

배열에 [10, 20, 30, 40]이 들어 있다고 하자. 20 뒤에 25를 넣고 기존 순서를 지키려면 30과 40을 한 칸씩 뒤로 옮긴다. 새 자리가 생긴 뒤 그곳에 25를 쓴다.

처음    [10, 20, 30, 40, _]
이동 뒤 [10, 20, _, 30, 40]
삽입 뒤 [10, 20, 25, 30, 40]

배열은 첫 칸의 위치와 각 칸의 크기를 알면 원하는 번호의 위치를 바로 계산할 수 있다. 100번째 값을 읽기 위해 1번째부터 99번째까지 훑을 필요는 없다. 반면 맨 앞에 값을 넣으면 기존 값을 거의 모두 옮겨야 한다. 목록이 길수록 이동량이 늘어난다.

크기가 늘어나는 동적 배열(dynamic array)은 현재 길이보다 넉넉한 저장 공간을 미리 확보할 수 있다. 남은 칸이 있으면 끝에 붙이는 작업은 빠르다. 공간이 가득 차면 더 큰 공간을 마련해 기존 값을 옮겨야 한다. 끝에 붙이는 작업이 항상 같은 시간에 끝난다는 뜻은 아니다.

연결 리스트는 다음 항목을 가리키는 곳을 바꾼다

단일 연결 리스트(singly linked list)는 각 항목이 값과 다음 항목을 가리키는 연결 하나를 가진 형태다. 항목 20의 위치를 이미 알고 있다면 새 항목 25가 기존의 30을 가리키게 만들고, 20이 25를 가리키도록 바꾼다. 30과 40의 값을 옮길 필요는 없다.

처음    [10] → [20] → [30] → [40]
새 연결 [10] → [20] → [25] → [30] → [40]

‘연결 리스트는 중간 삽입이 빠르다’는 말에는 조건이 있다. 넣을 위치의 앞 항목을 이미 알고 있어야 한다. 번호만 듣고 ‘100번째 뒤에 넣어 달라’고 하면 첫 항목부터 연결을 따라 100번째를 찾아가야 한다. 찾는 데 걸린 시간까지 포함하면 목록 길이에 따라 일이 늘어난다.

연결을 바꾸는 순서도 중요하다. 25가 먼저 30을 가리키게 한 뒤 20이 25를 가리키도록 하면 원래의 뒤쪽 목록을 잃지 않는다. 20의 연결을 무턱대고 끊고 나서 30의 위치를 기억하지 못했다면 뒤쪽 항목에 다시 닿지 못할 수 있다.

번호로 읽는 일은 왜 다를까

배열에서 인덱스(index)는 첫 칸을 0으로 놓고 항목의 위치를 세는 번호다. 배열의 100번째 위치는 첫 위치와 칸 크기로 계산한다. 연결 리스트는 100번째 항목을 찾으려면 1번째부터 다음 연결을 반복해서 읽는다. 어떤 항목이 다음에 있는지 현재 항목을 읽기 전에는 알 수 없기 때문이다.

배열의 연속된 칸은 순서대로 훑을 때 주변 값이 같은 메모리 영역에 들어오기 쉽다. 연결 리스트의 항목은 메모리 곳곳에 흩어질 수 있다. 연결만 바꾸는 작업 수가 적어도, 실제 실행에서는 값을 찾느라 이동하고 메모리에서 항목을 읽어 오는 시간이 커질 수 있다.

하려는 일	배열	단일 연결 리스트
번호로 한 항목 읽기	위치를 계산함	앞에서부터 연결을 따라감
위치를 이미 아는 중간 삽입	뒤 항목을 옮김	앞 항목과 새 항목의 연결을 바꿈
번호만 아는 중간 삽입	뒤 항목을 옮김	그 번호의 앞 항목부터 찾음
순서대로 훑기	연속된 칸을 읽기 쉬움	다음 항목의 위치를 차례로 읽음

어느 구조가 무조건 낫다고 고르기보다 실제 요청을 먼저 살펴보면 된다. 번호로 자주 읽고 순서대로 훑는 목록이라면 배열이 편하다. 이미 가지고 있는 항목의 앞뒤 연결을 자주 바꾼다면 연결 리스트가 맞을 수 있다. 다만 위치를 찾는 일이 대부분이면 연결을 바꾸는 비용만 비교해서는 안 된다.

참고 자료

• Open Data Structures: 배열 기반 목록과 연결 리스트
• Python 문서: 기본 자료형 연산의 시간 복잡도