5-2 단순 리스트 연산 (삭제, 탐색)

1. 단순 연결 리스트에서의 삭제 연산

① 방법

    - 삭제할 노드의 앞 노드 찾음

    - 앞 노드에 삭제할 노드의 링크 필드 값 저장

    - 삭제할 노드의 앞노드와 삭제할 노드의 다음 노드 연결

 

 

 

 

 - 삭제할 원소 "수욜"의 링크 필드 값을 앞 노드의 링크 필드에 저장

 

 

② 삭제 알고리즘 (포인터old : 삭제할 노드)

    - deleteNode(L,pre) 

               if (L=null) then error;

               else {

                        old <-pre.link

                        if (old = Null) then return;

                        pre.link <- old.link;

                        returnNode(old);

                }

         end deleteNode()

 

 

 

2. 단순 연결 리스트의 노드 탐색 알고리즘

① 노드 탐색 알고리즘

searchNode(L,x)

     temp <-L;

     while (temp≠Null) do { 

                   if (temp.data = x) then return temp;

                   else temp <- temp.link;

     }

     retrun temp;

end searchNode()

 

   - if (temp.data = x) then return temp;

     현재 temp 노드의 데이터 필드 값이 탐색 값 x와 같으면 현재 temp값 리턴하여

     x가 있는 노드 주소를 알려줌!

 

    - while 문에서 x 노드 찾지 못하고 마지막 노드 링크 필드 값인 null이 포인터 temp에 설정되어 while문 수행종료

       현재 포인터의 temp 값인 null 값 반환 : 탐색값 x 가 리스트 L에 없다는 의미이므로 탐색 실패!!

 

 

C언어에서 사용해 연결 리스트를 구현할 때 자기참조구조체, 동적메모리할당, 포인터 개념을 사용한다.