■ 연결 리스트의 추상 자료형(ADT)

구현하려면 함수의 사용법을 정의한 추상 자료형이 필요합니다. 연결 리스트의 추상 자료형은 다음과 같습니다.

1| S.append(data) -> None
데이터를 삽입하는 함수입니다. 함수명 append는 파이썬의 리스트에서 가져왔습니다. 반환형은 None입니다.

2| S.search_target(target, start = 0) -> (data, pos)
데이터를 검색하는 첫 번째 함수입니다. 데이터를 순회하면서 대상 데이터를 찾아 그 위치와 함께 반환합니다. pos는 찾은 대상 데이터가 리스트에서 몇 번째 데이터인지를 나타냅니다. 인덱스처럼 0부터 시작합니다. 하지만 pos는 인덱스와는 다릅니다. 인덱스는 인덱싱(indexing)이 가능하여 원하는 데이터에 바로 접근할 수 있지만, 연결 리스트에서는 원하는 데이터를 만나려면 처음부터 모든 데이터를 순회해야 합니다. 찾는 데이터가 없으면 (None, None)을 반환합니다. start는 시작 위치입니다. 시작 위치를 인자로 전달하면 start 전까지는 단순히 순회를 통해 이동만 하고 이후부터 if 문을 통해 대상 데이터와 비교합니다.

3| S.search_pos(pos) -> data
데이터를 검색하는 두 번째 함수입니다. 인자로 위치를 전달하면 연결 리스트에서 해당 위치에 있는 데이터를 반환합니다. 전달한 위치가 범위를 벗어나면 None을 반환합니다. 이 함수도 pos에 도달할 때까지 처음부터 모든 데이터를 순회합니다.

4| S.remove(target) -> data
데이터를 삭제하는 함수입니다. 리스트에 대상 데이터가 있으면 첫 번째 데이터가 지워지면서 그 데이터를 반환합니다. 대상 데이터가 없으면 None을 반환합니다.

5| S.empty() -> bool
연결 리스트가 비었다면 참, 비어있지 않다면 거짓을 반환합니다.

6| S.size() -> integer
연결 리스트의 데이터 개수를 반환합니다.