Linked list with C (2)

혀누·2021년 12월 19일

C linked list

우당탕탕C

목록 보기

2/5

Linked list

본격적인 링크드 리스트에 들어가기에 앞서 그림으로 간략히 설명해보고자 한다.

개념상으로는 그닥 어려울것 없어보인다. 자 이제 본격적으로 코드로 구현해보도록 하자.

structure, appendLast

typedef struct _Node 
{
    int key;
    //struct _Node *before;
    struct _Node *next;
}Node;

void appendLast(Node *ptr, int newData){
    if (ptr->next == NULL){
        Node *newNode = malloc(sizeof(Node));
        //newNode->before = ptr;
        newNode->next = ptr->next;
        newNode->key = newData;

        ptr->next = newNode;    
    }
    else{
        Node *cur = ptr;
        while (cur->next != NULL){
            cur = cur->next;
        }
        Node *newNode = malloc(sizeof(Node));
        //newNode->before = ptr;
        newNode->next = ptr->next;
        newNode->key = newData;

        ptr->next = newNode;  
    }
    
}

리스트의 다음 노드를 가리키는 next pointer 와 노드에 담을 값을 넣는 key 변수를 가지는 구조체를 선언해준다.

append_last 함수는 만약 넣고자 하는 자리의 포인터 ptr 이 리스트의 마지막이면 if 문 안의 코드를 통해 리스트의 마지막에 새로 malloc 으로 할당한 newNode 를 연결시켜주고,
마지막이 아니라면 cur 포인터를 선언해서 링크드리스트의 마지막으로 이동한다음 그 뒤에 newNode를 연결시켜준다.

링크드 리스트를 이루는데 필요한 몇몇 함수만 더 보도록 하자.

showList, deleteList

void showList(Node *ptr){
    Node *cur = ptr->next;
    printf("[");
    while (cur != NULL){
        printf("%d, ", cur->key);
        cur = cur->next;
    }
    printf("]\n");
}

// linked list 전체 삭제 및 메모리 해제
void deleteList(Node *ptr){
    Node *cur = ptr;
    Node *next;
    while (cur!=NULL){
        next = cur -> next;
        free(cur);
        cur = next;
    }
}

함수 자체의 패턴은 다른 함수들과 다를것 없이 cur 포인터를 선언하고 이걸 움직여가며 값을 출력하거나, 노드를 삭제하는 방식이다.

popleft

int popleft(Node *ptr){
    if (ptr -> next == NULL){// 지울게 없음
        return -1;
    }
    else{
        int target_key;
        Node *target = ptr -> next;
        target_key = target -> key;
        Node *tmp = target->next;
        free(target);
        ptr -> next = tmp;
        return target_key;
    }
}

흔히 접하는 '큐'자료구조에서 주로 쓰는 popleft 함수를 구현해보았다. (그냥 리스트 왼쪽, 맨 처음값 빼는 기본 기능만 구현했기 때문에 큐의 시간복잡도를 만족하지 않을 수 있음.)

main

int main(){
    Node *ptr = malloc(sizeof(Node));
    ptr->next = NULL;
    //ptr->before = NULL;

    appendLast(ptr, 1);
    appendLast(ptr, 2);
    appendLast(ptr, 3);
    appendLast(ptr, 4);
    appendLast(ptr, 5);
    appendLast(ptr, 6);
    appendLast(ptr, 10);
    appendLast(ptr, 11);
    appendLast(ptr, 13);
    appendLast(ptr, 19);
    appendLast(ptr, 20);


    showList(ptr);
    printf("%d is deleted\n",popleft(ptr));
    showList(ptr);
    showListMemory(ptr);
    
    
    deleteList(ptr);
    showListMemory(ptr);
    showList(ptr);
    return 0;
}