파이썬리스트 특징
• bamjun
Python의 리스트(list)는 연결 리스트(linked list)가 아닙니다. Python의 리스트는 동적 배열(dynamic array)을 기반으로 구현되어 있습니다. 이 구현은 Python의 표준 라이브러리인 CPython에서 확인할 수 있습니다.
동적 배열과 연결 리스트는 다음과 같은 차이점을 가집니다:
- 메모리 할당:
- 동적 배열: 배열의 요소는 메모리 상에서 연속적인 위치에 저장됩니다. 이는 인덱스를 통한 빠른 요소 접근을 가능하게 합니다. Python 리스트는 필요에 따라 자동으로 크기를 조정합니다.
- 연결 리스트: 각 요소(노드)는 다음 요소의 주소를 포함하며, 메모리 상에서 연속적으로 위치하지 않을 수 있습니다. 이는 요소 추가 및 삭제가 더 유연하지만, 특정 인덱스의 요소에 접근하기 위해서는 처음부터 순회해야 하므로 접근 시간이 더 오래 걸립니다.
- 성능:
- 동적 배열: 인덱스를 통한 요소 접근이 빠릅니다(일정한 시간 복잡도 O(1)). 그러나 배열의 크기를 변경할 때는 기존 배열을 새로운 크기의 배열로 복사하는 과정이 필요하므로, 크기 조정 시에는 더 많은 시간이 소요될 수 있습니다.
- 연결 리스트: 요소 추가 및 삭제가 빠르지만(일반적으로 O(1)), 특정 인덱스의 요소에 접근하거나 검색하는 데는 더 많은 시간이 소요됩니다(O(n)).
Python에서 연결 리스트와 같은 동작을 구현하려면, 기본 제공되는 리스트 대신 사용자 정의 클래스나 collections 모듈의 deque 클래스를 사용할 수 있습니다. deque는 양방향 큐(double-ended queue)로, 연결 리스트와 유사한 특성을 가지며, 양쪽 끝에서의 요소 추가 및 삭제를 빠르게 수행할 수 있습니다.
Python의 collections 모듈에서 제공하는 deque (덱, 또는 데크라고 발음)는 양방향 큐(double-ended queue)를 구현한 객체입니다. deque는 양 끝에서 빠르게 요소를 추가하거나 제거할 수 있으며, 리스트(list)보다 더 효율적인 방법으로 이러한 작업을 수행합니다. deque는 스택(stack) 또는 큐(queue)의 기능을 모두 갖추고 있어 유연하게 사용할 수 있습니다.
다음은 deque의 사용 예시입니다:
from collections import deque
# deque 생성
d = deque()
# 오른쪽(끝)에 요소 추가
d.append(1) # deque: 1
d.append(2) # deque: 1, 2
# 왼쪽(앞)에 요소 추가
d.appendleft(3) # deque: 3, 1, 2
# deque 출력
print("Deque:", d)
# 오른쪽 요소 제거하고 반환
right = d.pop() # 반환된 요소: 2, deque: 3, 1
print("Pop from right:", right)
# 왼쪽 요소 제거하고 반환
left = d.popleft() # 반환된 요소: 3, deque: 1
print("Pop from left:", left)
# deque 출력
print("Updated deque:", d)
이 예제에서는 deque를 생성하고, 양쪽 끝에 요소를 추가(append, appendleft)하고, 양쪽 끝의 요소를 제거(pop, popleft)하여 반환하는 과정을 보여줍니다. deque는 이렇게 양쪽 끝에서의 추가와 제거 작업을 빠르고 효율적으로 수행할 수 있어, 다양한 알고리즘과 데이터 구조에 적합합니다.