6-1 연결리스트의 응용

01. 연결 리스트의 변형

연결 리스트의 종류

단순 연결 리스트 

: 하나의 링크만 있고, 각각의 노드의 링크는 후행 노드만을 가리키는 구조

-> 특정 노드의 후행 노드는 쉽게 접근 할 수 있지만, 특정 노드의 선행 노드에 대한 접근은

헤드 노드부터 재검색해야 하는 문제점이 발생함

이중 연결 리스트 

: 특정 노드는 선행 노드를 가리키는 링크와 후행 노드를 가리키는 링크를 가짐

-> 특정 노드에서 선행 노드와 후행 노드에 간단한 프로그램 코드를 통해 접근할 수 있음

원형 연결 리스트

연결 리스트를 살펴보면, 가장 마지막 노드의 링크 필드는 언제나 'null' 값임

- 리스트의 마지막 원소 뒤에는 아무 원소도 없기 때문에 연결 리스트의 마지막 노드의 

링크 필드는 언제나 'null' 값임

- 그래서 마지막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서

원형 연결 리스트가 제안됨 

 

 

02. 원형 연결 리스트

연결리스트의 마지막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기

위해서 원형 연결 리스트가 제안됨

원형 연결 리스트의 생성

- 정의 및 생성 

typedef struct ListNode {	//원형 연결 리스트의 노드 구조 정의
	intdata;
	struct ListNode*link;
}listNode;
typedefstruct{	//원형 연결 리스트의 헤드 노드 구조 정의
	listNode* head;
}linkedList_h;

linkedList_h* createLinkedList_h(void){	//원형 연결 리스트의 헤드 노드 생성
	linkedList_h*H;
	H=(linkedList_h*)malloc(sizeof(linkedList_h));
	H
	returnH;}

삽입 연산(1) 

void addFirstNode(linkedList_h*H,intx){
//원형 리스트 첫 번째 노드 삽입 연산,x값은 100이라고 가정함
	listNode*tempNode;
	listNode*NewNode;
	NewNode =(listNode*)malloc(sizeof(listNode));
	NewNode → data = x;
	NewNode → link = NULL;

void addFirstNode(linkedList_h*H, intx){
if(H → head == NULL){ //현재 리스트가 공백인 경우 
	H → head == NewNode;
	NewNode → link = NewNode;
	return;}
tempNode = H → head;
while(tempNode → link != H → head)
	tempNode =tempNode → link;
NewNode → link = tempNode → link;
tempNode → link = NewNode; 
H → head = NewNode;
}

 

원형 연결 리스트의 노드 삽입

첫 번째 노드를 가리키는 tempNode의모습

tempNode = H → head;
while(tempNode → link != H → head)
	tempNode = tempNode → link;
NewNode → link = tempNode → link;
tempNode → link - NewNode;
H → head = NewNode;