Week 4-2 : Circular Linked List

< 180419 >

< Homework >

- 단일 연결리스트에서 최대값을 가지는 노드를 맨 마지막으로 보내기.

void maxLast(ListNode **phead)
{
    ListNode *p, *cur = *phead;
    ListNode *pMax, *cMax = cur;
 
    if(cur == NULL) return ;
 
    while(cur) {
        if(cur->data > cMax->data) {
            pMax = p; cMax = cur;
        }
        p = cur; cur = p->link;
    }
 
    if(pMax == NULL) *phead = cMax->link;
    else pMax->link = cMax->link;
 
    p->link = cMax;
    cMax->link = NULL;
}

>> while() 문이 끝나면 cur 는 NULL, p 는 마지막 노드를 가리키게 된다.

>> cMax 는 최대값을 가지고 있는 노드를, pMax 는 최대값을 가지고 있는 노드의 이전 노드를 가리키게 된다.

1) 원형 연결리스트의 삽입

<소스코드>

#include <stdio.h>
#include <stdlib.h>
 
typedef struct cListNode {
    int data;
    struct cListNode *next;
} CListNode;
 
void CircularListAdd(CListNode **phead, int data)
{
    CListNode *p, *newNode = (CListNode*)malloc(sizeof(CListNode));
    newNode->data = data;
 
    if(*phead == NULL) {
        *phead = newNode;
        newNode->next = newNode;
        return ;
    }
 
    p = *phead;
    while(p->next != *phead)
        p = p->next;
 
    p->next = newNode;
    newNode->next = *phead;
    //*phead = newNode;
}
 
void cDisplay(CListNode *phead)
{
    CListNode *cur = phead;
 
    if(cur == NULL) return ;
 
    do {
        printf("%d\n", cur->data);
        cur = cur->next;
    } while(cur != phead);
}
 
int main()
{
    CListNode *head = NULL; 
    CircularListAdd(&head, 1);
    CircularListAdd(&head, 3);
    CircularListAdd(&head, 7);
    CircularListAdd(&head, 5);
 
    cDisplay(head);    
 
    return 0;
}

>> 9 : 원형 연결리스트의 데이터를 삽입하는 함수.

>> 29 : 원형 연결리스트의 데이터를 출력하는 함수. do ~ while() !!

>> 49 라인의 결과는 1, 3, 7, 5

>> 26 라인의 주석을 해제하면, 49 라인의 결과는 5, 7, 3, 1

>> 즉 26가 없으면 뒤로 삽입, 있으면 앞으로 삽입을 하는 결과가 만들어진다.

>> 다만 위의 코드에서는 삽입을 할때, 항상 맨 마지막 노드를 찾아야 하는 번거로움(?)이 있다. (21-22 라인)

     하지만 헤드포인터를 테일이라고 생각하고 코드를 작성하면 그럴필요가 없어진다..!!

void CircularListAdd2(CListNode **phead, int data)
{
    CListNode *newNode = (CListNode*)malloc(sizeof(CListNode));
    newNode->data = data;
    
    if(*phead == NULL) {
        *phead = newNode;
        newNode->next = newNode;
        return ;
    }
 
    newNode->next = (*phead)->next;
    (*phead)->next = newNode;
    //*phead = newNode;
}

>> main() 에서의 head 를  tail 이라고 생각하는 것이 그림을 그려가는데 있어서 이해하기 쉽다.

>> 14 가 없으면 뒤로 삽입, 14가 있으면 앞으로 삽입하는 코드가 된다.

>> 뒤로 삽입시 출력 결과는 1 5 7 3, 

>> 앞으로 삽입했을 때 결과는 5 1 3 7 이 나온다. 

>> 우리가 작성한 코드대로라면 마지막 노드를 먼저 출력하고 나머지를 출력하기 때문이다.

>> head 포인터가 항상 마지막 노드를 가리키고 있기 때문이다.