[개인공부] 알고리즘 공부 #3

Chapter3 - 기초 데이터구조

---

3.1 데이터구조의 기본 재료

• 이 장에서는 배열과 연결리스트에 대해 알아봄

3.2 배열

3.2.1 1차원 배열

• 배열: V[LB..UB] 형식으로 선언
• 배열첨자는 0부터 N-1까지

3.2.2 다차원 배열

• table 형태로 표시하지만 메모리에 저장될 때에는 일직선의 형태로 저장

3.3 연결리스트

• 동적메모리에 할당괸, 링크에 의해 연결된 유한 개의 데이터원소 노드들
  • 연결리스트 명, L: 첫 노드의 주소
  • 연결리스트 크기, n: 연결리스트 내 노드 수
• 메모리 할당
  • getnode(): 노드를 할당하고 해당 주소 반환
  • putnode(i): 주소i에 할당된 메모리 해제 후 동적메모리에 반환

3.3.1 단일연결리스트

• 가장 단순하게 원소와 링크로 구성
  • 원소: 데이터 원소
  • 링크: 다음 노드 값 없을시 null 저장
• 연결리스트 전체에 대한 참조는 첫 노드의 주소(Head Node) 사용

3.3.2 이중연결리스트

• 각 노드에 원소를 하나 더 추가
  • 원소: 데이터 원소
  • 링크: 다음 노드 주소(Next Node), 다음 노드가 없으면 null 저장
  • 링크: 이전 노드 주소(Prev Node), 이전 노드가 없으면 null 저장
• 접근점은 Head Node 또는 Tail Node 주소 사용

3.3.3 원형연결리스트

• 마지막 노드의 링크가 null이 아닌 헤드 노드의 주소를 가리킴

3.3.4 헤더와 트레일러

• 헤드노드 앞에 헤더노드를 추가하여 사용
• 테일노드 뒤에 트레일러 노드 추가
• 헤더노드와 트레일러 노드는 Dummy Node

3.3.5 그외의 연결리스트

• 원형 헤더 연결리스트
• 원형 이중연결리스트
• 헤더 및 트레일러 이중연결리스트

참고 문헌 : 국형준, 알고리즘 원리와 응용, 21세기사