어떻게 줄 세워 담기, 배열과 리스트

붙어 있는 사물함, 배열

앞 레슨에서 그릇마다 모양이 다르다는 것을 보았다. 그 가운데 가장 단순한 모양이 배열이다. 번호가 붙은 칸들을 한 줄로 딱 붙여 놓은 사물함이라고 생각하면 된다.
칸 번호는 0번, 1번, 2번처럼 보통 0부터 매긴다. 칸이 모두 같은 크기로 붙어 있어서, 시작 위치에 번호만큼 칸 크기를 더하면 그 칸이 어디 있는지 바로 계산돼요.

번호를 눌러 그 칸으로 바로 건너가 보자. 칸들이 붙어 있어서 번호로 곧장 찾아요.

번호를 누르자 곧바로 그 칸이 빛났다. 칸들이 나란히 붙어 있으니 몇 번 칸이든 단번에 짚는다. 칸이 열 개든 백만 개든 걸리는 시간이 같다.
이렇게 번호로 바로 꺼내는 것을 빠른 접근이라고 하며, 배열의 가장 큰 장점이에요. 그런데 칸을 꼭 붙여 두어야만 할까? 흩어 두면 어떻게 될까?

흩어진 사물함, 리스트

리스트는 칸을 붙여 두지 않는다. 칸들이 메모리 여기저기에 흩어져 있다. 그렇다면 순서는 어떻게 이을까? 칸마다 쪽지를 한 장씩 붙이고, 그 쪽지에 다음 칸이 있는 위치를 적어 둔다.
그래서 첫 칸에서 쪽지를 보고 다음 칸으로, 또 그 쪽지를 보고 그다음 칸으로 따라간다. 칸들이 쪽지로 줄줄이 이어져 있어서 이런 모양을 연결 리스트라고 불러요.

쪽지를 눌러 다음 칸으로 따라가 보자. 칸은 흩어져 있어도 쪽지가 순서를 이어 줘요.

쪽지를 따라가니 흩어진 칸들이 한 줄로 이어졌다. 번호로 바로 건너가는 배열과 달리, 리스트는 쪽지를 읽으며 한 칸씩 차례로 가야 한다.
조금 번거로워 보이지만 이렇게 흩어진 구조에는 뜻밖의 장점이 있어요. 그것이 무엇인지는 곧 보게 된다.

빠른 접근 vs 느린 접근

이제 둘을 견주어 보자. 5번째 칸을 꺼내고 싶다고 하자. 배열은 번호만 대면 끝난다. 칸이 붙어 있으니 단번에 건너간다.
리스트는 그렇게 할 수 없다. 첫 칸부터 쪽지를 따라 한 칸, 두 칸, 세 칸 차례로 세며 가야 해요. 그래서 찾는 칸이 멀수록 더 오래 걸린다.

5번째를 꺼내 보자. 배열은 한 번에, 리스트는 처음부터 한 칸씩 간다. 누른 횟수를 견주어 봐요.

차이가 또렷하다. 배열은 한 번 눌러 바로 도착했지만, 리스트는 여러 번 눌러서야 겨우 닿았다. 꺼내는 일에서는 번호로 바로 가는 배열이 훨씬 빠르다.
그렇다면 배열이 언제나 더 좋을까? 그렇지 않아요. 다음 장면에서 리스트가 빛나는 순간이 온다. 중간에 무언가를 끼워 넣을 때다.

중간에 끼워 넣기

이번에는 줄 한가운데에 새 칸을 끼워 넣어 보자. 리스트에서는 아주 쉽다. 앞 칸의 쪽지가 새 칸을 가리키도록 고치고, 새 칸의 쪽지가 원래 다음 칸을 가리키게 하면 된다.
쪽지 두 장만 고쳐 쓰면 나머지 칸은 손대지 않아도 돼요. 칸이 백만 개라도 고치는 쪽지는 두 장뿐이다.

가운데에 새 칸을 끼워 보자. 리스트는 쪽지 두 장만 고치고, 배열은 뒤 칸을 모두 민다. 손이 얼마나 가는지 견주어 봐요.

배열은 어땠을까? 중간에 자리를 내려면 뒤에 있는 칸을 하나씩 모두 밀어야 했다. 칸이 붙어 있어서 빈자리가 없기 때문이다. 리스트는 쪽지 두 장으로 끝났다.
그래서 중간에 자주 끼워 넣는 일에는 리스트가 훨씬 편해요. 빠른 접근은 배열, 쉬운 끼워 넣기는 리스트. 하나를 얻으면 하나를 내주는 사이인 셈이다.

정리

한 줄로 모으면 이렇다. 배열은 번호가 붙은 칸을 딱 붙여 놓은 사물함이라 번호로 바로 꺼낼 수 있다. 리스트는 흩어진 칸에 다음 칸의 위치를 적은 쪽지를 단 것이라 중간에 끼워 넣기가 쉽다.
5번째를 꺼낼 때는 배열이 빠르고, 중간에 끼울 때는 리스트가 편해요. 무엇을 자주 하느냐에 따라 고르면 된다.

핵심을 차례로 눌러 되짚어 보자. (붙은 사물함 배열 → 흩어진 사물함 리스트 → 빠른 접근 vs 느린 접근 → 중간 삽입)

이제 같은 물건이라도 어떻게 담느냐에 따라 잘하는 일이 달라진다는 것을 알았다. 배열과 리스트는 그릇의 모양을 고르는 첫 갈림길이다.
다음 레슨에서는 한쪽 끝에서만 넣고 빼거나 줄을 선 차례대로만 꺼내는 특별한 그릇, 스택과 큐를 다뤄요.