[정보][자료구조] 2014-B-03 연결 리스트

 

 

위 내용은 case별로 나누면 이해하기 쉽다.

1. *head == NULL 인 경우

 : 기존 데이터가 없다.

 : *head = elm 으로 입력

 

2. *head != NULL 인 경우

 : 기존 데이터가 있다.

 1) 일단 초기화 두개의 포인터를 초기화

   prevptr = NULL

   ptr = (*head);

   이전 포인터값은 NULL, 현재 포인터는 (*head)이다.

 2) ptr->id < id 이면 : id의 값이 head보다 크다면

   이전 포인터를 현재 포인터와 자리를 바꾸고, 현재 포인터는 다음 포인터로 변환 검색해야한다.

    prevprt = ptr;

    ptr = prt-next;

 

 3) ptr->id > id 이면 

    처음에 진입한 경우(head의 id 값이 입력값보다 큰경우) 는 prevptr=NULL 이었을 것이다.

    이 경우는 입력값이 head가 되어야 하므로 (*head) = elm;

    그리고 elm->next는 ptr에 연결이 되어야 합니다. elm->next = ptr;

 4) ptr->id > id이나 prevptr !=NULL 인 경우

    prevptr->next = elm; (삽입된 link를 연결해주고)

    elm->next = ptr; (공통)

 

 5) 마지막 ㄷ의 case는  ptr->id < id 였는데, 입력된 id가 last 인경우. 즉 현재 포인터의 next가 elm으로 연결하면 됨.

ptr->next= elm;

 

개념을 알면 쉬운데, 코드를 분석하는데 시간이 꽤 걸렸습니다.

실제 문제가 나오면 쉬운 것은 아닐 것 같네요.

많은 연습이 필요한 문제입니다.