[추상자료형] 리스트(List)

[추상자료형] 리스트(List)

• 정의: 값들의 순서있는 나열 (같은 값이 한 번 이상 나올 수 있다)
• 순서있는 (ordered): 각 값들 간의 대소관계가 아닌, 값들의 등장 순서
  예) [1, 2, 3] ≠ [3, 2, 1]
  
• 나열 (sequence): 없거나 하나 이상의 값을 순서있게 배치한다.
• 용어
• 객체(entity): 리스트를 구성하는 개별 값
  
• 빈 리스트 (Nil, Not in list): 포함하는 객체가 없는 리스트
• 크기(length): 리스트 내 객체의 개수
  
• 리스트의 구성
• List of T = head(T) :: tail(List of T)
  타입 T의 리스트(List of T)는 '타입 T 객체인 head'와 '타입 T 리스트(List of T)인 tail'의 재귀로 이루어져 있다.
  
• 머리(head): 리스트의 구성 요소 중 가장 앞의 노드
  
• 꼬리(tail): 리스트의 구성 요소 중 머리를 제외한 나머지 노드들
• 같다(equality): L1 = head1 :: tail1, L2 = head2 :: tail2 일 때 head1 = head2, tail1 = tail2이면 L1과 L2는 같다.
  
• 기본 연산 (operation)
• 빈 리스트 생성 (constructor): 리스트의 초기 상태 정의
  
• 공백 여부 확인 (isEmpty): 용어 2(빈 리스트), 3(크기) 참조
  
• 리스트의 앞에 객체를 추가(prepend)
• 리스트 L2(head2 :: tail2) 앞에 리스트 L1(head1 :: tail1)을 추가: L1 :: L2 = head1 :: (tail1 :: L2)
• 리스트 L(head :: tail) 앞에 객체 e를 추가: e :: L = e :: head :: tail
  
• 리스트의 뒤에 객체를 추가(append)
• 리스트 L1(head1 :: tail1) 뒤에 리스트 L2(head2 :: tail2)를 추가: L1 :: L2 = head1 :: (tail1 :: L2)
• 리스트 L(head :: tail) 뒤에 객체 e를 추가: L :: e = head :: (tail :: (e :: Nil))
  
• 리스트의 머리와 꼬리를 구분(x :: xs): 리스트는 head :: tail으로 구성되어 있기 때문에 항상 머리와 꼬리로 구분할 수 있다.
• 구현
• 구성 요소
  
• sequence: TO-BE-FILLED
  
• interface: TO-BE-FILLED
• 구현 예시
• /* TO-BE-FILLED */