[C언어]42일차-스택 링크드 리스트로 구현해보기(이것이 C언어 자료구조 알고리즘이다)

 

[C언어]42일차 - 스택 - 링크드 리스트로 구현해보기

 

 

#include <string.h>
#include <stdlib.h>
#include <stdio.h>




/*
 링크드 리스트로 구현한 스택은 배열과 달리 인덱스를 활용해서 노드에 접근할 수 없다.
 따라서 링크드 리스트로 스택을 구현하려면 노드는 자신의 위에 위치하는 노드에 대한 포인터를 갖고 있어야 한다.
 */
typedef struct _Node{        //int나 double 같은 기본 자료형이라면 '값복사'를 통해 데이터를 담는다.
    char* Data;              //char* 형은 포인터이기 때문에 문자열이 저장된 주소만 담을 수 있다.
    struct _Node *NextNode;  //자기 위에 쌓여 있는 노드의 주소를 가리킨다.
} Node;

typedef struct _LinkedListStack{
    
    Node *Top;          //이 링크드 리스트의 꼬리를 가리킨다.(제일 마지막)
                        //즉, Top 포인터는 스택의 입출력이 이루어지는 최상위 노드에 대한 포인터다.
    Node *List;         //List 포인터는 데이터를 담는 링크드 리스트를 가리키고
}LinkedListStack;


void createStack(LinkedListStack** Stack);
void destroyStack(LinkedListStack** Stack);


Node* createNode(char* Data);
void destroyNode(Node* _Node);


void push(LinkedListStack* Stack, Node* NewNode);
Node* pop(LinkedListStack* Stack);


Node* top(LinkedListStack* Stack);
int getSize(LinkedListStack* Stack);
int isEmpty(LinkedListStack* Stack);


//MARK: 스택생성
void createStack(LinkedListStack** Stack){
    //LinkedListStack의 메모리 공간 생성
    (*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));
    (*Stack)->Top = NULL;
    (*Stack)->List = NULL;
}

//MARK: 스택소멸
void destroyStack(LinkedListStack* Stack){
    
    Node* Current = (Stack)->List;
    while (Current->NextNode != (Stack)->Top) {
        Node* TempNode = Current;
        Current = Current->NextNode;
        free(TempNode);
    }
    free((Stack)->Top);
    free((Stack));
}

//MARK: 노드 생성
Node* createNode(char* Data){
    Node* newNode = (Node*)malloc(sizeof(Node));                //Node 힙공간 생성
    newNode->Data = (char*)malloc(sizeof(strlen(Data) + 1));    //Node 안의 Data힙공간 생성
    strcpy(newNode->Data, Data);
    newNode->NextNode = NULL;
    return newNode;
}

//MARK: 노드 소멸
void destroyNode(Node* _Node){
    free(_Node->Data);
    free(_Node);
}

//MARK: push
void push(LinkedListStack* Stack, Node* NewNode){
    
    //만약 스택의 List가 비었으면
    if (Stack->List == NULL) {
        
        Stack->List = NewNode;
        
    //아니면 그 위에 쌓는다.
    }else{
        Stack->Top->NextNode = NewNode;
    }
    Stack->Top = NewNode;
}

//MARK: pop
Node* pop(LinkedListStack* Stack){
    
    if (isEmpty(Stack)) {
        printf("스택이 비었습니다.\n");
        return NULL;
    }
    
    //함수가 반환할 최상위 노드
    Node* top = Stack->Top;
    
    
    //헤드가 Top일 경우
    if (Stack->List == Stack->Top) {
        Stack->List = NULL;
        Stack->Top = NULL;
        
    }else{
        
        Node* Current = Stack->List;
        while (Current->NextNode != Stack->Top) {
            Current = Current->NextNode;
        }
        
        Stack->Top = Current;
        Stack->Top->NextNode = NULL;
    }
    
    return top;
}



//MARK: top
Node* top(LinkedListStack* Stack){
    if (isEmpty(Stack)) {
        printf("스택이 비었습니다.\n");
        return NULL;
    }
    return Stack->Top;
}

//MARK: getSize
int getSize(LinkedListStack* Stack) {
    
    int cnt = 0;
    
    Node* current = Stack->List;
    while (current != NULL) {
        cnt += 1;
        current = current->NextNode;
    }
    return cnt;
}

//MARK: isEmpty
int isEmpty(LinkedListStack* Stack){
    return Stack->Top == NULL;
}



//MARK: main
int main(int argc, const char * argv[]) {
    

    LinkedListStack *Stacks = NULL;
    
    createStack(&Stacks);

    push(Stacks, createNode("abc"));
    push(Stacks, createNode("def"));
    push(Stacks, createNode("efg"));
    push(Stacks, createNode("hij"));
    
    printf("cnt 값: %d\n" , getSize(Stacks));
    printf("node pop 값: %s\n" , pop(Stacks)->Data);


    printf("cnt 값: %d\n" , getSize(Stacks));
    printf("node pop 값: %s\n" , pop(Stacks)->Data);
    printf("node pop 값: %s\n" , pop(Stacks)->Data);
    printf("node pop 값: %s\n" , pop(Stacks)->Data);
    
    return 0;
}

 

