연결 리스트의 응용

단순 연결 리스트는 하나의 링크 부분이 존재한다. 각각의 노드는 후행 노드만을 가리키는 구조이다. 따라서 특정 노드의 선행노드에 대한 접근은 해드 노드부터 재검색해야 한다. 이러한 단점 보완을 위해 선행 노드를 가리키는 링크부분과 후행노드를 가리키는 링크 부분을 갖는 이중 연결리스트가 제안되었다. 단순연 결리 시스트가 사용되지 않는 마지막 노드 링크 부분을 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결리스트가 제안되었다. 단순 연결 리스트의 마지막 노드의 링크가 처음 노드를 가리키게 하여 원형 연결 리스트를 만든다. 원형 연결 리스트는 한 방향으로 모든 노드가 원형으로 계속 연결되어 있기에 한 노드에서부터 다른 어떤 노드로도 접근할 수 있는 이점이 있다.

 

연결 리스트의 변형

단순 연결 리스트의 문제점으로는 하나의 링크만 있고, 각각의 노드의 링크는 후행 노드만을 가리키는 구조이다. 특정 노드 후행 노드는 쉽게 접근할 수 있지만 특정 노드의 선행노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점이 발생한다. 

 

이중 연결 리스트는 단순연결리스트에서는 하나의 링크노드만 있었다면 이를 Rlink, Llink두 개를 만들어 선행노드와 후행노드를 만들어 양쪽에 링크를 다는 것을 말한다.

 

원형 연결 리스트는 단순연결리스트의 마지막 링크필드의 값은 원래 NULL이었는데 이 마지막 노드 링크 필드를 활용하여 프로그램성능을 높인다. 즉 마지막 링크필드에 첫 번째 노드와 연결하는 것을 말한다. 그래서 어느 노드에서든 순회하다 보면 원하는 것을 찾을 수 있다.

 

원형 연결리스트의 생성

typedef struct ListNode { //원형 연결리스트의 노드구조 정의
int data;
struct ListNode* link;
} listNode

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

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

typedef struct 선언문을 사용하여 정의한다. 데이터 부분은 정수형 변수를 사용해 data공간을 할당합니다. 링크 부분은 다음 노드의 주소값을 저장하여 가리키고 있어야 하므로 노드 구조의 자료형 ListNode 포인터를 사용하여 정의한다.

 

맨 앞부분은 헤드 노드라 불리고 연결리스트의 처음 노드를 가리키는 역할을 한다. 헤드 노드는 데이터 부분이 필요 없어 링크부분만 필요하다. 자료형 ListNode를 가리킬 수 있도록 listNode* head라고 정의한다.

 

연결 리스트 생성을 위해 헤드 노드인 H 생성으로 프로시저  createLinkedList_h( ) 해드노드를 하나 생성하여 반환하는 역할을 수행한다. 헤드노드를 가리키는 포인터 변수인 H를 선언하고 malloc(sizeof( )) 함수는 헤드 노드인 linkedList_h크기만큼 메모리 영역을 항당 받아 그 영역에 해당하는 주소를 반환하는 역할을 수행한다. H 링크필드 부분인 head에는 아직 가리킬 노드가 업어 NULL을 저장.

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

if(H→ head == NULL) { // 현재리스트가 공백인 경우
H → head = NewNode;
NewNode → link = NewNode;
return;
}

else {
tempNode = H → head;
while(tempNode → link!= H → head) tempNode = tempNode → link;
NewNode → link = tempNode → link;
tempNode → link = NewNode;
H→ head = NewNode;
} }

위의 코드는 가장 첫 번째에 노드를 삽입하는 코드이다. 원형 연결 리스트의 첫 번째 노드를 삽입하는 함수의 이름을 addFirstNode라고 정의하고 여기서 마지막 노드를 가리키는 변수가 필요하다 마지막 노드의 링크 값은 첫 번째 노드를 가리키게 되어있고 첫 번째 위치의 새로운 노드가 삽입이 되어야 하므로 마지막 노드의 링크 값을 수정해야 한다. 여기서는 자료형 ListNode에 대한 포인터 변수형인 listNode *tempNode라고 정의했다. 그리고 새롭게 정의할 노드는 NewNode이며 malloc함수를 사용하여 메모리 항당을 받고 항당 받은 메모리공간의 주소값을 NewNode가 저장한다.  NewNode값에 100을 저장하고 링크 값은 NULL을 저장한다.

 

헤드노드가 가리키는 노드가 없는 경우 현재 리스트 노드들이 전혀 없는 경우이고 이때는 새롭게 생선 된 첫 번째 노드인 NewNode의 링크가 자기 자신을 가리키게 해야 한다.

 

노드가 있다면 먼저 마지막 노드를 찾기 위해 while(tempNode → link!= H → head)를 사용하고 새로운 첫 번째로 들어갈 NewNode에 링크를 마지막에 있던 tempNode링크값으로 바꾸고 마지막의 tempNode링크를 NewNode로 바꾼다. 그리고 H 링크를 newNode로 바꾸어 원형을 만든다.

 

다음은 중간에 삽입하는 방법을 알아본다면 중간이기 때문에 해드노드는 건드릴 필요가 없겠지요.

vide addMiddleNode(linkedList_h *H, listNode* prevNode, int itdata){
listNode* NewNode;
NewNode = (listNode*) malloc(sizeof(listNode));
NewNode → data = itdata;
NewNode → link - NULL;

NewNode → link = prevNode → link;
prevNode → link = NewNode;
return;
}

