목차
기차 한 편성을 떠올리면 두 그릇이 한눈에 갈린다. 좌석이 번호대로 붙은 한 량이냐, 객차를 고리로 이어 붙인 편성이냐다.
좌석 번호가 붙은 한 량
배열은 객차 한 량이다. 좌석이 1번부터 붙어 있고 간격이 일정하다. 그래서 15번 좌석이 어디인지 세어보지 않아도 안다. 입구에서 좌석 하나 너비를 열넷 곱한 자리다.
이게 배열이 가진 유일하고 결정적인 능력이다. 몇 번째든 계산 한 번으로 곧장 간다. 앞 글의 표기로는 O(1)이고, 데이터가 100만 개여도 그대로다.
연결리스트는 객차를 고리로 이은 편성이다. 각 객차는 다음 객차가 어디 있는지만 안다. 그래서 열다섯 번째 객차에 가려면 첫 칸부터 걸어가야 한다. 건너뛸 방법이 없다.
여기까지는 배열이 이긴다. 뒤집히는 건 다음 대목부터다.
중간에 한 칸 끼우기
3번과 4번 사이에 하나 끼워 넣는다고 하자.
자리가 곧 순서라, 뒤에 있던 세 칸이 전부 한 칸씩 밀려야 한다.
고리 두 개만 바뀐다. 움직인 칸은 하나도 없다.
같은 일을 시켰는데 위는 뒤가 전부 물들고, 아래는 물들 칸이 없다.
배열은 뒤를 전부 민다. 좌석 번호가 자리를 정하는 그릇이라, 새 자리를 만들려면 뒤에 앉은 사람이 모두 한 칸씩 옮겨야 한다. 앞쪽에 끼울수록 밀 사람이 많아진다. 맨 앞에 끼우면 전원이 움직인다.
연결리스트는 고리 두 개만 바꾼다. 3번 객차가 가리키는 곳을 새 객차로, 새 객차가 가리키는 곳을 4번으로. 나머지 객차는 자리에서 꿈쩍도 안 한다. 편성이 1,000량이어도 바꾸는 고리는 두 개다.
이게 두 그릇이 갈리는 자리다. 한쪽은 자리를 밀고, 한쪽은 고리를 바꾼다.
기차 비유가 깨지는 자리를 밝혀둔다. 실제 기차는 객차를 이어도 줄지어 서 있다. 하지만 연결리스트의 객차는 메모리 여기저기에 흩어져 있고, 고리는 물리적인 연결이 아니라 “다음은 저기”라고 적어둔 주소일 뿐이다. 이 차이가 뒤에서 실무 결론을 뒤집는다.
배열이 꽉 차면 이사한다
배열에는 비유에 없는 제약이 하나 더 있다. 크기를 미리 정하고 시작한다. 좌석 열 개짜리 객차에 열한 번째 손님이 오면 자리가 없다.
이때 벌어지는 일이 이사다.
두 배짜리 자리를 새로 얻고 있던 것을 전부 옮겨 적는다. 옛 자리는 반납한다(빗금).
칸 하나가 모자랐을 뿐인데 있던 것 전부가 이사한다. 대신 다음 네 번은 이사가 없다.
더 큰 자리를 새로 얻어 전부 옮겨 적고, 쓰던 자리를 반납한다. 여기서 두 배씩 키우는 게 보통이다. 열 칸이 차면 스무 칸으로, 그것도 차면 마흔 칸으로.
한 칸씩 늘리지 않고 두 배로 키우는 데는 이유가 있다. 한 칸씩 늘리면 넣을 때마다 매번 이사를 간다. 두 배로 키우면 이사 뒤에는 한동안 이사가 없다.
그런데도 뒤에 붙이기는 O(1)이라고 한다
이사가 전부를 옮기는 일인데 왜 “뒤에 붙이기는 O(1)”이라고 할까. 이 대목이 처음 보면 앞뒤가 안 맞는다.
세어보면 답이 나온다. 열여섯 칸까지 채우는 동안 이사는 1, 2, 4, 8칸을 옮겼다. 다 합쳐도 15번이고, 그동안 넣은 건 16개다. 하나당 한 번꼴이다.
그래서 어쩌다 한 번 크게 무는 값을 전체로 나눠 보면 결국 상수가 된다. 이걸 분할상환이라고 부르고, 표기할 때는 그냥 O(1)이라 쓴다. 다만 평평하게 싼 게 아니라 가끔 크게 튄다는 건 알고 있어야 한다. 응답 시간을 밀리초 단위로 보는 자리에서는 그 튐이 그래프에 그대로 찍힌다.
연결리스트는 이사하지 않는다
연결리스트는 이 문제가 아예 없다. 객차 하나가 필요하면 그때 하나 얻어서 고리에 건다. 미리 크기를 정할 일도, 꽉 차서 옮길 일도 없다.
대신 값을 다른 데서 낸다. 객차마다 다음 객차 주소를 적을 칸을 따로 들고 있어야 한다. 숫자 하나를 담자고 주소 칸을 하나 더 두는 셈이라, 같은 개수를 담아도 차지하는 공간이 더 크다.
그리고 객차를 하나 얻을 때마다 메모리를 얻어 오는 일이 벌어진다. 배열은 한 번에 크게 얻어두고 나눠 쓰지만, 연결리스트는 넣을 때마다 따로따로 얻는다.
그런데 왜 실무는 거의 배열인가
여기까지 보면 “중간에 자주 끼우면 연결리스트”라는 결론이 나올 것 같다. 그런데 실제로 재보면 배열이 이기는 경우가 압도적으로 많다. 이유는 빅오에 안 적히는 데 있다.
메모리는 한 번에 한 칸씩 읽히지 않는다. 덩어리째 읽혀 CPU 가까운 곳에 올라온다. 배열은 붙어 있으니 첫 칸을 읽는 순간 뒤따르는 것들이 같이 딸려 온다. 다음 칸을 볼 때는 이미 가까이 있다.
연결리스트는 객차가 흩어져 있어서 이게 안 된다. 고리를 따라갈 때마다 매번 새로 멀리 다녀온다. 한 걸음의 값이 배열보다 몇 배에서 몇십 배까지 비싸진다.
그래서 이런 역전이 생긴다. “중간 삽입 1,000번”에서 배열이 뒤를 다 밀고도 연결리스트보다 빠른 일이 흔하다. 미는 일은 붙어 있는 자리를 통째로 옮기는 것이라 기계가 잘하는 일이고, 고리를 따라가는 일은 기계가 가장 못하는 일이다.
지우기도 같은 이야기다
지우는 것은 끼우는 것의 거울상이라 규칙이 그대로 뒤집혀 적용된다. 배열은 뒤를 당겨서 구멍을 메우고, 연결리스트는 고리 하나를 건너뛰게 바꾼다.
다만 연결리스트에서 하나 더 짚을 게 있다. 지울 객차를 찾는 값은 별개다. 고리를 바꾸는 건 O(1)이지만, 그 객차까지 걸어가는 게 O(n)이다. “연결리스트는 삭제가 빠르다”는 말은 이미 그 자리에 서 있을 때만 참이다.
실무에서: 무엇을 쓰나
기본값은 배열 쪽이다. ArrayList·List·vector·파이썬 list가 전부 배열로 되어 있고, 대부분의 상황에서 가장 무난하다. 고민하지 않고 이걸 쓰는 게 대개 옳다.
연결리스트가 값을 하는 자리는 좁고 분명하다.
- 양 끝에서만 넣고 뺀다. 이건 다음 글에서 볼 큐와 덱의 모양이다. 걸어갈 일이 없으니 연결리스트의 약점이 안 드러난다.
- 이미 그 자리를 들고 있다. 순회하면서 지우는 경우처럼, 찾는 값을 이미 치렀을 때다.
- 원소가 아주 크고 옮기는 값이 비싸다. 미는 일 자체가 비쌀 때다.
그리고 실무에서 자주 만나는 건 이 둘의 조합이다. 자바 HashMap은 배열 위에 얹혀 있으면서 한 칸에 여럿이 몰리면 그 안을 연결로 잇는다. 어느 하나가 이기는 게 아니라 자리마다 골라 쓴다.
정리
- 배열은 간격이 일정해서 몇 번째든 계산 한 번으로 간다. 연결리스트는 첫 칸부터 걸어가야 한다.
- 중간에 끼울 때 배열은 뒤를 전부 밀고, 연결리스트는 고리 둘만 바꾼다.
- 배열은 꽉 차면 두 배로 이사한다. 어쩌다 크게 무는 값을 나눠 보면 상수지만, 가끔 크게 튄다.
- 그런데도 실무는 거의 배열이다. 붙어 있는 것이 덩어리째 읽히기 때문이고, 이건 빅오에 안 적힌다.
- 연결리스트는 양 끝만 다룰 때 제 몫을 한다.
다음 글이 바로 그 “양 끝만 다루는” 그릇이다. 같은 더미를 놓고 위에서 꺼내느냐 아래에서 꺼내느냐만 바꿨을 뿐인데 쓰임이 전혀 달라진다.