1. 커서로 연결 리스트 만들기
- 각 노드를 배열 안의 요소에 저장하고 그 요소를 잘 이용해 연결 리스트를 구현
- 실행 중에 데이터의 개수가 크게 바뀌지 않고 데이터 개수의 최댓값을 미리 알 수 있다면
배열을 사용해 효율적으로 연결리스트 구현
- 배열의 커서에 해당하는 값 = 다음 노드가 들어 있는 요소의 인덱스에 대한 값
- 커서(cursor) : 포인터 역할을 하는 인덱스
-> 노드 B의 커서 3은 B의 다음 노드 C가 인덱스 3인 위치에 저장되어 있음을 의미
-> 꼬리 노드의 커서는 -1
-> 노드의 삽입, 삭제 시 요소를 옮길 필요 없음
ex) 머리에 노드 G 삽입
- head를 1에서 6으로 업데이트 하고 노드 G의 커서에 1을 대입
2. 배열에 비어 있는 요소 처리하기
1)
- 연결 리스트: A->B->C->D
- 배열 : C->A->D->B
- 머리 커서 head의 값은 노드 A가 들어 있는 인덱스 1
- 노드 A의 커서 값 3 (B가 인덱스 3인 요소에 들어 있음)
- 노드 B의 커서 값 0 (C가 인덱스 0인 요소에 들어 있음)
- 노드 C의 커서 값 2 (D가 인덱스 2인 요소에 들어 있음)
- 노드 D의 커서 값 -1( 꼬리값)
2)
- 연결 리스트의 머리에 노드 E 삽입
- 인덱스가 4인 위치에 노드 E
- head의 값은 노드 E가 들어 있는 인덱스 값인 4로 바뀜
- 삽입한 노드 E는 다음 노드 A가 인덱스 1에 들어 있으므로 커서의 값을 1로 지정
- 배열에 저장한 데이터의 물리적인 위치 != 연결 리스트에 저장된 데이터의 논리적인 순서
- n번째 레코드 : 배열의 n번째 인덱스에 들어있는 노드
3)
- 3번째 노드 B 삭제
- 3번째 레코드가 비어 있는 상태
- 노드 A의 다음 노드는 노드 C로 변경
- 노드 A의 커서 값도 3에서 0으로 업데이트
3. 프리 리스트 구현하기
프리 리스트 (free list)
- 삭제한 레코드를 관리 하기 위해 사용하는 자료구조
- '사용하지 않는 빈 배열'의 문제 해결
1) 커서의 자료형
-Index는 커서의 자료형을 나타내는 typedef 이름
2) 노드의 자료형 Node
- 연결 리스트의 노드를 의미
- 커서 next의 자료형은 커서의 자료형인 Index
- Dnext : 프리 리스트의 다음 포인터 (프리 리스트의 다음 노드를 가리키는 다음 커서)
3) 연결 리스트를 관리하는 구조체 List
- 연결 리스트를 관리하는 구조체
- deleted : 프리 리스트의 머리 커서 ( 프리 리스트의 머리 노드를 가리키는 커서)
- max : 배열의 가장 꼬리 쪽에 들어 있는 레코드 번호
typedef int Index; //커서의 자료형
//노드
typedef struct {
Member data; //데이터
Index next; //다음 노드
Index Dnext; //프리 리스트의 다음 노드
}Node;
//연결 리스트
typedef struct {
Node *n; //리스트 본체(배열)
Index head; //머리 노드
Index max; //사용중인 꼬리 레코드
Index deleted; //프리 리스트의 머리 커서
Index crnt; //선택한 노드
}List;
- 노드의 삽입과 삭제에 따라 프리리스트가 변화하는 모습
1)
- 연결 리스트 : A->B->C->D->E
- max : 7
- 3개의 레코드 1,3,5는 삭제를 마친 빈 레코드
- 프리 리스트는 3->1->5
- 프리 리스트의 머리 노드의 인덱스 3은 연결 리스트용 구조체 List의 멤버 deleted에 저장
2)
- 연결 리스트 꼬리에 노드 F 삽입
- 노드 삽입 위치는 프리 리스트 3,1,5중 머리 노드인 3 사용
- 노드 F를 3번째 레코드에 저장하고 프리리스트에서 3 삭제 (프리리스트 1->5)
- max값은 8이 아니라 7 상태 유지
3)
- 노드 D를 삭제
- 7번째 레코드에 넣어둔 데이터를 삭제 했기 때문에 7을 프리 리스트의 머리 노드로 추가
- 프리리스트 7->1->5
- 노드를 삽입할 때 레코드 번호를 정하는 GetIndex 함수
//삽입할 레코드의 인덱스를 구한 다음 반환
static Index GetIndex (List *list)
{
if(list->deleted == NULL) //프리리스트가 비워져 있는 경우
return ++(list->max);
else {
Index rec = list->deleted;
list->deleted = list->n[rec].Dnext;
return rec;
}
}
- 삭제한 레코드를 프리 리스트에 등록하는 함수 DeleteIndex 함수
//지정된 레코드를 삭제 리스트에 등록
static void DeleteIndex (List *list, Index idx)
{
if(list->deleted == Null) { //프리리스트가 비워져 있는 경우
list->deleted = idx;
list->n[idx].Dnext = Null;
}
else
{
Index ptr = list->deleted;
list->deleted = idx;
list->n[idx].Dnext = ptr;
}
}
'C언어 > 자료구조' 카테고리의 다른 글
9-1장 트리 (0) | 2023.08.03 |
---|---|
8-4장 원형 이중 연결 리스트 (0) | 2023.08.03 |
8-2장 포인터를 이용한 연결 리스트(2) (0) | 2023.08.02 |
8-2장 포인터를 이용한 연결 리스트(1) (0) | 2023.08.02 |
8-1장 선형 리스트 (0) | 2023.08.02 |