C 언어 코딩 도장: Linked list에 관해 이야기 드릴것이 있습니다.

FAQ

Linked list에 관해 이야기 드릴것이 있습니다.

우선 제가 도움받은 것에 대해 감사드린다는 말을 하고 싶네요. 덕분에 도움 많이 되었습니다. 앞으로 이야기 할 것은 저만의 착각일 수도 있으니 한번 검토해보시길 바랍니다.

Linked list에서 아래 부문의 동작이 잘못되었다고 생각이 드네요.

https://dojang.io/mod/page/view.php?id=647

while (curr != NULL)    // 포인터가 NULL이 아닐 때 계속 반복
    {
        struct NODE *next = curr->next; // 현재 노드의 다음 노드 주소를 임시로 저장
        free(curr);        // 현재 노드 메모리 해제
        curr = next;       // 포인터에 다음 노드의 주소 저장
    }

Visual Studio의 기능 중 Debug 를 통해 내부적인 흐름을 관찰하였는데, 위의 부문에서 의도하는 동작을 하지 않았습니다. 자세한 내용은 아래 압축 File에서 result 1, 2를 참고해주세요.

본래라면 result 3, 4, 5처럼 되야 정상인데, 반복문이 의미없이 동작합니다. (직접 Debug를 해보시길 바랍니다.) Linked list 특성상 이전 Node를 경유할 수 없습니다. 때문에 매번 마지막 Node를 찾아 제거하거나 아래 Algorithm과 같이 원하는 위치의 Node를 찾아 제거하는 방법으로 해야 합니다.

struct List_Node_Type* Pointer_Node = NULL;

Pointer_Node = (struct List_Node_Type*) &Pointer_List->Header_Node;

int index = 0;

for (index = 0; index < position; index++) {

Pointer_Node = (struct List_Node_Type*)Pointer_Node->Pointer_Link;

}

struct List_Node_Type* Pointer_Delete_Node = NULL;

Pointer_Delete_Node = (struct List_Node_Type*) Pointer_Node->Pointer_Link;

Pointer_Node->Pointer_Link = (struct List_Node_Type*)Pointer_Delete_Node->Pointer_Link;

free((struct List_Node_Type*)Pointer_Delete_Node);

Colored by Color Scripter

가장 상단의 Algorithm은 첫 번째 Node를 제거하고 다음 Node를 제거하는 방식으로 의도됩니다. 하지만 첫 Node를 제거하는 순간 다음 노드의 접점은 사라지게 됩니다 .따라서 가장 선두의 Node만 Memory 해제될 뿐 그 후의 Node는 제거되지 않습니다.

이상진의 자료구조 책을 참고하여 제가 따로 Linked list를 만든 Blog가 있습니다.

https://breakinformation-byr.blogspot.com/2019/09/linked-list-alpha.html

한번 비교해보시기 바랍니다. 감사합니다.

예제 코드의 동작은 잘못되지 않았고, C 언어에서 전형적으로 작성하는 코드입니다.

블로그의 링크한 것처럼 remove 동작이 복잡하게 작성될 이유는 없습니다.

예제 코드를 보면 처음에 3개의 노드를 추가하고, 각각의 값은 10, 20, 30입니다. 스택 프레임으로 보면 알 수 있습니다.

예제에서 마지막에 추가한 노드 30을 삭제합니다. 삭제한 이후는 다음과 같습니다.

이후에 문의한 while 반복문에서 나머지 노드를 삭제합니다.

우선 반복문에서 노드 하나를 삭제한 모습입니다. data가 20인 노드가 삭제되었습니다.

free(curr)을 한 직후이므로 왼쪽 main 스택에서 curr은 어떤 것도 가리키지 않게 됩니다. 쓰레기 값이 들어가 있으므로 여기서는 똥 아이콘으로 표시하고 있습니다.

