4.5 요약¶
1. 핵심 정리¶
- 배열과 연결 리스트는 두 가지 기본 자료 구조로, 컴퓨터 메모리에 데이터를 저장하는 연속 공간 저장과 분산 공간 저장을 각각 대표한다. 둘의 특징은 서로 보완적이다.
- 배열은 임의 접근을 지원하고 메모리 사용량이 적다. 그러나 원소 삽입과 삭제의 효율이 낮으며 초기화한 뒤 길이를 바꿀 수 없다.
- 연결 리스트는 참조(포인터)를 바꾸어 노드를 효율적으로 삽입하고 삭제하며, 길이도 유연하게 조절할 수 있다. 하지만 노드 접근 효율이 낮고 메모리를 더 많이 사용한다. 대표적인 종류에는 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다.
- 리스트는 삽입, 삭제, 탐색, 갱신을 지원하는 순서 있는 원소의 모음으로, 보통 동적 배열로 구현한다. 배열의 장점을 유지하면서 길이를 유연하게 조절할 수 있다.
- 리스트의 등장으로 배열의 실용성이 크게 높아졌지만, 메모리 공간 일부가 낭비될 수 있다.
- 프로그램이 실행될 때 데이터는 주로 메모리에 저장된다. 배열은 메모리 공간 효율이 더 높고, 연결 리스트는 메모리를 더 유연하게 사용한다.
- 캐시는 캐시 라인, 프리페치, 공간 지역성, 시간 지역성 등의 로딩 방식을 통해 CPU에 빠른 데이터 접근을 제공하여 프로그램 실행 효율을 크게 높인다.
- 배열은 캐시 적중률이 더 높으므로 보통 연결 리스트보다 효율적이다. 자료 구조를 선택할 때는 구체적인 요구와 상황에 맞춰야 한다.
2. Q & A¶
Q: 배열을 스택에 저장하는지 힙에 저장하는지에 따라 시간 효율과 공간 효율이 달라지는가?
스택에 저장한 배열도 힙에 저장한 배열도 연속된 메모리 공간에 있으므로, 데이터 연산 효율은 대체로 같다. 다만 스택과 힙의 특성 때문에 다음과 같은 차이가 생긴다.
- 할당 및 해제 효율: 스택은 비교적 작은 메모리 영역으로 컴파일러가 자동으로 할당한다. 힙은 더 크며 코드에서 동적으로 할당할 수 있고 단편화도 더 쉽게 발생한다. 따라서 힙의 할당 및 해제 연산은 보통 스택보다 느리다.
- 크기 제한: 스택 메모리는 비교적 작고 힙의 크기는 대개 사용 가능한 메모리에 의해 제한된다. 따라서 큰 배열을 저장하기에는 힙이 더 적합하다.
- 유연성: 스택에 저장하는 배열의 크기는 컴파일 시 정해야 하지만, 힙에 저장하는 배열의 크기는 실행 중에 동적으로 정할 수 있다.
Q: 배열은 원소의 자료형이 같아야 한다고 하는데, 연결 리스트에서는 왜 이를 강조하지 않는가?
연결 리스트는 참조(포인터)로 연결된 노드들로 이루어진다. 각 노드에는 int, double, string, object 등 서로 다른 자료형의 데이터를 저장할 수 있다.
반면 배열 원소는 자료형이 같아야 오프셋을 계산하여 해당 원소의 위치를 구할 수 있다. 예를 들어 배열에 int와 long이 함께 있으면 원소 하나가 각각 4바이트와 8바이트를 차지한다. ‘원소 길이’가 두 가지이므로 다음 식으로 오프셋을 계산할 수 없다.
Q: 노드 P를 삭제한 뒤 P.next를 None으로 설정해야 하는가?
P.next를 바꾸지 않아도 된다. 해당 연결 리스트에서는 머리 노드부터 꼬리 노드까지 순회해도 더 이상 P를 만나지 않는다. 즉, P는 이미 연결 리스트에서 삭제되었으므로 어디를 가리키든 이 연결 리스트에 영향을 주지 않는다.
자료 구조와 알고리즘 문제를 푸는 관점에서는 프로그램 논리가 올바르기만 하면 연결을 끊지 않아도 된다. 표준 라이브러리 관점에서는 연결을 끊는 편이 더 안전하고 논리도 명확하다. 연결을 끊지 않은 상태에서 삭제한 노드가 정상적으로 회수되지 않으면, 뒤따르는 노드의 메모리 회수에도 영향을 줄 수 있다.
Q: 연결 리스트의 삽입과 삭제는 시간 복잡도가 \(O(1)\)이라고 한다. 하지만 먼저 원소를 찾는 데 \(O(n)\)이 필요한데, 전체 시간 복잡도는 왜 \(O(n)\)이 아닌가?
원소를 먼저 찾고 삭제한다면 시간 복잡도는 실제로 \(O(n)\)이다. 다만 연결 리스트의 \(O(1)\) 삽입 및 삭제는 다른 응용에서 장점을 발휘한다. 예를 들어 덱은 연결 리스트로 구현하기에 적합하다. 머리 노드와 꼬리 노드를 항상 가리키는 포인터 변수를 유지하면 매번 삽입과 삭제를 \(O(1)\)에 수행할 수 있다.
Q: ‘연결 리스트의 정의와 저장 방식’ 그림에서 노드 포인터를 저장하는 연한 파란색 부분은 하나의 메모리 주소를 차지하는가? 아니면 노드 값과 반씩 차지하는가?
그 그림은 정성적인 설명이다. 정확한 크기는 구체적인 상황에 따라 분석해야 한다.
- 노드 값이 차지하는 공간은 자료형에 따라 다르다. 예를 들어
int,long,double, 인스턴스 객체 등이 있다. - 포인터 변수가 차지하는 메모리 크기는 운영체제와 컴파일 환경에 따라 정해지며, 대개 8바이트 또는 4바이트다.
Q: 리스트 끝에 원소를 추가하는 연산은 항상 \(O(1)\)인가?
원소를 추가할 때 리스트의 길이를 넘으면 먼저 용량을 늘려야 한다. 시스템이 새 메모리 영역을 요청하고 기존 원소 전체를 옮기므로, 이때의 시간 복잡도는 \(O(n)\)이다.
Q: ‘리스트는 배열의 실용성을 크게 높였지만 메모리 공간 일부를 낭비할 수 있다’는 설명에서, 공간 낭비는 용량, 길이, 확장 배수 같은 추가 변수의 메모리를 뜻하는가?
여기서 공간 낭비는 주로 두 가지를 뜻한다. 하나는 리스트에 초기 길이를 설정하지만 그만큼 필요하지 않을 수 있다는 것이다. 다른 하나는 잦은 확장을 피하려고 보통 \(\times 1.5\)처럼 일정한 계수를 곱해 용량을 늘린다는 것이다. 이때도 빈자리가 많이 생기며, 보통 이를 전부 채우지는 못한다.
Q: Python에서 n = [1, 2, 3]을 초기화하면 세 원소의 주소가 이어져 있다. 하지만 m = [2, 1, 3]을 초기화하면 원소들의 id가 연속적이지 않고 n의 같은 값과 각각 일치한다. 주소가 연속적이지 않아도 m은 배열인가?
리스트 원소를 연결 리스트 노드로 바꾸어 n = [n1, n2, n3, n4, n5]라고 하면, 이 다섯 노드 객체도 보통 메모리 곳곳에 흩어져 있다. 그래도 리스트 인덱스가 주어지면 \(O(1)\) 시간에 노드의 메모리 주소를 얻어 해당 노드에 접근할 수 있다. 배열에 저장된 것은 노드 자체가 아니라 노드의 참조이기 때문이다.
많은 언어와 달리 Python에서는 숫자도 객체로 감싸져 있으며, 리스트에는 숫자 자체가 아닌 숫자의 참조가 저장된다. 따라서 두 배열의 같은 숫자가 같은 id를 가지며, 숫자들의 메모리 주소는 연속적일 필요가 없다.
Q: C++ STL의 std::list는 이중 연결 리스트를 구현하는데, 일부 알고리즘 책에서는 거의 직접 쓰지 않는 것 같다. 어떤 한계가 있기 때문인가?
한편으로는 보통 배열로 알고리즘을 구현하는 것을 선호하며, 꼭 필요할 때만 연결 리스트를 사용한다. 주된 이유는 두 가지다.
- 공간 비용: 원소마다 이전 원소와 다음 원소를 위한 포인터가 두 개 더 필요하므로
std::list는 보통std::vector보다 공간을 많이 차지한다. - 캐시에 불리함: 데이터가 연속적으로 저장되지 않아
std::list의 캐시 활용률이 낮다. 일반적으로는std::vector의 성능이 더 좋다.
다른 한편으로 연결 리스트가 필요한 경우는 주로 이진 트리와 그래프다. 스택과 큐는 연결 리스트 대신 프로그래밍 언어가 제공하는 stack과 queue를 쓰는 경우가 많다.
Q: res = [[0]] * n으로 만든 이차원 리스트에서 각 [0]은 서로 독립적인가?
독립적이지 않다. 이 이차원 리스트의 모든 [0]은 실제로 같은 객체를 참조한다. 한 원소를 수정하면 대응하는 원소가 모두 함께 바뀐다.
각 [0]을 독립적으로 만들려면 res = [[0] for _ in range(n)]을 사용하면 된다. 이 방식은 서로 독립적인 [0] 리스트 객체 \(n\)개를 초기화한다.
Q: res = [0] * n으로 만든 리스트에서 각 정수 0은 서로 독립적인가?
이 리스트의 모든 정수 0은 같은 객체를 참조한다. Python은 객체 재사용을 극대화하고 성능을 높이기 위해 작은 정수(보통 -5부터 256까지)를 캐시 풀로 관리하기 때문이다.
모두 같은 객체를 가리켜도 리스트의 각 원소는 독립적으로 바꿀 수 있다. Python의 정수는 ‘불변 객체’이기 때문이다. 원소를 바꾸면 기존 객체 자체가 바뀌는 것이 아니라 다른 객체를 참조하게 된다.
그러나 리스트 원소가 리스트, 딕셔너리, 클래스 인스턴스 같은 ‘가변 객체’라면, 원소의 내용을 수정할 때 객체 자체가 바뀌므로 이를 참조하는 모든 원소에서 같은 변화가 나타난다.