8-3장 커서를 이용한 연결 리스트

 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;
	}
}