원형 연결 리스트 circular linked list 삽입(insert) by c

circular linked list는 singly linked list의 tail의 next 포인터 값에 head 값을 추가한 linked list이다.

포인터로는 head값만 두고 있다.

이러한 circular linked list가 정렬돼있는 상태에서 새로운 값이 삽입됐을 때는 크게 3가지 케이스가 있다.

1. 리스트가 비어있는 경우

새로운 노드를 추가하고 Head값과 new node의 next 포인터를 new node로 지정한다.(O(1))

  // Case 1 of the above algo
  if (current == NULL)
  {
     new_node->next = new_node;
     *head_ref = new_node;
  }

2. 새로운 값이 head의 이전에 삽입되는 경우 (head 값을 꾸는 경우)

마지막 노드를 찾는다.(O(n))

마지막 노드의 next 포인터 값을 new node로 바꾼다.(O(1))

new node의 next 포인터를 head로 바꾼다.(O(1))

head를 new_node로 바꾼다.(O(1))

// Case 2 of the above algo
  else if (current->data >= new_node->data)
  {
    /* If value is smaller than head's value then
      we need to change next of last node */
    while(current->next != *head_ref)
        current = current->next;
    current->next = new_node;
    new_node->next = *head_ref;
    *head_ref = new_node;
  }

3. 새로운 값이 head의 이후에 삽입되는 경우

new node의 위치의 이전 노드를 찾는다.(O(n))

new node의 next 포인터를 이전 노드의 next로바꿔준다.(O(1))

이전 노드의 next 포인터를 new_node로 바꾼다.(O(1))

  // Case 3 of the above algo
  else
  {
    /* Locate the node before the point of insertion */
    while (current->next!= *head_ref &&
           current->next->data < new_node->data)
      current = current->next;
 
    new_node->next = current->next;
    current->next = new_node;
  }

 

소스코드 by https://www.geeksforgeeks.org/sorted-insert-for-circular-linked-list/?ref=lbp