while 반복문의 마지막 코드인 curr = next를 실행한 결과입니다. curr이 쓰레기 값에서 연결 리스트의 노드를 가리키는 것으로 표시됩니다.

모든 노드를 삭제한 이후에는 다음과 같이 됩니다.

마지막 head 노드를 free로 메모리를 해제하면 완전히 사라집니다.

addFirst는 head 노드 뒤에 새 노드를 추가하고 있습니다.

head -> 10

에서 새 노드 20을 head 노드 뒤에 추가하면

head -> 20 -> 10이 됩니다.

스택 프레임에서는 20 노드가 가장 아래에 그려지고, head는 가장 아래에 있는 20 노드를 가리키게 됩니다.

메모리를 해제했을 때 다음 노드의 접점이 사라지지 않게 하기 위해

*next = curr -> next;에서 먼저 다음 노드 위치를 저장하고,

free(curr)로 현재 노드를 해제하고

curr = next;로 다음 노드의 위치를 저장합니다.

메모리 해제 동작에도 문제는 없습니다.

C 언어 스택 프레임 시각화로 동작을 하나씩 살펴보기 바랍니다.

http://pythontutor.com/c.html

연결 리스트를 구현하는 방식은 여러 가지가 있습니다.

head의 next를 처음 추가한 node에 고정하는 방식이 있고,

next가 마지막에 추가한 node를 가리키는 방식도 있습니다.

항상 마지막에 추가한 요소를 가리키기 때문에 삽입과 삭제를 빠르게 할 수 있습니다.

head의 next가 처음 추가한 node에 고정되어 있으면

head -> 10 -> 20 -> 30 순서로 순회하게 되고,

head의 next가 마지막에 추가한 node로 변동하게 되면

head -> 30 -> 20 -> 10 순서로 순회하게 됩니다.

Last In, First Out(LIFO)로 구현한다면 마지막에 들어간 node가 먼저 나오게 되니까

head -> 30 -> 20 -> 10으로 구현하게 됩니다.

보통 스택 구조는 LIFO 구조이고, 여러 구현에서는 스택 구조를 빈번하게 사용하기 때문에 연결 리스트는 LIFO 구조로 구현하는 게 일반적입니다.

First in, First Out(FIFO)로 구현한다면 처음 들어간 요소가 먼저 나오게 됩니다. 이럴 때는

head -> 10 -> 20 -> 30으로 구현하고,

head가 가리키는 첫 번째 원소 10을 꺼낸 후에는

head -> 20 -> 30으로 바뀌게 구현해야 합니다.

보통 리스트를 순회하며 마지막 노드를 삭제하는 코드를 구현하지 않습니다.

head -> 10 -> 20 -> 30 구조에서

30을 삭제, 20을 삭제, 10을 삭제하는 구조로 node를 꺼낼 때마다 전체 리스트를

순회하는 것은 비효율적이므로 LIFO 구조로 구현하게 됩니다.

따라서 목적에 따라 FIFO, LIFO에 따라 연결 리스트를 구현하게 되는데,

리스크를 순회하며 마지막 노드를 제거하는 코드는 그렇게 사용 빈도가 높은 코드는 아닙니다. 실무라면 FIFO, LIFO 중에 선택하겠죠.

FIFO 구조는 보통 큐(queue) 구현에 사용되고, 이는 버퍼, 스트리밍 등에 사용됩니다.

다시 분석해보니 제가 틀렸네요 ㅎㅎ;; (예전에 공부를 했었는데, 갑자기 다시 보니까 이상해서 올렸습니다.)

저는 head node를 끊고 메모리 해지하는 것이 문제라고 생각했는데, 저의 고정관념을 부숴버리는 코드였네요. head node와 그 이후의 node를 서로 분리하여 각각 memory를 해제하는 방식이 새롭네요. 제 코드에도 적용시켜 봐야겠습니다. ㅎㅎ

C 언어 코딩 도장 생략내비게이션 생략