Review 6 - Linked list in C

https://eglife.tistory.com/79

Review 5 - Dynamic(Structure) in C

REVIEW 5

Stack은 Array 형태, Heap은 위에서 아래로 내려오는 memory이고(memory주소가 작아지는 방향) Linked list같은 것들을 user가 manual하게 할당한다. 즉, free하기 전에 Heap에 있는 memory는 사라지지 않아서 free하는 걸 잊으면 안 된다.

 

malloc은 input으로 memory size를 받고 output으론 그 memory에 접근 가능한 Pointer를 return한다.

 

기본적으로 void* 의 ptr을 return 하니까, User가 int인지 float인지 각자 적절하게 Pointer type을 선언해서 받아야 하며 이 Pointer를 마지막에 free해줘야 한다.

 

C에선 Python과 달리 Class가 없고 대신에 Structure가 있다.

 

이 Structure에는 method를 선언할 순 없지만, 다양한 type의 variable을 묶어서 관리할 수 있다.

 

이러한 Structure로 C에서 Linked List를 만들어보려고 한다.

 

 

1. Linked list in C

 

addFirst를 할 때마다, 우리는 malloc 함수를 써서 새로운 놈을 선언해줘야 한다.

 

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

typedef struct nodeType LinkedNode;

struct nodeType{
    int val;
    LinkedNode *next; //typedef 선언
};

LinkedNode *createNode(int x){ //node를 가르키는 pointer반환,python에서 __init__에 해당하던 내용,여기까지가 Node 만드는 과정
    LinkedNode *newNode;
    newNode = (LinkedNode*)malloc(sizeof(LinkedNode)); //malloc 중요!
    newNode->val = x;
    newNode->next = NULL;
    return newNode;
}

typedef struct listType SLList;

struct listType{
    LinkedNode *first;
    int size;
};



void addFirst(SLList*LL,int x);
int getFirst(SLList*LL);
int getSize(SLList*LL);
void printSLList(SLList*LL);


int main(void){

    SLList myLL = {NULL, 0};
    printf("gf:%d\n",getFirst(&myLL));

    addFirst(&myLL,10);
    addFirst(&myLL,11);

    
    printf("after add gf:%d\n",getFirst(&myLL));
    printf("gs:%d\n",getSize(&myLL));
    printSLList(&myLL);

    return 0;
}

void addFirst(SLList*LL,int x){
    LinkedNode *newFirst = createNode(x);
    newFirst->next = LL->first;
    LL->first = newFirst;
    LL->size ++;
}

int getFirst(SLList*LL){
    if(LL->first == NULL) return -1;
    return LL->first->val;
}

int getSize(SLList*LL){
    return LL->size;
}

void printSLList(SLList*LL){
    LinkedNode *temp = LL->first;
    while(temp){
        printf("%d->",temp->val);
        temp = temp->next;
    }
    printf("END\n");
}
/*
gf:-1
after add gf:11
gs:2
11->10->END
*/

 

Python에서의 linked list와 logic은 같다.

 

그런데 이제 newNode를 만들어줄 때, malloc을 쓰는 법 그리고 struct를 써주는 것, 그리고 python에서 __init__ method를 일일히 Function으로 만들어주는 것이 다르다.

 

일단 Insert기능! addFirst와 getFirst, getSize를 한 번 만들어봤다.

 

 

2. Delete a node from SSList ( Search기능까지 자동으로 필요함 )

 

Delete 구현은 좀 복잡하다. 나는 이렇게 해봤다.

 

자동으로 Search 기능까지 쓰게 됨!

 

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

typedef struct nodeType LinkedNode;

struct nodeType{
    int val;
    LinkedNode *next; //typedef 선언
};

LinkedNode *createNode(int x){ //node를 가르키는 pointer반환,python에서 __init__에 해당하던 내용,여기까지가 Node 만드는 과정
    LinkedNode *newNode;
    newNode = (LinkedNode*)malloc(sizeof(LinkedNode)); //malloc 중요!
    newNode->val = x;
    newNode->next = NULL;
    return newNode;
}

typedef struct listType SLList;

struct listType{
    LinkedNode *first;
    int size;
};



void addFirst(SLList*LL,int x);
int getFirst(SLList*LL);
int getSize(SLList*LL);
void printSLList(SLList*LL);

//Implementatino of Deletion
LinkedNode* searchNode(SLList*LL,int x);
void deleteNode(SLList*LL,int x);

int main(void){

    SLList myLL = {NULL, 0};
    deleteNode(&myLL,999);
    printSLList(&myLL); //1
    addFirst(&myLL,10);
    printSLList(&myLL); //2
    addFirst(&myLL,11);

    printSLList(&myLL); //3
    addFirst(&myLL,15);
    addFirst(&myLL,7);   

    printSLList(&myLL); //4
    deleteNode(&myLL,100);
    printSLList(&myLL); //5

    deleteNode(&myLL,11);
    printSLList(&myLL); //6

    addFirst(&myLL,99);   
    deleteNode(&myLL,7);
    printSLList(&myLL); //7


    return 0;
}

void addFirst(SLList*LL,int x){
    LinkedNode *newFirst = createNode(x);
    newFirst->next = LL->first;
    LL->first = newFirst;
    LL->size ++;
}

int getFirst(SLList*LL){
    if(LL->first == NULL) return -1;
    return LL->first->val;
}

int getSize(SLList*LL){
    return LL->size;
}

void printSLList(SLList*LL){
    LinkedNode *temp = LL->first;
        printf("size:%d, first:%d, allvals: ",getSize(LL),getFirst(LL));
    while(temp){
        printf("%d->",temp->val);
        temp = temp->next;
    }
    printf("END\n");
}


LinkedNode* searchNode(SLList*LL,int x){
    
    LinkedNode* temp = LL->first;
    while(temp){
        if(temp->val == x){
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}
void deleteNode(SLList*LL,int x){
    LinkedNode *temp = LL->first;
    LinkedNode *prev = NULL;
    
    while(temp){
        
        if(temp == searchNode(LL,x)){
            prev->next = temp->next;
            temp->next = NULL;
            free(temp);
            LL->size--;
            return;
        }
        prev = temp;
        temp = temp->next;
    }
    return;
}
/*
좀 다양하게 print로 출력해봤다.

size:0, first:-1, allvals: END
size:1, first:10, allvals: 10->END
size:2, first:11, allvals: 11->10->END
size:4, first:7, allvals: 7->15->11->10->END
size:4, first:7, allvals: 7->15->11->10->END
size:3, first:7, allvals: 7->15->10->END
size:3, first:99, allvals: 99->15->10->END

*/

 

사실 C Linked List delete에서도 Search함수를 굳이 따로 구현하지 않고 Delete 안에 한 번에 넣을 수도 있다. 그것은 취향껏 하자~

 

C에서도 좀 복잡하지만 Linked list 구현에 익숙해져야 한다.

 

그러려면 그 전에 struct, typedef, 각종 function 구현법에 익숙해져야 한다.

 

기본적으로 위 5가지에 대해선 잘 숙지하고 있자.

 

그러면 이제 이론은 다 배웠으니, C도 Python과 마찬가지로 다양한 문제를 풀어보며 실전감각을 길러야 한다!

 

이것으로 C Review 끝!

 

- E. O. D -