한빛출판네트워크

때로는 여러 항목을 목록으로 메모리에 저장해야 할 때가 있습니다. 예를 들어, 해야 할 일 목록을 관리하는 앱을 만들고 있다고 가정해 볼게요. 그러면 이 할 일들을 메모리 안에 목록으로 저장해야 하겠죠?.

이때 배열을 사용해야 할까요? 아니면 연결 리스트를 사용해야 할까요? 일단 배열이 더 이해하기 쉬우니까 배열을 사용해서 할 일 목록을 저장해 보겠습니다. 배열을 사용하면 할 일들을 메모리에 차례대로 붙여서 저장합니다.

이제 네 번째 할 일을 추가하고 싶어졌다고 가정해 볼게요. 그런데 다음 칸을 벌써 누군가가 차지하고 있습니다!

이 상황은 마치 친구들과 영화를 보러 극장에 가서 앉을 자리를 찾는 경우와 비슷합니다. 극장에서 또 다른 친구를 만나기로 했는데 이미 우리 옆자리는 다른 사람이 앉아 있기 때문에 그 친구와 같이 앉을 수가 없습니다. 이런 경우에는 컴퓨터에 4개 자리가 있는 다른 메모리 공간을 요청합니다. 그리고 4개 할 일을 모두 그 자리로 옮겨야 하죠.

만약 또 다른 친구가 온다면 다시 자리가 모자라니까 또 전원이 같이 자리를 옮겨야 합니다. 힘들겠죠? 마찬가지로 배열에 새 원소를 추가하는 일은 쉽지 않은 일입니다. 만약 공간이 모자라서 매번 모든 원소를 메모리의 새로운 위치로 옮긴다면 배열에 원소를 추가하는 작업은 아주 느려지죠. 

이를 고칠 수 있는 쉬운 방법 중 하나는 좌석을 미리 예약하는 거예요. 지금은 할 일 목록에 할 일이 3개밖에 없어도 만약을 대비해서 컴퓨터에 자리를 10개 요청하는 겁니다. 그러면 전체 배열을 옮기지 않아도 10개까지는 할 일을 추가할 수 있습니다. 이 방법은 좋은 해결책이지만 몇 가지 단점이 있습니다.

• 만약 추가할 일이 생기지 않는다면 메모리를 쓸데없이 낭비한 게 됩니다. 우리가 그 자리를 사용하지 않지만 다른 어느 누구도 사용할 수 없으니까요. 
• 만약 목록의 크기가 10개보다 커진다면 어차피 자리를 옮겨야 합니다.

그러니까 좋은 해결책이기는 해도 완벽한 해결책은 아니라는 겁니다. 연결 리스트를 사용하면 원소를 추가할 때 생기는 이런 문제를 해결할 수 있습니다.

✅연결 리스트

연결 리스트^{linked list}를 사용하면 원소를 메모리의 어느 곳에나 둘 수 있습니다.

각 원소에는 목록의 다음 원소에 대한 주소가 저장되어 있습니다. 그러니까 여러 임의의 메모리 주소들이 하나의 목록으로 연결된 거죠.

이는 마치 보물찾기와 비슷합니다.  첫 번째 주소로 가면 그곳에 이렇게 적혀 있습니다. ‘다음 보물은 주소 123에 있습니다.’ 그래서 주소 123으로 가면 거기에는 또 이렇게 적혀 있죠. ‘다음 보물은 주소 847에 있습니다.’ 이런 식으로요. 연결 리스트를 사용하면 원소를 추가하는 일이 쉽습니다. 그냥 메모리 아무 곳에나 원소를 넣고, 그 주소를 바로 앞의 원소에 저장해 놓으면 됩니다.

연결 리스트를 사용하면 원소를 옮길 일이 없습니다. 예를 들어, 다음과 같은 문제가 발생하지 않아요. 우리가 친구 5명과 함께 인기 있는 영화를 보러 극장에 갔는데, 극장이 꽉 차서 6명이 같이 볼 수 있는 자리가 없습니다. 배열을 사용한다면 이 상황은 문제가 되죠. 

