정글 26일차

4주차부터는 c언어로 진행된다.

1. 연결리스트

1-1. 리스트

추상적 자료형(스택, 큐, 그래프, 집합 등 실체적 구현법과 무관하게 개념만 정의) 중 하나.
그래프 1. 순서를 가지고 2. 선형으로 나열된 원소들의 집합이다.

1-2. 연결리스트

리스트의 구체적 구현인 자료구조(배열, 이진 탐색 트리, 힙 등 구체적 구현이 정의)
각 노드는 다음 노드(의 주소)를 가리키고 있다.
이전 노드의 주소도 가진 이중 연결리스트,
마지막 노드가 첫 노드를 가리키는 순환하는 형식의 원형 연결리스트도 있다.

2. 연습문제

2-1. 연결리스트 1번

int insertSortedLL(LinkedList *ll, int item)
{
    ListNode *cur = ll->head;
    ListNode *prev = NULL;
    int i = 0;

    while (i < ll->size){
        if (item == cur->item) {
            return -1;
        }
        else if (item > cur->item) {
            prev = cur;
            cur = cur->next;
        }
        else {
            break;
        }
        i++;
    }
    // 현위치에 삽입
    if (i == 0) {
        prev = ll->head;
        ll->head = malloc(sizeof(ListNode));
        ll->head->item = item;
        ll->head->next = prev;
    }
    else {
        prev->next = malloc(sizeof(ListNode));
        prev->next->item = item;
        prev->next->next = cur;
    }
    ll->size++;

    return i;
}

처음에는 prev포인터를 안 쓰고 풀어보려 했는데 오히려 head 예외처리를 하느라 코드가 늘어지는 것이 마음에 안 들어 다시 짰다.

// 처음에 작성한 코드
int insertSortedLL(LinkedList *ll, int item)
{
    ListNode *now = ll->head;
    ListNode *new;
    int temp;
    new = (ListNode*)malloc(sizeof(ListNode));
    new->item = item;
    new->next = NULL;

    if (ll->head == NULL)
    {
        ll->head = new;
        ll->size++;
        return 0;
    }
    else if (new->item < ll->head->item) {
        new->next = ll->head;
        ll->head = new;
        ll->size++;
        return 0;
    }

    for (int i = 1; i <= ll->size; i++)
    {
        if (new->item == now->item) {
            return -1;
        }
        else if (now->next == NULL) {
            now->next = new;
            temp = i;
            break;
        }
        else if (new->item < now->next->item) {
            new->next = now->next;
            now->next = new;
            temp = i;
            break;
        }
        else {
            now = now->next;
        }
    }
    ll->size++;
    return temp;
}

앞에 예외처리하는 if문이 없어 더 눈에 잘 들어오는 것 같다.
삽입할 때 메모리를 할당하여 별도로 free를 할 필요가 없기도 하다.

2-2. 연결리스트 3번

void moveOddItemsToBack(LinkedList *ll)
{
    ListNode *cur, *head_odd, *tail_odd, *tail_even;

    if (ll->head == NULL) {
        return;
    }

    cur = ll->head->next;
    if (ll->head->item % 2 == 1) {
        head_odd = ll->head;
        head_odd->next = NULL;
        tail_odd = head_odd;
        ll->head = NULL;
    }
    else {
        tail_even = ll->head;
    }
    
    while (cur != NULL) {
        if (cur->item % 2 == 1) {
            // cur은 홀수
            if (head_odd == NULL) {
                head_odd = cur;
                head_odd->next = NULL;
            }
            tail_odd->next = cur;
            tail_odd = tail_odd->next;
            cur = cur->next;
            tail_odd->next = NULL;
        }
        else {
            // cur은 짝수
            if (ll->head == NULL) {
                ll->head = cur;
                tail_even = cur;
            }
            else {
                tail_even->next = cur;
                tail_even = cur;
            }
            cur = cur->next;
        }
    }
    tail_even->next = head_odd;
}

홀수 리스트와 짝수 리스트로 분리하고 홀수 리스트를 짝수 리스트 뒤에 연결하는 방식으로 구현하였다.

2-3. 연결리스트 6번

int moveMaxToFront(ListNode **ptrHead)
{
    ListNode *max, *max_prev, *cur, *prev;
    cur = *ptrHead;
    max = *ptrHead;
    
    if (*ptrHead == NULL) {
        return -1;
    }

    while (cur != NULL) {
        if (cur->item > max->item) {
            max = cur;
            max_prev = prev;
        }
        prev = cur;
        cur = cur->next;
    }
    if (max_prev != NULL) {
        max_prev->next = max->next;
        max->next = *ptrHead;
        *ptrHead = max;
    }

    return max->item;
}

최대 값 노드를 맨 앞으로 옮기는 문제
먼저 최대 값을 순회하여 찾고 앞에 삽입한다.
최대 값이 헤드에 있는 경우에는 별도로 작업하지 않는다.

2-4. 연결리스트 7번

void RecursiveReverse(ListNode **ptrHead)
{
    ListNode *cur, *newHead;

    cur = *ptrHead;
    if (cur->next == NULL) {
        return;
    }
    while (cur->next->next  != NULL) {
        cur = cur->next;
    }
    cur->next->next = cur;
    newHead = cur->next;
    cur->next = NULL;
    RecursiveReverse(ptrHead);
    *ptrHead = newHead;
}

재귀를 사용하여 연결리스트를 거꾸로 뒤집는 문제
매 재귀마다 마지막 노드를 반대로 뒤집어 준다.