Python 추상자료형 - 리스트 ( List )

리스트의 기능 

 

특징 : 데이터간 순서 관계를 유지 할 수 있다.

 

기능 

1. 접근 연산 : 특정 위치에 있는 데이터를 가지고 오거나 수정한다.

2. 탐색 연산 : 특정 조건을 만족하는 데이터를 찾는다. 

3. 삽입 연산 : 특정 위치에 새로운 데이터를 저장한다.

4. 삭제 연산 : 특정 위치에 있는 데이터를 지운다.

 

 

Python에서 어떻게 사용하는지 보여드릴께요.

# 리스트 생성
my_list = []

# 특정위치에 삽입
my_list.insert(0, 'A')
my_list.insert(1, 'B')
my_list.insert(2, 'C')

print(my_list) # ['A', 'B', 'C']

# 특정위치 데이터 탐색
print(my_list[0]) # A
print(my_list[1]) # B
print(my_list[2]) # C

print('A' in my_list) # True
print('X' in my_list) # False

# 특정위치 데이터 삽입
my_list[2] = 'D'
print(my_list) # ['A', 'B', 'D']

# 데이터 삭제 연산
del my_list[0]
print(my_list) # ['B', 'D']

 

 

리스트의 구현 

리스트는 어떤 자료구조로 구현되어 있을까요?

동적배열과 링크드리스트로 구현이 가능합니다. 

그럼 어떤 자료구조를 사용해야할까요?

 

각 자료구조의 시간복잡도를 살펴볼께요.

	동적배열	더블리 링크드 리스트
접근	O(1)	O(n)
탐색	O(n)	O(n)
접근+삽입	O(n)	O(n)
접근+삭제	O(n)	O(n)
맨 앞 삽입	O(n)	O(1)
맨 앞 삭제	O(n)	O(1)
맨 뒤 삽입	분할 상환 O(1)	O(1)
맨 뒤 삭제	분할 상환 O(1)	O(1)

 

어떤 기능을 많이 하냐에 따라서 효율적인 자료구조를 선택하면 되는데 

파이썬에서 리스트는 동적배열로 구현되어 있어요.