1️⃣ List
List는 데이터를 일렬로 나열한 구조로, 데이터의 추가, 삭제, 검색과 같은 다양한 작업을 수행할 수 있습니다. 리스트는 배열 기반과 연결 리스트 기반의 두 가지 주요 유형이 있다.
2️⃣ 배열 기반 리스트
- 배열을 사용하여 데이터를 순차적으로 저장한다.
- 인덱스를 통해 데이터에 빠르게 접근할 수 있는 장점이 있다.
- 그러나 데이터를 중간에 삽입하거나 삭제할 때는 해당 위치에서부터 모든 데이터를 이동시켜야 하므로 비효율적일 수 있다.
- 배열의 크기가 정적인 경우, 배열이 꽉 차면 더 큰 배열로 데이터를 옮겨야 하므로, 크기 조정 작업이 필요할 수 있다.
3️⃣ 연결 리스트 기반 리스트
- 각 데이터가 포인터로 다음 데이터와 연결된 형태로 구성된다.
- 데이터의 삽입과 삭제가 유연하며, 오버헤드 없이 가능하다. 즉, 원하는 위치에 바로 새로운 요소를 추가하거나 제거할 수 있다.
- 그러나 특정 인덱스의 데이터에 접근하기 위해서는 첫 번째 데이터부터 순차적으로 탐색해야 하므로 접근 속도가 느릴 수 있다.
4️⃣ Python 예제
- 파이썬예제를 통해 차이점을 더 쉽게 이해할 수 있도록 해보자. 여기서 파이썬의 내장 리스트 타입을 사용하여 배열 기반 리스트의 동작을 보여주고, 'collections' 모듈의 'deque'를 사용하여 연결 리스트의 특징을 설명하도록 하겠다.
Ⅰ. 배열 기반 리스트 : Python 내장 리스트
- Python의 리스트는 내부적으로 동적 배열을 사용한다. 데이터를 추가, 삭제, 검색하는 기본적인 방법을 알아보자.
# 리스트 생성
my_list = [1, 2, 3, 4, 5]
# 데이터 추가
my_list.append(6) # 리스트 끝에 6 추가
print("Append:", my_list)
# 데이터 삽입
my_list.insert(2, 2.5) # 인덱스 2에 2.5 삽입
print("Insert:", my_list)
# 데이터 삭제
my_list.remove(2.5) # 값 2.5 삭제
print("Remove:", my_list)
# 인덱스를 통한 접근
print("Access by index (index 3):", my_list[3])
1. 리스트 생성
- 여기서부터는 1부터 5까지의 숫자로 리스트를 초기화한다. 이 리스트는 연속된 메모리 공간에 저장된다.
2. 데이터 추가 : ('append')
- 'append' 메소드를 사용하여 리스트의 끝에 새로운 요소 '6'을 추가한다. 이 연산은 일반적으로 O(1) 시간 복잡도를 가지지만, 내부 배열의 공간이 부족할 때는 새로운 배열로 복사하는 과정에서 O(n)이 될 수 있다.
3. 데이터 삽입 : ('insert')
- 'insert' 메소드는 지정된 인덱스 '2'에 새로운 요소 '2.5'를 삽입한다. 이 과정에서 해당 위치 이후의 모든 요소는 한 칸씩 뒤로 이동해야 하므로 시간 복잡도는 O(n)이 된다.
4.데이터 삭제 : ('remove')
- 'remove' 메소드는 리스트에서 첫 번째로 나오는 '2.5'를 찾아서 제거한다. 이 요소를 제거한 후, 뒤에 있는 모든 요소들이 한 칸 씩 앞으로 이동해야 하므로, 이 역시 O(n)의 시간 복잡도를 가진다.
5.인덱스를 통한 접근
- 리스트의 인덱스 '3'을 통해 데이터에 접근한다. 배열 기반 리스트는 인덱스로 직접 접근이 가능하기 때문에 연산은 O(1) 시간 복잡도를 가진다.
Ⅱ. 연결 리스트 기반 리스트 : Collectons.deque
- 'deque' (덱, double-ended queue)는 양쪽 끝에서 데이터를 추가하거나 제거할 수 있도록 설계된 양방향 연결 리스트이다. 중간 삽입 삭제도 지원하지만, 특히 양 끝에서의 작업이 효율적이다.
from collections import deque
# 덱 생성
my_deque = deque([1, 2, 3, 4, 5])
# 끝에 데이터 추가
my_deque.append(6) # 오른쪽 끝에 6 추가
print("Append:", my_deque)
# 시작점에 데이터 추가
my_deque.appendleft(0) # 왼쪽 끝에 0 추가
print("Append left:", my_deque)
# 데이터 삭제
my_deque.pop() # 오른쪽 끝의 요소 삭제
print("Pop:", my_deque)
# 시작점 데이터 삭제
my_deque.popleft() # 왼쪽 끝의 요소 삭제
print("Pop left:", my_deque)
# 인덱스를 통한 접근
print("Access by index (index 2):", my_deque[2])
1. 덱 생성
- 'deque'를 숫자 1부터 5까지로 초기화한다. 'deque'는 내부적으로 양방향 연결 리스트로 구현되어 있으며, 데이터의 양 끝에서 추가와 삭제가 매우 빠르다.
2. 끝에 데이터 추가 : 'append'
- 'append' 메소드는 'deque'의 오른쪽 끝에 요소 '6'을 추가한다. 이 작업은 일반적으로 O(1)의 시간 복잡도를 가진다.
3. 시작점에 데이터 추가 : 'appendleft'
- 'appendleft' 메소드는 'deque'의 왼쪽 끝에 요소 '0'을 추가한다. 이 역시 O(1)의 시간 복잡도를 가진다.
4. 데이터 삭제
- 'pop'과 'popleft'는 각각 'deque'의 오른쪽과 왼쪽 끝에서 요소를 삭제한다. 양쪽 메소드 모두 O(1)의 시간 복잡도를 가진다.
5. 인덱스를 통한 접근
- 'deque'에서도 인덱스 접근이 가능하지만, 내부적으로 양방향 연결 리스트이기 때문에 시작점부터 순차적으로 탐색해야 하므로 O(n)의 시간 복잡도를 가질 수 있다. 그러나 실제로는 더 빠른 접근을 위해 복잡한 인덱싱 메커니즘이 사용된다.