예를 들어 10,000개 자리가 있는 배열을 만들어야 하는데, 메모리에 10,000개 공간이 있기는 하지만 10,000개가 모두 이어진 자리는 없을 수도 있습니다. 그러면 배열을 만들 수 없습니다! 하지만 연결 리스트를 사용한다면 이렇게 이야기하는 것과 마찬가지입니다. “일단 흩어져서 영화를 보자.” 그러니까 배열을 만들 공간은 없어도, 연결 리스트를 만들 공간은 있는 것입니다. 

이렇게 원소를 추가하기에는 연결 리스트가 좋다면, 배열이 연결 리스트보다 나은 점은 뭘까요?

✅배열

인기 순위 10개를 보여 주는 웹 사이트가 있을 때, 이 웹 사이트는 페이지 뷰를 늘리기 위해 다음과 같은 비열한 방법을 쓸 수도 있습니다. 한 페이지에 10개를 모두 보여 주는 것이 아니라, 한 페이지에 하나만 보여 주고 ‘다음’ 버튼을 클릭해야만 다음 순위를 보여 주는 거죠. 

예를 들어 영화 속 최고의 악당 10명을 보여 주는 사이트에서 10명을 한 페이지에 모두 보여 주지 않는 겁니다. 대신 10위 악당부터 시작해서 계속 ‘다음’ 버튼을 눌러야만 1위 악당까지 볼 수 있습니다. 이 방법은 광고할 수 있는 페이지를 10개로 늘리는 대신 보는 사람은 1위에 도달할 때까지 지루하게 ‘다음’ 버튼을 누르고 있어야 합니다. 만약 모든 악당 목록을 한 페이지에 보여 주고, 각 악당의 이름을 클릭할 때마다 자세한 정보를 알려 준다면 훨씬 나을 겁니다. 

연결 리스트도 비슷한 문제가 있습니다. 만약 연결 리스트에서 마지막 원소를 보고 싶어도 바로 읽을 수 없습니다. 왜냐하면 그 주소를 바로 알 수 없으니까요. 대신에 2번 원소의 주소가적힌 1번 원소의 주소로 가야 합니다. 그런 다음 2번 원소의 주소를 알아내어 3번 원소의 주소가 적힌 2번 원소의 주소로 갑니다. 이런 식으로 마지막 원소의 위치까지 가야 합니다. 만약 모든 원소의 값을 한 번에 읽어야 한다면 연결 리스트가 좋지만, 특정한 원소만 알고 싶다면 연결 리스트는 최악입니다. 

배열^array은 다르죠. 배열에서는 모든 원소의 주소를 다 알고 있습니다. 예를 들어 배열에 다음과 같이 5개의 원소가 있고, 주소가 00부터 시작한다면 5번째 원소의 주소는 어디일까요?

간단한 산수로 계산할 수 있습니다. 답은 04입니다. 배열은 배열 안 어떤 원소든 바로 찾을 수 있기 때문에 임의의 원소의 값을 읽는 데 최고입니다. 연결 리스트에서는 원소가 이웃하고 있지 않아서 몇 번째 원소가 어디에 있는지 바로 계산할 수 없습니다. 두 번째 원소의 주소를 알려면 첫 번째 원소로 가야 하고, 세 번째 원소의 주소를 알려면 두 번째 원소로 가야 합니다. 원하는 원소에 도착할 때까지 이것을 반복해야 합니다.

✅배열과 연결 리스트 중 더 자주 쓰는 것은?

✔️리스트의 가운데에 삽입하기

만약 할 일 목록이 달력과 같아서 실제 해야 할 순서대로 할 일을 삽입해야 한다고 가정해 볼게요.

원소를 배열이나 리스트의 중간에 삽입한다면 배열과 리스트 중 어느 것이 나을까요? 리스트는 이전 원소가 무엇을 가리키는지만 바꾸면 되므로 리스트에 삽입하는 것이 훨씬 쉽습니다.