출력

     cnt 값: 4
     node pop 값: hij
     cnt 값: 3
     node pop 값: efg
     node pop 값: def
     node pop 값: abc

 

 

1) 주요 문제점 요약 (중요)

 

1. createNode에서 메모리 할당 오류
   • malloc(sizeof(strlen(Data) + 1)) — sizeof를 잘못 사용했습니다. sizeof(strlen(...)+1)는 상수 크기(예: size_t의 크기)를 반환합니다.
   • 결과: 너무 작은 메모리 할당 → strcpy에서 버퍼 오버플로우 / UB 발생.
2. destroyStack 구현이 잘못되어 안전하지 않음
   • Node* Current = Stack->List; while (Current->NextNode != Stack->Top) { ... } 처럼 작성했는데 Current 또는 Current->NextNode가 NULL이면 바로 크래시.
   • 스택이 비어있거나 노드가 1개일 때 동작하지 않음.
   • 올바른 방법은 while (current != NULL) { next = current->NextNode; free(current); current = next; }.
3. pop 사용 방식으로 인한 메모리 누수 / 소유권 모호성
   • pop(Stacks)->Data로 바로 사용하면 반환된 Node*를 free할 기회를 잃습니다(메모리 누수).
   • 누가 free할지 명확하게 설계되어야 합니다. (pop이 노드를 반환하고 호출자가 destroyNode()로 해제할지, pop이 Data 포인터만 반환하고 호출자가 free()할지 등)
4. 비효율: Top을 리스트의 꼬리(tail)로 관리
   • 현재 설계는 List(head)부터 끝까지 traversal해서 Top을 찾거나 Top 이전 노드를 찾습니다. pop에서 while (Current->NextNode != Stack->Top)과 같은 O(n) 작업이 필요합니다.
   • 스택은 LIFO이므로 **head(리스트의 시작)를 Top으로 삼아 push/pop을 O(1)**로 구현하는 것이 일반적이고 더 효율적입니다.
5. NULL 체크 부족
   • 대부분 함수가 Stack == NULL 또는 Data == NULL 같은 인자 체크를 하지 않음 — 예외 케이스에서 크래시가 날 수 있음.
6. 메모리 할당 실패 처리 없음
   • malloc 반환값을 항상 확인해야 합니다.

---

2) 핵심 권고

 

• createNode는 malloc(strlen+1) 또는 strdup을 사용해 문자열을 복사(깊은 복사)하라.
• 스택 구현은 Top을 리스트의 head로 두고 push/pop을 head에서 수행하라(간단하고 O(1)).
• pop의 소유권을 명확히: pop은 char*(데이터 포인터)를 반환하고 호출자가 free() 하도록 하거나, pop이 Node*를 반환해 호출자가 destroyNode()로 해제하게 하라.
• destroyStack은 모든 노드를 순회하며 안전하게 free 하라.
• 모든 malloc 결과와 인자(null) 체크를 추가하라.

 

3) 구현: (A) 당신 코드의 버그를 바로잡은 버전 (원래 tail 기반 방식 유지)

 

— tail(끝)을 Top으로 유지하는 방식의 최소수정판입니다. 비효율(O(n) pop) 은 그대로지만 기존 API(Top/ List 필드, push/pop 반환 Node*) 호환됩니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Node{
    char* Data;
    struct _Node* NextNode;
} Node;

typedef struct _LinkedListStack{
    Node *Top;   // tail (최상위)
    Node *List;  // head
} LinkedListStack;

void createStack(LinkedListStack** Stack){
    if (!Stack) return;
    *Stack = malloc(sizeof(LinkedListStack));
    if (!*Stack) return;
    (*Stack)->Top = NULL;
    (*Stack)->List = NULL;
}

void destroyNode(Node* n){
    if (!n) return;
    free(n->Data);
    free(n);
}

Node* createNode(const char* Data){
    if (Data == NULL) return NULL;
    Node* newNode = malloc(sizeof(Node));
    if (!newNode) return NULL;
    size_t len = strlen(Data);
    newNode->Data = malloc(len + 1);
    if (!newNode->Data) { free(newNode); return NULL; }
    memcpy(newNode->Data, Data, len + 1);
    newNode->NextNode = NULL;
    return newNode;
}

void push(LinkedListStack* Stack, Node* NewNode){
    if (!Stack || !NewNode) return;
    NewNode->NextNode = NULL;
    if (Stack->List == NULL){
        Stack->List = NewNode;
    } else {
        Stack->Top->NextNode = NewNode;
    }
    Stack->Top = NewNode;
}

