cs50 6강 연결리스트

연결리스트란

연결리스트는 대충 설명을 읽어보면 아니 이거 배열과 똑같은 거 아닌가 하는 생각이 들만큼 유사하다.
우선 순차적+간접참조라는 특성에서는 배열과 유사하다고 착각하기 쉽지만, 크기의 제한이 없다는 점과 연속된 메모리 주소를 할당받지는 않는다는 점에서 배열과는 차이를 지닌다.

배열과의 차이에서 오는 장단점

배열과 달리 크기를 동적으로 변경하는 것이 가능하고, 요소의 추가 및 제거가 쉽다.
그러나 연속적으로 배치된 것이 아니이 때문에 랜덤접근은 불가능하다.

링크드 리스트 코딩하기

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

typedef struct node
{
    int number;
    struct node* next;
} node;

void push_front(node** head, int num) {
    // 새로운 노드 동적 할당
    node* new_node = (node*)malloc(sizeof(node));

    if (new_node == NULL) {
        printf("할당에 실패하였습니다");
        return;
    }

    // 새로운 노드에 데이터 설정
    new_node->number = num;

    // 새로운 노드를 현재의 head로 설정하고 기존 head는 새로운 노드를 가리키게 함
    new_node->next = *head;
    *head = new_node;
}
void pop_front(node** head) {
    if (*head == NULL) {
        printf("리스트가 비어있습니다.");
        return;
    }

    // 제거할 노드를 가리킴
    node* remove = *head;

    // head를 다음 노드로 변경
    *head = (*head)->next;
    //혹시 이거 왜 괄호해야 돌아가는지 아시는분??
    // 제거할 노드의 메모리를 해제
    free(remove);
}
void insert(node** pre, int number) {
    if (*pre == NULL) {
        printf("리스트 비었다");
        return;
    }
    node* new_node = (node*)malloc(sizeof(node));
    new_node->number = number;
    new_node->next = (*pre)->next;
    (*pre)->next = new_node;
}
void remove_node(node** pre, int number) {
    if (*pre == NULL) {
        printf("리스트가 비어있습니다");
        return;
    }

    // 삭제할 노드를 찾음
    node* remove = *pre;
    while (remove != NULL && remove->number != number) {
        *pre = remove;
        remove = remove->next;
    }

    // 리스트에서 해당 노드가 없는 경우
    if (remove == NULL) {
        printf("해당 숫자를 찾을 수 없습니다.");
        return;
    }

    // 이전 노드의 next를 삭제할 노드의 next로 설정
    (*pre)->next = remove->next;

    // 삭제할 노드의 메모리를 해제
    free(remove);
}

코드 설명

우선 코드는 주소값을 철저하게 활용한 방식으로 코딩했다.
push_front()함수의 경우 새로운 헤더에 데이터를 넣고 기존 헤더를 한칸 뒤로 밀어넣어, 새로운 헤더가 맨 앞이 되도록 하는 방식이다.
pop()종류 함수의 경우 삭제하는 노드가 NULL인지 꼭 확인한 뒤에 노드를 삭제해야한다는 것과 삭제를 했다면, 노드를 적절하게 뒤쪽 칸으로 옮겨주어야한다는 것이다.

트리 구조

트리는 연결리스트에서 자식 노드라는 방향성이 추가된 느낌이라고 이해하면 된다.
즉 트리가 똑바로+균형잡힌 트리 라면 링크드 리스트에 비해 빠른 탐색이 가능하다.