addMiddleNode 특정노드 중간에 삽입하는 함수이름으로 정의하고 연결 리스트 헤드노드(H)와 삽입하고자 하는 앞의 노드의 위치를 가리키는 prevNode, 삽입하고자 하는 노드의 데이터 값을 매개변수로 전달받는다.

 

NewNode의 링크를 선행노드가 가리키고 있는 노드를 가리킬 수 있도록 하고 선행노드의 링크를 NewNode 가리킬 수 있도로 한다.

 

삭제 노드 탐색

void finddelCircularNode(linkedList_ h *H, int itdata){ //itdata=90 이것을 삭제한다.
listNode *tempNode;
listNode *prevNode;
PrevNode = H;

if(H →head==NULL){
printf("Circular Linked List is EMPTY");
return;}

else { tempNode = H →head; // 첫 번째 노드부터 검색하자
do {
if(tempNode → data == itdata){
return deleteCircularNode(H, prevNode);} // 찾았다면 삭제 함수를 호출하고 검색함수는 끝
else { prevNode = tempNode;
tempNode = tempNode →link;}
} while(thempNode!= H →head);
}
//마지막 노드까지 검색했는데 없다면
printf("Search Fail");
return;
}

탐색하는 함수이름을 finddelCircularNode 정의하고 연결 리스트의 헤드 노드와 삭제하고자 하는 노드의 data값을 매개변수로 전달받는다. 삭제하고자 하는 data를 비교하기 위해 이동하는 변수를 tempNode라고 정의하고 선행노드를 알기 위해 prevNode변수를 정의한다. prevNode를 선행노드를 가리키도로 ㄱ하기 위해 H부터 출발

 

먼저 공백여부를 확인해야 하고 참이면 공백이다.

 

노드가 존재한다면 data값을 비교할 tempNode를 첫 번째 노드로 이동시키고 비교한다. 값이 같지 않다면 else문이 실행되고 prevNode는 tempNode의 선행노드가 되고 tempNode는 다음 노드위치로 이동한다. revNode = tempNode;
tempNode = tempNode →link;  이때 itdata를 검색하지 못하고 첫 번째 노드로 돌아왔는지 확인하고 아니라면 반복실행한다. 찾았다면 if(tempNode → data == itdata){ return deleteCircularNode(H, prevNode);}

 

노드삭제 코드

void deleteCircularNode(linkedList_h *H, listNode *prevNode){
listNode *lastNode;
listNode *delNode;

lastNode = H →  head;
while(lastNode → link!= H → head) lastNode = lastNode  → link;

delNode = prevNode → link;
prevNode  → link = delNode → link

if(delNode == H → head) lastNode → link = H → head;

free(delNode); }

삭제 함수를 deleteCircularNode라고 정의하고 헤드노드와 삭제하고자 하는 노드의 선행노드의 위치를 가리키는 prevNode를 전달받는다. 마지막위치의 노드를 가리키기 위해 lastNode, 삭제하고자 하는 노드를 가리키는 delNode 변수를 정의

 

마지막 위치의 노드를 찾기 위해 첫 번째 노드의 위치부터 가리키고 lastNode가 첫 번째를 가리키고 있지 않다면 link를 따라 이동한다.

선행노드에서 가리키고 있는 위치 prevNode → link;를 삭제하고자 하는 노드로 저장한다. 이제 링크 값을 삭제하고 하고자 하는 노드의 다음 노드로 저장한다. prevNode  → link = delNode → link

 

삭제하고자 하는 노드가 첫 번째 노드라면 헤드노드는 삭제되는 노드의 후행노드를 가리키게 한다 그리고 마지막 노드는 헤드노드가 가리키는 원형 연결리스트의 처음 노드를 가리케게하고 delNode의 메모리 공간을 힙 영역에 반환하여 삭제한다.

 

이중 연결 리스트의 노드 삽입

void addDNode(linkedList_h *H, listNode *prevNode, int x){
listNode *NewNode;
NewNode = (liseNode*)malloc(sizeof(listNode));
NewNode → Llink = NULL;
NewNode → data = x;
NewNode → Rlink = NULL;

1.NewNode → Rlink  = prevNode → Rlink;
2.prevNode → Rlink = NewNode;
3.NewNode → Llink = prevNode;
4.NewNode → Rlink → Llink = NewNode;
}

1. 먼저 새로운 노드의 Rlink를 prevNode의 Rlink로 같게 하고
2. prevNode의 R링크를 새로 넣는 NewNode를 가리키게 한다
3. 그리고 새로운 노드의 L링크는 prevNode를 가리키게 한다.
4. NewNode의 Rlink에서 화살표가 더 있기에 Rlink가 가리키는 다음 노드의 Link를 NewNode의 주소값으로 바꿔준다.

이중 연결 리스트의 삭제

void deleteDNode(linkedList_h *H, listNode* delNode){

delNode → Link → Rink = delNode → Rlink;
delNode → Rink → Link = delNode → Llink;
free(delNode);
}

삭제 함수 이름을 deleteDNode라고 정의한다. 헤드노드와 삭제하고자 하는 노드의 위치를 가리키는 delNode를 매개변수로 전달받는다.

 

삭제하려는 노드의 앞에 있던 노드의 링크가 삭제되는 노드 다음노드를 가리킬 수 있도록 delNode 앞 노드( delNode → Link)의 Rlink를 delNode의 Rlink값으로 바꾸고 뒤에 오는 링크도 마찬가지로 변경해 준다.

 

그리고 delNode의 메모리 공간을 힙영역에 반환하여 삭제한다.