Node* pop(LinkedListStack* Stack){
    if (!Stack || Stack->Top == NULL) return NULL;
    Node* top = Stack->Top;
    if (Stack->List == top) {
        // 한 개 남은 경우
        Stack->List = Stack->Top = NULL;
    } else {
        Node* cur = Stack->List;
        // 안전하게 이전 노드 검색
        while (cur && cur->NextNode != top) cur = cur->NextNode;
        if (cur) {
            cur->NextNode = NULL;
            Stack->Top = cur;
        } else {
            // 이상 상황 (일관성 깨짐), 비어있는 것으로 처리
            Stack->List = Stack->Top = NULL;
        }
    }
    // 반환하는 쪽(호출자)이 destroyNode()로 해제하도록 규정
    return top;
}

int getSize(LinkedListStack* Stack){
    if (!Stack) return 0;
    int cnt = 0;
    Node* cur = Stack->List;
    while (cur){ cnt++; cur = cur->NextNode; }
    return cnt;
}

int isEmpty(LinkedListStack* Stack){
    return (Stack == NULL || Stack->Top == NULL);
}

void destroyStack(LinkedListStack* Stack){
    if (!Stack) return;
    Node* cur = Stack->List;
    while (cur){
        Node* nxt = cur->NextNode;
        destroyNode(cur);
        cur = nxt;
    }
    free(Stack);
}

/* 사용 예시 */
int main(void){
    LinkedListStack* s = NULL;
    createStack(&s);

    push(s, createNode("abc"));
    push(s, createNode("def"));
    push(s, createNode("ghi"));

    printf("size=%d\n", getSize(s));

    Node* n = pop(s);
    if (n) { printf("pop: %s\n", n->Data); destroyNode(n); }

    while (!isEmpty(s)) {
        Node* m = pop(s);
        if (m) { printf("pop: %s\n", m->Data); destroyNode(m); }
    }

    destroyStack(s);
    return 0;
}

 

주의: 이 버전은 pop이 Node*를 반환하므로 호출자가 destroyNode()로 해제해야 합니다.

 

 

4) 권장 구현: 

Top을 head로

 — 더 간단하고 빠른 방식 (O(1) push/pop)

 

— 실무/학습 모두에서 권장됩니다. List 포인터도 불필요하니 제거했습니다. push/pop 모두 O(1)이고 코드가 간결합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Node {
    char* Data;
    struct _Node* Next;
} Node;

typedef struct {
    Node* Top; // head가 Top
} LinkedListStack;

void createStack(LinkedListStack** st){
    if (!st) return;
    *st = malloc(sizeof(LinkedListStack));
    if (!*st) return;
    (*st)->Top = NULL;
}

Node* createNode(const char* s){
    if (!s) return NULL;
    Node* n = malloc(sizeof(Node));
    if (!n) return NULL;
    size_t L = strlen(s);
    n->Data = malloc(L+1);
    if (!n->Data) { free(n); return NULL; }
    memcpy(n->Data, s, L+1);
    n->Next = NULL;
    return n;
}

void destroyNode(Node* n){
    if (!n) return;
    free(n->Data);
    free(n);
}

void push(LinkedListStack* st, const char* s){
    if (!st) return;
    Node* n = createNode(s);
    if (!n) return; // 할당 실패 처리 (단순히 무시)
    n->Next = st->Top;
    st->Top = n;
}

// pop은 char*를 반환하고 호출자가 free() 하도록 설계
char* pop(LinkedListStack* st){
    if (!st || !st->Top) return NULL;
    Node* n = st->Top;
    st->Top = n->Next;
    char* data = n->Data; // 소유권 이전 (문자열 포인터 반환)
    free(n);              // 노드 구조체만 해제
    return data;
}

int isEmpty(LinkedListStack* st){ return st == NULL || st->Top == NULL; }

void destroyStack(LinkedListStack* st){
    if (!st) return;
    Node* cur = st->Top;
    while (cur){
        Node* nxt = cur->Next;
        free(cur->Data);
        free(cur);
        cur = nxt;
    }
    free(st);
}

/* 사용 예 */
int main(void){
    LinkedListStack* s = NULL;
    createStack(&s);
    push(s, "one");
    push(s, "two");
    push(s, "three");

    char* v;
    while ((v = pop(s)) != NULL) {
        printf("pop: %s\n", v);
        free(v); // pop이 반환한 포인터를 해제
    }
    destroyStack(s);
    return 0;
}

장점: push/pop 모두 O(1), 구현 간결, 메모리 소유권이 명확(노드 구조체는 내부에서 해제, 문자열 포인터는 pop 호출자가 해제).

 

 

5) 추가 팁 (마무리)

 

• API 규약을 문서화: 누구(함수)가 할당하고 누구가 해제하는지 명확히 해두세요. (예: pop()은 문자열 포인터 소유권을 호출자에게 넘긴다.)
• strdup 사용 가능 환경이면 간단히 쓰세요 (newNode->Data = strdup(Data);) — 단, strdup도 NULL 체크 필요.
• 테스트 케이스: 빈 스택, 한 원소 스택, 여러 원소 스택, NULL 인자 테스트를 자동화하세요.
• 메모리 도구: valgrind 같은 도구로 메모리 누수/오류 검사하세요.