8-2장 포인터를 이용한 연결 리스트(2)

1. 머리에 노드를 삽입하는 InsertFront 함수 

 

- 연결 리스트의 머리에 노드를 삽입하는 함수 

//머리에 노드를 삽입
void InsertFront(List *list, const Member *x) 
{
	Node *ptr = list->head;
	list->head = list->crnt = AllocNode();
	SetNode(list->head,x,ptr);
}

1)

- 삽입 전의 머리 노드 A에 대한 머리 포인터를 ptr에 대입

Node *ptr = list->head;

 

2)

- 삽입할 노드 G를 AllocNode 함수로 만들고 만든 노드를 가리키도록 머리 포인터 list->head를 업데이트

list->head = list->crnt = AllocNode();

 

3)

- SetNode 함수를 호출하여 값 설정

- next값을 ptr(삽입하기 전의 머리 노드 A)로 업데이트 

SetNode(List->head,x,ptr);

삽입 전

 

 

삽입 후 

 

2. 꼬리에 노드를 삽입하는 InsertRear 함수 

 

- 연결 리스트 꼬리에 노드를 삽입하는 함수 

- 리스트가 비어 있는지 아닌지 먼저 확인

 

 - 리스트가 비어 있는 경우 

   - InsertFront 함수로 처리 

 - 리스트가 비어 있지 않은 경우 

   - 리스트 꼬리에 노드 G삽입

 

//꼬리에 노드를 삽입
void InsertRear (List *list, const Member *x) 
{
	if(list->head == NULL) //비어 있는 경우 
		InsertFront(list,x); //머리에 삽입
	else {
		Node *ptr = list -> head;
		while(ptr->next != NULL)
			ptr = ptr->next;
		ptr->next = list->crnt = AllocNode();
		SetNode(ptr->next,x,NULL);
	} 	
}

 

1) 

- ptr(머리노드 가리킴)이 가리키는 노드를, 계속해서 다음 노드를 가리키도록 업데이트하는 과정을 반복 

- ptr->next가 가리키는 노드가 널이 되면 while문을 종료 

- 이때 ptr이 가리키는 노드는 꼬리노드 F

Node *ptr = list->head;
while(ptr->next != NULL)
	ptr = ptr->next;

 

2)

- 삽입할 노드 G를 AllocNode함수로 만듬

- 삽입하기 전의 꼬리노드 F의 다음 포인터 ptr->next가 가리키는 노드에 삽입한 다음의 꼬리노드 G를 대입

- SetNode함수를 이용해 G의 값을 설정

 -> next에는 null대입

ptr->next = list->crnt = AllocNode();
SetNode(ptr->next,x,NULL);

 

삽입 전

 

삽입 후 

 

3. 머리 노드를 삭제하는 RemoveFront 함수 

 

- 머리노드를 삭제 

- 리스트가 비어 있지 않은 경우에만 삭제 

//머리 노드를 삭제 
void RemoveFront(List *list) 
{
	if(list->head != NULL)
	{
		Node *ptr = list->head->next; //2번째 노드에 대한 포인터 
		free(list->head); //머리 노드를 해제 
		list->head = list->crnt = ptr; //새로운 머리 노드  
	}
}

- 삭제하기 전의 머리 노드 A의 메모리 영역 해제 

- list->head에 두번째 노드 B에 대한 포인터 list->head->next를 대입하여 list->head가 노드 B를 가리키도록  업데이트 

 

삭제 전

삭제 후 

 

4. 꼬리 노드를 삭제하는 RemoveRear 함수 

 

- 꼬리 노드를 삭제 

- 노드 1개인지 2개 이상인지 구분

 

- 리스트에 노드 1개만 있는 경우 

 -> RemoveFront  실행 

//꼬리 노드를 삭제 
void RemoveRear(List *list) 
{
	if(list->head != NULL) {
		if((list->head)->next == NULL) //노드가 1개 있는 경우 
			RemoveFront(list);
		else {
			Node *ptr = list->head;
			Node *pre; //핸져 스캔하고 있는 노드의 앞에 있는 노드 
			while(ptr->next !=NULL) 
			{
				pre = ptr;
				ptr = ptr->next;
			}
			pre->next = NULL; //pre는 꼬리 노드로부터 두 번째 노드
			free(ptr); //ptr은 꼬리노드
			list->crnt = pre; 	
		}
	}
}

 

