배열과 리스트, 도대체 너희들은 뭐가 다른 거야?

배열이나 리스트를 이용해서 데이터들을 묶음으로 관리하면, 동일한 특성의 데이터들을 한데 모아 처리할 수 있는 장점이 있다. 또한, 숫자로 된 인덱스를 이용해서 한 묶음내의 모든 데이터에 간편하게 접근할 수 있다. 이것은 Loop 명령문 타일의 index 변수를 그대로 사용해서 Loop 명령문 타일 내에 배치한 한 개의 명령문 타일만으로 묶음 내의 모든 데이터들을 접근할 수 있다는 것을 의미한다. 이렇게 배열과 리스트는 그 사용법에서 매우 유사점을 가지고 있다.

 

한편, 리스트의 경우 그 크기를 프로그램 실행 중에 자유자재로 변경할 수 있다는 점에서 배열보다 유연하고, 제공하는 메서드와 함수들도 매우 다양해서 프로그래머가 사용하기에 매우 편리하다. 그렇다면, 배열의 존재 이유는 무엇일까? 이렇게 편리한 리스트만 있어도 충분한 것을, 굳이 배열이라는 자료구조가 있어야 할 이유는? 이것을 알게 되면, 배열과 리스트의 차이점도 자연스럽게 파악할 수 있다. 자! 이제 배열의 존재 이유를 자세히 살펴보자.

 

첫 번째, CPU의 처리 속도에서 배열이 리스트보다 훨씬 더 빠르다. 본 교재에서는 “내부적인 동작 방식” 때문이라고 설명하고 있지만, 그림 F-1과 그림 F-2를 살펴보면 그 원인을 확실하게 알 수 있다. 각각의 그림은 배열과 리스트의 논리적인 모양을 나타내고 있다.

 

그림 F-1 배열

 

그림 F-2 리스트

 

배열과 리스트의 사각형 박스는 데이터가 저장되는 공간이고, 그 공간에 현재 a, b, c, d, e 라는 데이터가 저장되어 있다. 각 박스마다 번호가 붙여 있다. 이 번호를 인덱스라고 생각하면 된다. 이때 3번째 위치, 즉, 인덱스 번호가 3인 데이터에 접근한다고 가정하자. 배열은 인덱스 번호 3을 이용하여 곧바로 그 위치의 데이터에 직접 접근할 수 있다. 그러나 리스트는 0번 위치의 데이터를 기점으로 3개의 화살표를 오른쪽으로 따라가야 비로소 3번 위치의 데이터에 도달할 수 있다. 여기서 리스트는 배열처럼 인덱스 번호를 이용하여 직접 접근할 수 없다는 것이다. 반드시 0번 위치부터 화살표를 따라가야 하며, 그때 따라간 화살표의 개수를 세야 한다. 당연히 배열 보다 느릴 수밖에 없다.

 

두 번째, 이들 자료 구조를 이용하여 해결하려고 하는 문제의 특성에 따라, 리스트와 배열의 유용성이 상당히 달라진다. 어떤 문제는 리스트를 사용하는 것이 더 좋고, 어떤 문제는 배열을 사용하는 것이 더 좋다. 이렇게 자료 구조의 유용성을 다르게 하는 문제의 특성이란 무엇일까? 바로 “데이터들의 묶음에서, 삽입 또는 삭제될 위치에 있는 데이터의 처리”에 있다. 그 위치의 처리 상황은 삽입과 삭제 시 각각 두 가지 경우가 있을 수 있다.

 

새로운 데이터의 삽입 시

 

- 삽입할 위치에 있던 기존의 데이터를 그냥 덮어 쓰는 경우

- 삽입 위치의 데이터와 그 이후의 데이터를 한 칸씩 뒤로 밀어서 삽입할 공간을 만들어야 하는 경우

 

기존 데이터의 삭제 시

 

- 삭제되고 남아 있는 공간을 그대로 두는 경우

- 삭제 위치 이후의 데이터들을 한 칸씩 앞으로 밀어서 삭제된 공간을 메워야 하는 경우

 

삽입과 삭제 시 전자에 해당하는 경우는 배열을, 후자에 해당하는 경우는 리스트를 사용하는 것이 프로그래밍을 하기에 편리하다.

 

예를 들어 보자. 알고리즘에 대한 대표적인 문제 2가지를 꼽는다면, 단연 “정렬(Sort)”과 “검색(Search)”이다. “정렬”이란 임의의 데이터들이 N개가 있을 때, 그 N개의 데이터들을 특정 순서(오름차순, 또는 내림차순)대로 나열하는 것이다. 그리고 “검색”이란 임의의 데이터들이 N개가 있을 때 찾고자 하는 데이터가 그 N개의 데이터들에 포함되어 있는지, 그리고 포함되어 있다면 어느 위치에 있는지를 알아내는 것이다.

 

이 2가지 문제 모두, 문제 해결 과정에서 N개의 데이터 이외에 새로운 데이터가 삽입되거나, 기존의 데이터가 삭제되는 경우는 전혀 일어나지 않는다. 정렬의 경우, 두 데이터의 교환 과정이 전체 데이터가 정렬될 때까지 반복되는데, 이 과정에서 기존 데이터들의 묶음에 새로운 데이터 삽입되거나 그 묶음에서 데이터가 삭제되는 경우는 없다. 그냥 그 묶음 속에 있던 두 데이터들이 서로의 위치만 교환되어 바뀔 뿐이다. 또한 두 데이터의 교환 과정에서 나머지 데이터들의 위치는 전혀 변화될 필요가 없다. 예를 들어, 10개의 데이터를 정렬한다고 하자. 그 정렬 과정에서 교환되는 데이터들이 2번째와 6번째라고 한다면, 이때(2번째 데이터와 6번째 데이터를 서로 교환될 때) 3번째, 4번째, 5번째 데이터의 위치는 변화될 필요가 없다. 또한 7번째, 8번째, 9번째 데이터들도 역시 그 위치는 변함이 없다. 이와 같은 경우는 리스트보다 배열을 사용하는 것이 프로그래밍 하기에 훨씬 편리하다.

 

그러나 7장의 추가 연습 문제 “11. 조세퍼스 문제”는 선택된 기사의 번호를 묶음에서 완전히 삭제하고, 그 이후의 데이터들이 삭제된 자리를 메워야 한다. 또한, “12. 줄 세우기”는 학생이 뽑은 번호대로 학생의 위치가 변동되는데, 그때, 앞에 있던 다른 학생들의 위치까지 한 칸씩 뒤로 이동되어야 한다. 이와 같은 문제들은 리스트를 사용하는 것이 훨씬 편리하다.

 

리스트와 배열의 차이점에 대해서 자세히 설명하였지만, 혹시 이해가 잘 되지 않는 독자가 있다면, 배열과 리스트를 각각 사용해서 7장 추가 연습 문제를 해결해 보라고 권하고 싶다. 특히, “11. 조세퍼스 문제”와 “12. 줄 세우기”를 추천한다. 배열과 리스트를 이용하여 이 문제들을 해결하다 보면, 문제의 특성에 대한 두 자료구조의 유용성을 확실하게 느낄 수 있다.