Q5_A_LL.c (frontBackSplitLinkedList 함수) - sihyun10/data_structures_docker GitHub Wiki

이 문제는 frontBackSplitLinkedList() 함수를 구현하는 문제였다.
이 함수는 주어진 연결 리스트를 앞/뒤로 두 개의 연결 리스트 (Front, Back)으로 나누어주는 기능이다.

마주친 문제

코드를 다 구현한 후에 아래와 같은 오류를 마주쳤었다.
바로 메모리를 두 번 해제하려고 할 때 발생하는 문제라고 한다.
즉 내 코드에서 메모리 해제가 중복으로 이루어져서 오류가 나는 것이다.

free(): double free detected in tcache 2
qemu: uncaught target signal 6 (Aborted) - core dumped
Aborted

어떻게 해결했을까?

// 두 줄의 코드 추가

  ll->head = NULL;
  ll->size = 0;

원본 리스트의 포인터 끊기

• ll->head = NULL; 과 ll->size = 0; 의 코드를 추가해, ll 원본 리스트의 head, size를 초기화 시켜준다.
• removeAllItems()를 호출할 때 원본 리스트를 잘못 해제하는 문제는 발생하지 않게 된다.

즉 ll(원본 리스트)를 resultFrontList와 resultBackList 두 개의 리스트로 소유권을 넘겨주었기 때문에
원본 리스트를 초기화(NULL과 0) 해준거다.
초기화 해줌으로써 이제 ll은 빈 리스트가 되었기에 main()에서 removeAllItems()에서도 문제 없이 동작하게 된거다.

---

전체 코드

// main()에서 frontBackSplitLinkedList() 함수를 호출하는 부분만 가져옴
    case 2:
      printf("The resulting linked lists after splitting the given linked list are:\n");
      frontBackSplitLinkedList(&ll, &resultFrontList, &resultBackList); // You need to code this function
      printf("Front linked list: ");
      printList(&resultFrontList);
      printf("Back linked list: ");
      printList(&resultBackList);
      printf("\n");
      removeAllItems(&ll);
      removeAllItems(&resultFrontList);
      removeAllItems(&resultBackList);
      break;

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
  if (ll == NULL || ll->head == NULL || ll->size == 0)
  {
    printf("[ERROR] Cannot split. linked list is empty\n");
    return;
  }

  int mid = (ll->size + 1) / 2;
  ListNode *cur = ll->head;
  ListNode *prev = NULL;

  resultFrontList->head = ll->head;
  resultFrontList->size = mid;

  for (int i = 0; i < mid; i++)
  {
    prev = cur;
    cur = cur->next;
  }

  if (prev != NULL)
    prev->next = NULL;

  resultBackList->head = cur;
  resultBackList->size = ll->size - mid;

  ll->head = NULL;
  ll->size = 0;
}