[Python] 리스트(List) 정리

안녕하세요. 오늘은 파이썬 자료형 중 하나인 리스트 자료형에 대해 정리하겠습니다. 

파이썬의 리스트는 입력 순서가 유지되며, 내부적으로 동적 배열로 구현되어 있어 삽입/삭제가 가능한 자료구조입니다.

list 는 C++의 vector, Java의 ArrayList와 비슷한데요. 연속된 구조로 저장되는 배열, 다양한 타입을 연결하여 배치하는 연결 리스트의 장점을 갖추고 있어 String, Int, Boolean 등 다양한 자료 데이터형을 저장할 수 있습니다. 

 

목차
1. 리스트란? 
2. 리스트의 주요 연산 

 

📌 1. 리스트란?

리스트란, 선형 자료구조로서 입력순서가 유지되며 내부적으로 동적 삽입 삭제가 가능한(push/pop) 자료구조입니다.

Last in Last Out인 스택의 자료구조와 유사하며, 삽입/삭제는 append() / pop() 메서드를 통해 구현할 수 있습니다. 

리스트(List) 사용 시,  마지막 원소 추가/삭제는 O(1) 의 시간복잡도가 소요되는 것에 비해  첫번째 원소를 삽입/삭제하는 경우 O(N) 이 소요되므로 큐의 연산을 사용할 때에는 주의해야 합니다. 또한, O(1),O(N),O(k) 등 복잡도를 가진 여러 연산들을 지원합니다. 

 

파이썬에서 리스트는 대괄호 [ ]를, 튜플은 소괄호 ( )를, 딕셔너리는 중괄호 { }를 사용해서 나타냅니다. 리스트는 자료를 변경할 수 있으며, 인덱스 1,2,3 등으로 순차적 접근이 가능합니다 .

 

📌 2. 리스트의 주요 연산

1. len(a)  

: 전체 요소의 개수를 리턴한다. 

시간 복잡도 : O(1) 

a = [1,2,3] 
print(len(a)) #3

 

2. a[i] 

: 특정 인덱스 i의 요소를 가져온다. 

시간 복잡도 : O(1) 

a = [1,2,3] 
print(a[1]) #2

 

3. a[i:j] 

: 범위 i부터 j까지(i이상 j미만) 슬라이스의 길이만큼 k개의 요소를 가져온다.

시간복잡도 : O(k) 

a = [1,2,3,4,5]
b = a[1:3] #2,3

 

4. elem in a 

: elem 에 a 요소가 있는 지 확인한다. 처음부터 순차 탐색하므로 최악의 경우 O(N), 최선의 경우 O(1) 시간이 소요됩니다. 

시간복잡도 : O(N)

 

5. a.count(elem) 

: elem 의 요소의 개수를 리턴합니다. 

시간복잡도 : O(N) 

a = [1,2,3,4,5,'안녕',True, True]
print(a.count(True)) #2

 

6. a.index(elem) 

: elem 요소의 인덱스를 리턴합니다. 

시간복잡도 : O(N)

 

7. a.append(elem) 

: 리스트에 elem 요소를 추가합니다.

시간복잡도 : O(1) 

a = [1,2,3,4,5,'안녕']
a.append('행복')

 

8. a.pop() 

: 리스트의 마지막 요소를 빼냅니다. (스택의 Pop 연산) 

시간복잡도 : O(N)

a = [1,2,3,4,5,'안녕']
a.append('행복')
a.pop() #삽입된 데이터 행복이 제거

 

9. a.pop(0) 

: 리스트의 첫번째 요소를 빼냅니다. (큐의 Pop 연산) 

시간복잡도 : O(1)

a = [1,2,3,4,5,'안녕','행복']
a.pop(0) #처음 데이터인 1이 제거

 

10. del a[i] 

: 리스트의 i번째 요소를 삭제합니다 .

최악의 경우 시간복잡도 O(N), 최선의 경우 시간복잡도 O(1) 

a = [1,2,3,4,5,'안녕','행복']
del(a[5]) #안녕이 제거

 

11. a.sort() 

: Team sort 방법을 사용해 O(NlogN) 만에 리스트를 정렬합니다.

시간 복잡도 : 최선의 경우 O(N) 에 실행됩니다. 

 

12. min(a) / max(a) 

: 최솟값 / 최댓값을 계산하여 리턴합니다. 

시간복잡도 : 전체를 선형 탐색해야 하므로 O(N) 

a = [1,2,7,4,6,3]
print(max(a)) #7
print(min(a)) #1

 

13. a.reverse() 

: 입력순서가 유지된 리스트를 뒤집습니다.

시간복잡도 : O(N)

a = [1,2,7,4,6,3]
a.reverse()