1)

- '꼬리 노드'와 '꼬리 노드로부터 두 번째 노드'를 찾음

- pre : 현재 스캔하고 있는 노드의 '앞에 있는 노드'를 가리키는 변수 

Node *ptr = list->head;
Node *pre;
while(ptr -> next != NULL) {
	pre = ptr;
    ptr = ptr->next;
}

 

2)

- 꼬리 노드부터 두 번째 노드인 E의 next에 null 대입

- 꼬리 노드 F 메모리 해제 

pre->next = NULL;
free(ptr);
list->crnt = pre;

삭제 전 

삭제 후 

 

5. 선택한 노드를 삭제 하는 RemoveCurrent 함수 

 

- 현재 선택한 포인터(list->crnt)가 가리키는 노드를 삭제 

 

- crnt가 머리 노드인 경우 

 -> RemoveFront함수로 처리 

 

//선택한 노드를 삭제 
void RemoveCurrent(List *list) 
{
	if(list->head != NULL) {
		if(list->crnt == list->head) //머리 노드를 선택한 상태라면
			RemoveFront(list); //머리 노드를 삭제  
		else {
			Node *ptr = list -> head;
			while(ptr->next != list->crnt) 
				ptr = ptr->next;
			ptr->next = list->crnt->next;
			free(list->crnt);
			list->crnt = ptr;
		} 
	}
}

 

삭제 전

삭제 후 

1) 

 - 선택한 노드의 앞 노드를 찾음

 - while문은 머리 노드부터 ptr->next가 list->crnt와 같을 때까지 반복

Node *ptr = list->head;
while(ptr->next != list->crnt)
	ptr = ptr->next;

 

2)

- 삭제하기 위해 선택한 노드 D 의 다음 노드 포인터 list->crnt->next를 노드 C의 다음 노드 포인터 ptr->next에 대입 

- 노드 C의 next가 노드 E로 업데이트 

- 노드 D 메모리 해제

ptr->next = list->crnt->next;
free(list->crnt);
list->crnt = ptr;

 

6. 모든 노드를 삭제하는 Clear 함수 

 

- 연결 리스트가 완전히 텅 빈 상태 (head == NULL)가 될 때까지 머리 요소의 삭제 작업 반복

//모든 노드를 삭제 
void Clear(List *list) 
{
	while(list->head != NULL) //텅빌때 까지 
		RemoveFront(list); //머리 노드를 삭제 
	list->crnt = NULL; 
}

 

7. 선택한 노드의 데이터를 출력하는 PrintCurrent/PrintLnCurrent 함수 

 

- 선택한 포인터 list->crnt가 가리키는 노드의 데이터를 출력

//선택한 노드의 데이터를 출력
void PrintCurrent(const List *list) 
{
	if(list->crnt == NULL)
		printf("선택한 노드가 없습니다.");
	else
		PrintMember(&list->crnt->data);
}

//줄바꿈 문자 포함  
void PrintLnCurrent (const List *list)
{
	PrintCurrent(list);
	putchar('\n');
}

 

8. 리스트의 모든 노드를 출력하는 Print 함수 

 

- 리스트의 모든 노드를 순서대로 출력

//모든 노드의 데이터를 리스트 순으로 출력
void Print(const List *list) 
{
	if(list->head == NULL)
		puts("노드가 없습니다.");
	else {
		Node *ptr = list->head;
		puts("[모두 보기 ]");
		while(ptr != NULL) {
			PrintMember(&ptr->data);
			putchar('\n');
			ptr = ptr->next; 
		} 
	} 
}

 

9. 연결 리스트를 종료하는 Terminate 함수 

 

- 모든 노드를 삭제 하는 Clear 함수 호출

//연결리스트를 종료
void Terminate(List *list) 
{
	Clear(list); //모든 노드를 삭제  
}