06 리스트(List)

1. 리스트(List)

• 리스트
  • 순서/위치를 갖는 자료들이 차례대로 나열된 선형 자료구조
  • $L=[ite{m}_0,ite{m}_1,ite{m}_2,..,ite{m}_{n-1}]$

1.1. 추상 자료형

• 데이터: 같은 유형의 요소들의 순서 있는 모임
• 연산:
  • is_empty(): 공백 상태이면 true 반환
  • is_full(): 포화 상태이면 true 반환
  • insert(pos, e): pos에 e 추가
  • delete(pos): pos 꺼내서 반환
  • get_entry(pos): pos 꺼내지 않고 반환

1.2. 교재에서 소개된 리스트

• 배열 구조의 리스트

  • 요소의 수를 별도로 저장
  • 삽입/삭제 시 요소 밀기/당기기 필요

• 단순 연결된 리스트

  • 자기참조 구조체(링크 필드) 및 헤드 포인터 사용
  • 삽입/삭제 시 링크 필드를 수정

• 이중 연결된 리스트

  • 선행 노드와 후속 노드를 가리키는 링크 필드 사용
  • 헤드 포인터 외에도 헤드 노드(dummy node)를 사용할 수 있다.

• 이중 연결된 덱

  • 이중 연결된 리스트에서 헤드 포인터와 테일 포인터를 함께 사용

2. 연결 리스트(Linked List)

2.1. Time Complexity

• Search: $O(n)$ (Linear Search)
• Insert/Delete: 임의 위치에 대하여 $O(n)$

2.2. Features

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

2.3. Applications

• Stack, Queue, Deque, Tree, Graph 등 자료구조 구현
• 빈번한 삽입/삭제가 필요한 데이터 (실시간 데이터 처리 등)
• Hash Table에서 Chaining 방식의 Collision 처리에 사용