리스트 - 단순 연결 리스트(Simply Linked List)

단순 연결 리스트

  - 하나의 링크 필드에 의해 각 노드들이 순차적으로 연결된 연결리스트 

화살표로 표시된 각 노드의 링크 필드는 실제 다음 노드에 대한 메모리 주소 값을 갖는 포인터.

마지막 노드의 링크 필드는 더 이상의 연결된 노드가 없음을 의미하기 위해 NULL값으로.

첫번째 노드를 가리키는 포인터 변수인 list_ptr이 이 리스트에 대한 이름으로서 사용.

 

단순 연결 리스트의 생성

① malloc()함수를 이용하여 하나의 노드에 대한 메모리를 할당한다.

② 리스트의 이름을 나타내는 포인터 변수가 생성된 노드를 가리키게 한다.

③ 생성된 노드의 링키 필드의 값을 NULL로 설정한다.

④ 생성된 노드의 데이터 필드를 해당 값으로 설정한다.

 

연결리스트에서의 노드 구조체 정의

typedef struct node_type *node_ptr; typedef struct node_type {     int data;     node_ptr link; }; node_ptr list_ptr = NULL;

 

1-노드 단순 연결 리스트의 생성

node_ptr CreateSingleLinkedList() {     node_ptr ptr;     ptr = (node_ptr)malloc(sizeof(node_ptr));    //과정 ①, ②     ptr->link = NULL;                                     //과정 ③     ptr->data = 10;                                        //과정 ④     return ptr; }   int main(void) {         :         :     list_ptr = CreateSingleLinkedList();         :         : }

 

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

① 연결 리스트 list_ptr에서 새로운 노드가 삽입될 위치의 이전에 있는 노드를 검색한다.

    이때 검색된 노드에 대한 포인터를 pre_node라 한다.

② 삽입될 노드에 대한 메모리 공간을 할당하고 이 노드에 대한 포인터를 new_node라 한다.

③ new_node의 데이터 필드를 해당 값으로 설정한다.

④ new_node의 링크 필드를 pre_node의 링크 필드의 값으로 설정한다.

⑤ pre_node의 링크 필드가 new_node를 가리키게 한다.

node_ptr Search_Pre_Node(node_ptr ptr, int value) {     /* ptr의 리스트에서 value 값을 갖는 노드를 찾아 해당 노드가 존재하면 NULL포인터를 반환        해당 노드가 존재하지 않는다면 바로 이전의 값을 갖는 노드에 대한 포인터를 반환 */ }   node_ptr insert(node_ptr *ptr, node_ptr ptr_node, int value) {     /*  (*ptr)이 가리키는 리스트의 pre_node 뒤에 value의 값을 갖는 새로운 노드 삽입 */         node_ptr new_node;     new_node = (node_ptr)malloc(sizeof(node_ptr));    // 과정 ②     new_node->data = value;                                    // 과정 ③         if(*ptr)   // 공백 리스트가 아닐 경우             {         new_node->link = pre_node->link;                    // 과정 ④         pre_node->link = new_node;                            // 과정 ⑤     }     else    // 공백 리스트일 경우     {         new_node->link = NULL;                                  // 과정 ④         *ptr = new_node;                                             // 과정 ⑤     } }     int main(void) {         :     node_ptr = temp = Search_Pre_Node(list_ptr, 30);     if(*temp) insert(&list_ptr, temp, 30);         : }

위 프로그램에서 추가로 고려할 사항은 리스트가 공백일 경우와 그렇지 않은 경우를 나누어서 처리했다는 점이다.

위의 insert() 함수에는 하나의 제한 사항이 존재한다. 새로운 노드가 리스트의 앞에 삽입될 수 없다는 점이다.

이 문제는 리스트의 처음에 새로운 노드를 삽입하기 위한 새로운 함수를 정의하거나,

리스트에 헤드노드(head node)를 추가하는 방법으로 해결할 수 있다.

헤드노드는 리스트의 시작점만을 나타내기 위해 사용되는 노드로서 데이터 필드에는 값을 갖지 않으며

헤드노드의 링크 필드가 실제 리스트에 대한 포인터 즉, 시작점을 갖는다.

 

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

① 연결 리스트 list_ptr에서 삭제될 노드를 node라 하고, node의 선행 노드를 pre_node라 하자.

    (node가 첫 번째 노드이면 pre_node는 NULL)

② node가 첫 번째 노드가 아니라면, pre_node의 링크가 node의 링크가 가리키는 노드(node의 다음노드)를 가리키도록 하고,

③ node가 첫 번째 노드라면, list_ptr가 node의 다음 노드를 가리키게 한다.

④ free()함수를 이용하여 node에 할당된 메모리를 해제한다.

void delete(node_ptr *ptr, node_ptr ptr_node, node_ptr node) {     /* (*ptr) : 리스트에 대한 포인터         pre_node : 삭제될 노드의 선행 노드에 대한 포인터         node : 삭제될 노드에 대한 포인터  */     if(pre_node)                                 //선행 노드가 존재할 경우 : 과정 ②     {         pre_node->link = node->link;     }     else                                            //첫 번째 노드가 삭제될 경우 : 과정 ③     {         *ptr = (*ptr)->link;     }         free(node);                                 //node에 할당된 메모리 해제 : 과정 ④ }