06 List

1. 리스트(List)

리스트(List)
- 순서/위치를 갖는 자료들이 차례대로 나열된 선형 자료구조
- $L = [i t e m_{0}, i t e m_{1}, i t e m_{2}, .., i t e m_{n - 1}]$
- 집합(Set)과의 차이: 항목 간의 중복을 허용하며, 순서의 개념이 있다.
- 예시: 핸드폰 문자 메시지 리스트, 다항식의 각 항 등

데이터
- 같은 유형의 요소들의 순서 있는 모임
연산
- insert(pos, e): pos 위치에 요소 e 삽입
- delete(pos): pos 위치의 요소 삭제 및 반환
- is_empty(), is_full(): 리스트의 공백/포화 상태 검사
- get_entry(pos): pos 위치의 요소 반환

메모리 비연속적 저장 (각 노드가 다음 노드 주소를 저장)
- → 인덱스 접근 불가 (Sequential Access)
- → 삽입/삭제가 빠름 (노드 포인터만 수정)
- → 링크 필드 저장으로 인한 메모리 오버헤드
동적 크기 할당 (필요에 따라 크기 변화 가능)

배열 구조의 리스트
- 요소의 수를 별도로 저장
- 삽입/삭제 시 요소 밀기/당기기 필요
단순 연결된 리스트
- 자기참조 구조체(링크 필드) 및 헤드 포인터 사용
- 삽입/삭제 시 링크 필드를 수정
이중 연결된 리스트
- 선행 노드와 후속 노드를 가리키는 링크 필드 사용
- 헤드 포인터 외에도 헤드 노드(dummy node)를 사용할 수 있다.
이중 연결된 덱
- 이중 연결된 리스트에서 헤드 포인터와 테일 포인터를 함께 사용

구조
- 고정된 크기의 배열(data[MAX_SIZE])과 현재 요소의 수(size)를 이용
특징 및 시간 복잡도
- 접근(get_entry): 인덱스로 직접 접근하므로 $O (1)$ 로 매우 빠름
- 삽입(insert): 중간에 삽입 시 뒤의 요소들을 한 칸씩 뒤로 밀어야 하므로 $O (n)$
- 삭제(delete): 중간 요소 삭제 시 뒤의 요소들을 한 칸씩 당겨야 하므로 $O (n)$
Lab. 추가 연산
- append(맨 뒤 추가), pop(맨 뒤 삭제), replace(수정), find(검색)

구조
- 노드(Node): 데이터(data)와 다음 노드를 가리키는 포인터(link)로 구성
- 헤드 포인터(Head Pointer): 리스트의 첫 번째 노드를 가리키는 포인터
특징 및 시간 복잡도
- 탐색(get_node)
  - 앞에서부터 순차적으로 찾아야 하므로 $O (n)$
- 삽입/삭제
  - 물리적인 데이터 이동 없이 포인터만 변경하면 됨
  - 삽입/삭제할 위치의 선행 노드(before)를 알고 있다면 $O (1)$
  - 그렇지 않다면 위치를 찾는 과정 때문에 $O (n)$
헤드 노드(Head Node)
- 실제 데이터를 담지 않고 시작 위치만 표시하는 더미 노드
- 첫 번째 노드 삽입/삭제 시의 예외 처리를 없애고 코드를 단순화하기 위해 사용
Lab. 추가 연산
- 배열 리스트와 동일한 추가 연산(append, pop, replace, find) 구현

구조
- 단순 연결 리스트의 단점(선행 노드 찾기 어려움)을 보완
- 노드 구조: prev (이전 노드 포인터) + data + next (다음 노드 포인터)
특징
- 양방향 탐색이 가능하여, 특정 노드만 알면 삭제나 이전 위치 삽입이 $O (1)$ 에 가능
Lab. 덱(Deque) 연산
- 후단 삭제(delete_rear): tail 포인터가 없어도 prev를 이용해 마지막 노드의 이전을 바로 찾을 수 있어 $O (1)$ 로 구현 가능