링크드 리스트

 

 

 

 

 

 

C언어로 다음과 같이 생긴 링크드 리스트를 구현해 보았다

리스트는 자료구조 대부분의 기본형이므로 숙지하고 있으면 여러가지를 이해하기 좋다

다른 자료구조를 익히기 쉬워지고, 객체지향 같은 패러다임들도 결국 자료구조의 확장형인 경우가 많다

 

 

 

 

이 프로그램은 리스트에 노드를 하나 추가하거나, 하나 제거한다

추가 함수는 정수인수 하나를 받아서 그것에 대한 노드를 추가하고

제거 함수는 정수인수와 같은 정수를 가진 노드를 찾아서 제거한다 

 

 

#include <stdio.h>
#include <stdlib.h>
// 쌍방향으로 참조 가능한 노드
struct node {
    int data;
    struct node* next;
    struct node* prev;
};
 
struct node* head = 0;
 
void addToList(int i) {
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = i;
    newNode->next = 0;
    newNode->prev = 0;
 
    if (head == 0) {
        head = newNode;
    }
    else
    {    
        head->prev = newNode;
        newNode->next = head;
        head = newNode;
    }
    printf("추가된 노드(i) : %d\n", newNode->data);
}
// 아무 데이터나 삭제 할 수 없으니 인수 정수를 찾아서 삭제한다
struct node* deleteFromList(int i) {
    struct node* temp = head;
 
    while (temp != 0)
    {
        if (temp->data == i)
        {
            if (temp == head) 
            {
                head = temp->next;
                head->prev = 0;
                temp->next = 0;
            }
 
            if (temp->next != 0) temp->next->prev = temp->prev;
            if (temp->prev != 0) temp->prev->next = temp->next;        
            
            printf("제거된 노드(i) : %d\n", temp->data);
            return temp;
        }
        temp = temp->next;
    }
}
 
int main()
{
    int i;
    for (i = 0; i < 5; i++)
        addToList(i);
 
    deleteFromList(4);
    deleteFromList(0);
    deleteFromList(2);
}

 

 

 

 

 

그러나 C언어의 메모리는 함수가 종료되어도 자동으로 해제 되지 않기 때문에

리스트를 전혀 사용하지 않는 시점에 아래의 함수로 모든 리스트 메모리를 제거해주어야만 한다

 

그 메모리를 참조하고 있는 변수가 없어도 메모리가 해제 되지 않는다

즉, 메모리를 참조하고 있는 변수가 있을 때, 해제 할 수 있다 

(이 경우에는 전역변수 head가 항상 참조하고 있다)

 

이 함수는 리스트의 모든 메모리를 해제해 버리므로 리스트는 더 이상 쓸모 없게 된다

void freeList()
{
    struct node* temp = head;
 
    while (temp != 0) {
        struct node* target = temp;
        printf("%d 노드의 메모리 해제\n", temp->data);
        temp = temp->next;
        free(target);
    }
}