너구리의 개발공부

기본적인? 연결리스트의 경우 노드 구조체에 다음 노드의 주소만 가지고 있는 형태이다.

하지만 이중 연결리스트의 경우 노드에 '전 노드의 주소'와 '다음 노드의 주소'를 모두 가지고 있는 형태이다.

또한 tail이 추가되어 연결리스트의 마지막 노드가 무엇인지 바로 알 수 있다.

struct node
{
    char *data;
    struct node *prev;
    struct node *next;
};

typedef struct node Node;

Node *head;
Node *tail;
int size = 0;

사실 이전 노드의 주소만 가지고 있더라도 노드의 삽입, 수정, 삭제 모두 가능하긴 하다.

그래도 이중 연결리스트는 노드를 삭제를 하는 코드에서 편리함이 존재한다. 이외에도 마지막 노드를 바로 찾는 것이 필요할 때 사용할 수 있을 것 같다.

-노트 삽입

void add_after(Node *prev, char *item) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = item;
    new_node->prev = NULL;
    new_node->next = NULL;

    if (prev == NULL && head == NULL) {         // empty list
        head = new_node;
        tail = new_node;
    }
    else if (prev == NULL) {            // add first
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    }
    else if (prev == tail) {            // add last
        new_node->prev = tail;
        tail->next = new_node;
        tail = new_node;
    }
    else {                              // insert node
        new_node->prev = prev;
        new_node->next = prev->next;
        prev->next->prev = new_node;
        prev->next = new_node;
    }
    size++;
}

노드 삽입/추가는 4가지 경우로 나누어 생각해 볼 수 있다.

1. 빈 연결리스트에 노드 추가: 아무것도 존재하지 않으므로 head/tail 모두 추가하려는 노드를 가리키면 된다.
2. 연결리스트의 첫번째에 노드를 추가: 새로운 노드가 head의 주소를 가리킴. head의 주소는 새로운 노드로 변경
3. 연결리스트의 마지막에 노드를 추가: 새로운 노드가 tail의 주소를 가리킴. tail의 주소는 새로운 노드로 변경
4. 연결리스트의 중간에 노드를 삽입: 4개의 링크를 변경하면 된다. 글보단 아래 그림을 보는 것이 이해가 편하다.

-노드 삭제

void remove(Node *p) {
    if (head == p && tail == p) {           // p is only node of list
        head = NULL;
        tail = NULL;
    }
    else if (head == p) {               // p is head
        p->next->prev = NULL;
        head = p->next;
    }
    else if (tail == p) {               // p is tail
        p->prev->next = NULL;
        tail = p->prev;
    }
    else {                              // p is middle node
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    free(p);
    size--;
}

 이중 연결리스트의 장점인 삭제 부분이다. 기존 연결리스트는 어떤 노드를 삭제하기 위해서 타겟노드의 이전 노드를 기억하고 있어야 했다. 하지만 노드들 마다 이전 노드의 주소를 알고 있기 때문에 코드에서 이전노드의 주소를 기억할 필요가 없어지게 된다.

 노드 삽입/추가와 마찬가지로 4가지 경우로 나누어 코드를 구현하면 된다.

-정렬된 연결리스트에 노드 삽입

add_ordered_list(char *item) {          // start searching at tail
    Node *p = tail;
    while (p != NULL && strcmp(item, p->data) < 0) {
        p = p->prev;
    }
    add_after(p, item);
}

이미 노드 삽입 부분을 구현했다. 따라서 기존 삽입함수를 활용하면 4가지 경우를 고려하지 않고 코드를 구현할 수 있다. 일단 정렬된 연결리스트이기 때문에 삽입하려는 노드의 값보다 작은 값을 찾아야 한다. (여기선 abc 오름차순 정렬) strcmp함수로 삽입하려는 노드보다 작은 값을 찾거나 p 노드가 가리키는 노드가 NULL이면 반복을 종료한다. 이 노드를 add_after 함수에 전달만 하면 끝이다. 4가지 경우는 add_after 함수에서 처리할 것이다.

-결과 확인

int main() {
    add_ordered_list("c");
    add_ordered_list("a");
    add_ordered_list("d");
    add_ordered_list("b");
    
    return 0;
}

제대로 결과값이 나오는 모습을 확인

사실 연결리스트 개념 자체는 이해하기 어렵지 않았다. 다만 c언어를 잘못해서 포인터 변수에 대한 이해가 조금 어려웠던 것 같다.

- 전역변수 (global variable)

함수의 외부에 선언된 변수들 프로그램이 시작될 때 메모리가 할당되며 프로그램이 종료될 때 까지 유지된다

Data section이라고 부르는 메모리 영역에 위치한다.

- 지역변수 (local variable)

함수의 내부에 선언된 변수들 자신이 속한 함수가 호출될 때 메모리가 할당되며 함수가 return될 때 소멸된 다.

스택(stack)이라고 부르는 영역에 위치한다.

- 동적 메모리 할당 (dynamic memory allocation)

아무때나 malloc등의 함수를 호출하여 필요한 크기의 메모리를 할당할 수 있 다. 이것을 동적 메모리 할당이라고 부른다.

동적으로 할당된 메모리는 힙(heap)이라고 부르는 영역에 위치한다.

동적으로 할당된 메모리는 명시적으로 free()함수를 호출하여 반환하지 않 는 한 계속 유지된다.

- strdup 함수

아래 그림처럼 복사하려는 char 배열의 값만 복사하여 다른 메모리 영역에 붙혀넣는다.

이후 다른 메모리 영역의 주소값을 리턴해준다.

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

#define CAPACITY 100
#define BUFFER_SIZE 20

char *names[CAPACITY];
char *numbers[CAPACITY];
int n = 0;

void add();

int main()
{
    char command[BUFFER_SIZE];
 
    while (1) {
        printf("$ ");
        scanf("%s", command);
;
        if (strcmp(command, "add") == 0)
            add();
        else if (strcmp(command, "exit") == 0)
            break;
    }
    return 0;
}

void add() {
    char name[BUFFER_SIZE];
    char number[BUFFER_SIZE];

    scanf("%s", name);
    scanf("%s", number);

    names[n] = strdup(name);
    numbers[n] = strdup(number);
    ++n;

    printf("%s was added successfully.\n", name);
}