리스트란?
- 리스트는 가장 자유로운 선형 자료구조
- 스택, 큐, 덱과의 차이점: 리스트는 임의의 위치에서도 항목의 삽입과 삭제가 가능
리스트 ADT
- 데이터: 같은 유형의 요소들의 순서있는 모임
- 연산
- List(): 비어 있는 새로운 리스트를 만듦
- insert(pos, e): pos 위치에 새로운 요소 e을 삽입
- delete(pos): pos 위치에 있는 요소를 꺼내 반환
- isEmpty(): 리스트가 비어있는지를 검사
- getEntry(pos): pos 위치에 있는 요소를 반환
- size(): 리스트안의 요소의 개수를 반환
- clear(): 리스트를 초기화
- find(item): 리스트에서 item이 있는지 찾아 인덱스를 반환
- replace(pos, item): pos에 있는 항목을 item으로 바꿈
- sort(): 리스트의 항목들을 어떤 기준으로 정렬
- merge(lst): 다른 리스트 lst를 리스트에 추가
- display(): 리스트를 화면에 출력
- append(e): 리스트의 맨 뒤에 새로운 항목을 추가
리스트의 구현 방법
- 배열 구조(array)
- 구현이 간단
- 항목 접근이 O(1)
- 삽입, 삭제시 오버헤드
- 항목의 개수 제한
- 연결된 구조(linked list)
- 구현이 복잡
- 항목 접근이 O(n)
- 삽입, 삭제가 효율적
- 크기가 제한되지 않음
배열 리스트의 시간 복잡도
- append(e) 연산: 대부분의 경우 O(1)
- pop() 연산: O(1)
- insert(pos, e) 연산: O(n)
- pop(pos) 연산: O(n)
배열 리스트 구현
class ArrayList:
def __init__(self): # 생성자
self.items = [] # 멤버 변수 선언 및 초기화
def insert(self, pos, elem): # pos 위치에 새로운 요소 item을 삽입
self.items.insert(pos, elem)
def delete(self, pos): # pos 위치에 있는 요소를 꺼내고 반환
return self.items.pop(pos)
def isEmpty(self): # 크기가 0이면 True, 아니면 False 반환
return self.size() == 0
def getEntry(self, pos): # pos번째 항목 반환
return self.items[pos]
def size(self): # 리스트의 크기 반환
return len(self.items)
def clear(self): # items를 초기화
self.items = []
def find(self, item): # 탐색 후 인덱스 반환
return self.items.index(item)
def replace(self, pos, elem): # pos번째 항목 변경
self.items[pos] = elem
def sort(self): # 정렬
self.items.sort()
def merge(self, lst): # 병합(확장)
self.items.extend(lst)
def display(self, msg="ArrayList:"): # 출력(메시지+크기+배열내용)
print(msg, self.size(), self.items)
