2.2.3 단순 연결 리스트 (Simple linked list)

2.2.3 단순 연결리스트

- 개념 : 하나의 방향으로 연결되어 있으며, 마지막 노드의 링크 필드 값이 NULL인 연결리스트이다.

 

     

 

- 단점

  1) 한 노드에서 이전 노드나 역방향으로 노드를 탐색할 수 없다. (별도의 포인터가 필요하다.)

- 단순연결리스트의 구현

  

  (1) 노드 정의

    1) 노드는 C언어 구조체를 이용하여 정의 된다.

    2) 구조체 안에는 데이터를 저장하는 데이터필드와 포인터인 링크필드가 있다.

    3) 노드의 구조가 구조체를 이용하여 정의 되었지만, 아직 노드는 생성되지 않았다는 것을 주의 해야 한다.

 

  (2) 노드 생성

 

    1) 연결 리스트에서는 필요할 때 마다 동적 메모리 할당을 이용해 노드를 동적으로 생성한다.

    2) 그림의 코드에서는 임시 포인터 변수 p1을 만들고, malloc 함수를 이용하여 노드의 크기만큼 

        메모리를 할당 받는다.

    3) 이 할당된 메모리가 노드가 되는 것이다.

    4) 옆의 코드가 실행되면 그림처럼 노드가 생성되고, p1이 노드를 가리킨다. 

       하지만 아직 노드에는 아무것도 채워지지 않았다는 걸 유의하라.

   

      (2.1) 노드 생성

    

     

    

       1) 다음순서는 만들어진 노드에 데이터를 저장하고 링크 필드를 NULL로 설정한다.

       2) p1->data = 10, p1->link = NULL ; 실행시 옆의 그림과 같이 된다.

 

     

    (3) 노드 삭제

       1) 사용이 끝났다면 반드시 사용한 메모리를 해제해 주어야 한다.

       2) p1의 메모리 공간을 해제할 경우 free(p1); 의 코드를 추가해주면 된다.

 

 

- 단순연결리스트의 삽입 연산

(1) 삽입을 위한 변수

     

 

1) ListNode *head : 첫번째 노드를 가리키는 헤드 포인터이다.

2) phead는 헤드포인터 head에 대한 포인터다. 헤드포인터의 포인터를 전달한 이유는 함수 안에서 

   헤드포인터를 변경해야 하기 때문이다.

 

 

(2) head가 NULL인 경우의 삽입( == 리스트가 비어있을 경우)

       

            

 

  1) head가 NULL이라면 현재 삽입하려는 노드가 첫 번째 노드가 된다. 

      따라서 head의 값만 변경하면 된다.

 

 

 

 

(3) p가 NULL인 경우 (== 리스트에 노드 들이 있고, 삽입할 노드가 리스트 맨 앞에 삽입될 경우)

          

 

         1) 선행 노드 p가 NULL 값일 때는 리스트의 맨 앞에 삽입한다.

         2) 먼저 new_node의 link가 head와 같은 값을 갖도록 한다.

         3) 다음에 head가 new_node를 가리키도록 한다.

 

   (4) head와 p가 NULL이 아닌 경우 (== 노드들의 중간에 삽입할 경우)

    

   

 

           1) 가장 일반적인 경우이다.

           2) new_node의 link에 p->link값을 복사한다.

           3) 그 다음 p->link가 new_node를 가리키도록 한다.

(5) 단순 연결 리스트의 삽입 함수코드

  

 

 

 

 

- 단순 연결 리스트의 삭제 연산

  

  (1) 삭제를 위한 변수

 

  (2) p가 NULL 인 경우 삭제 (== 선행노드가 없는 경우)

            1) 연결리스트의 첫 번째 노드를 삭제한다.

            2) 헤드 포인터를 변경하고 removed 노드가 차지하고 있는 메모리 공간을 시스템에 반환한다.

 

     

(3) p가 NULL이 아닌 경우 삭제(== 선행노드가 존재하는 경우)

   

      

   

         1) 먼저 removed 앞의 노드인 p의 링크가 removed 다음 노드를 가리키도록 변경한다.

         2) 추가적으로 removed 노드가 차지하고 있는 공간을 시스템에 반환한다.

 

    (4) 단순 연결 리스트의 삭제 함수 코드

 

        

 

 

- 단순 연결리스트의 데이터 출력 연산

     

  (1) 반복문을 이용한 리스트 출력 코드                  (2) 순환함수를 이용한 리스트 출력 코드

    

          1) 노드를 순차적으로 방문하는 알고리즘이다.

          2) 노드의 링크 값이 NULL이 아니면 계속 다음 링크를 방문하며 화면에 노드의 데이터값을 출력한다.

          3) 링크 값이 NULL이면 연결리스트 끝이므로 반복을 중단한다.

 

- 단순 연결리스트의 노드 값 탐색 연산

 

 

 

 

- 단순 연결리스트 응용 연산

(1) 2개 단순 연결 리스트를 1개의 단순연결 리스트로 만드는 연산

 

 

 

      1) 먼저 첫 번째 리스트의 맨 끝으로 간다.

      2) 첫 번째 리스트의 마지막 노드의 링크가 두 번째 리스트의 맨 처음 노드를 가리키도록 변경한다.

      3) 주의할 점은 head1이나 head2가 NULL일 경우를 반드시 처리해주어야 한다.

 

 

 

 

(2) 단순 연결 리스트의 링크를 역순으로 만드는 연산

 

    

 

       1) 이 연산에서는 세개의 포인터 p, q, r을 사용한다. (포인터의 이름은 상관 X, 역할이 중요하다.)

       2) p, q, r 포인터를 이용하여 연결 리스트를 순회하며 링크의 방향을 역순으로 바꾸면 된다.

       3) 주의할 점은 링크의 방향을 역순으로 바꾸기 전에 다음에 역순으로 바꿀 노드를 미리 기억해야 한다.

   

            p : 아직 역순으로 바뀌지 않은 노드

            q : 현재 역순으로 만들 노드

            r : 이미 역순으로 변경된 노드