하지만 배열에서는 다음에 오는 모든 원소의 위치를 바꾸어야 하죠.

만약 공간이 부족하면 모든 원소를 새로운 장소로 복사해야 합니다! 그래서 중간에 원소를 삽입하려면 리스트가 훨씬 낫습니다.

✔️삭제하기

만약 원소를 삭제하고 싶을 때는 어떨까요? 이 경우에도 이전 원소가 가리키는 위치만 바꾸면 되기 때문에 리스트가 더 낫습니다. 배열에서는 원소 하나만 삭제하고 싶을 때도 모든 것을 다옮겨야 합니다. 

삽입할 때와 달리 삭제할 때는 실패하는 경우가 없습니다. 삽입할 때는 가끔 메모리에 남아 있는 공간이 없어서 실패할 수도 있습니다. 하지만 원소를 삭제하는 것은 언제나 할 수 있죠. 

✔️배열과 연결 리스트 중 더 자주 쓰는 것은?

배열이 연결 리스트보다 장점이 많아서 배열을 쓰는 경우가 더 많습니다. 무엇보다 배열은 임의의 위치에 있는 원소를 읽을 수 있는 임의 접근^{random access}이 가능합니다.

자료에 접근하는 방식에는 임의 접근과 순차 접근이라는 두 가지 방식이 있습니다. 순차 접근^{sequential access}은 원소를 첫 번째부터 하나씩 읽는 것을 뜻합니다. 연결 리스트는 순차 접근밖에 할 수 없습니다. 만약 연결 리스트에 있는 10번째 원소를 읽으려면 그 앞의 9개 원소를 모두 읽어서 10번째 원소로 가는 링크를 찾아내야 합니다. 반면에 임의 접근은 10번째 원소로 바로 건너뛸 수 있습니다. 배열에서는 임의 접근이 가능합니다. 임의 접근이 필요한 경우가 많다 보니 배열을 사용하는 경우가 많은 겁니다.

배열에서는 임의 접근 말고도 캐싱을 사용할 수 있어서 더 빠릅니다. 아마도 다음 그림처럼 한 번에 하나씩 원소를 읽을 거라고 생각하겠죠?

그러나 실제로 컴퓨터는 속도를 빠르게 하려고 다음처럼 전체를 한꺼번에 읽습니다.

배열에서는 이렇게 전체 원소를 한 번에 읽는 것이 가능합니다. 하지만 연결 리스트에서는 불가능하죠! 다음 원소가 어디에 있는지 모르니까요. 다음 원소의 위치를 알기 위해서는 일단 그 앞의 원소를 읽어야만 합니다. 

그래서 배열은 임의 접근이 가능할 뿐 아니라 순차 접근도 더 빠릅니다!

읽기 속도는 배열이 더 낫다고 했습니다. 그러면 메모리 효율성은 어떨까요? 앞에서 배열을 사용할 때 보통은 당장 필요한 것보다 많은 메모리를 요구한다고 했죠. 이렇게 더 많이 요구되는 메모리는 그냥 낭비되는 걸까요?

사실은 이렇게 낭비되는 공간이 연결 리스트보다 많지 않습니다. 연결 리스트를 사용하면 다음 원소의 주소를 저장해야 하기 때문에 모든 원소에서 메모리를 추가로 사용하게 됩니다. 따라서 연결 리스트에서는 각 원소의 크기가 매우 작은 경우 배열보다 더 많은 공간을 차지합니다. 다음은 같은 정보를 배열과 연결 리스트로 나타낸 것입니다. 연결 리스트가 배열보다 더 많은 공간을 차지하는 것을 볼 수 있습니다.

물론 원소 하나하나의 크기가 크다면 포인터를 저장하는 데 사용하는 추가 메모리는 상대적으로 매우 작게 느껴질 수 있습니다. 이러한 이유로 특정한 경우를 제외하고는 연결 리스트보다 배열을 더 자주 사용합니다.

위 콘텐츠는 『그로킹 알고리즘(개정판)』을 재구성하여 작성되었습니다.