링크드 리스트 설명 및 구현

링크드 리스트란?

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

링크드 리스트는 크게 단방향 리스트

(단일 연결 리스트)와 이중 연결 리스트가 존재하는데, 먼저 단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

그 다음  이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

구현

 단일 연결 리스트

#include <stdio.h>
#include <stdlib.h>    
 
struct NODE {             // 연결 리스트의 노드 구조체
    struct NODE *next;    // 다음 노드의 주소를 저장할 포인터
    int data;             // 데이터를 저장
};
 
int main()
{
    struct NODE *node1 = malloc(sizeof(struct NODE));   //첫번째 노드
 
    struct NODE *node2 = malloc(sizeof(struct NODE));   //두번째 노드
    node1->next = node2;                                //다음 주소를 가르킴
    node2->data = 10;                                   //10을 넣음
 
    struct NODE *node3 = malloc(sizeof(struct NODE));   //3번째 노드
    node2->next = node3;                                //다음주소를 가르킴
    node3->data = 20;                                    //20을 넣음
 
    node3->next = NULL;                                 // 세 번째 노드 다음은 노드가 없음(NULL)
 
    struct NODE *curr = node1->next;    // 첫번째 노드 주소
    while (curr != NULL)               // 다음으로 가르키는 주소가 NULL이 아니면 계속 반복
    {
        printf("%d\n", curr->data);    // 데이터 출력
        curr = curr->next;             // 포인터에 다음 노드의 주소 저장
    }
 
    free(node1);     // (1)노드 메모리 해제
    free(node2);     // (2)노드 메모리 해제
    free(node3);     // (3)노드 메모리 해제
 
    return 0;
}

 이중연결 리스트

#include <stdio.h>
#include <stdlib.h>    
 
struct NODE {             // 연결 리스트의 노드 구조체
    struct NODE *next;    // 다음 노드의 주소를 저장할 포인터
    struct NODE *prev;      // 전 노드의 주소를 저장할 포인터
    int data;             // 데이터를 저장
};
 
int main()
{
    struct NODE *node1 = malloc(sizeof(struct NODE));   // 첫 번째 노드 생성
 
    struct NODE *node2 = malloc(sizeof(struct NODE));   // 두 번째 노드 생성
    node1->next = node2;                                // 첫 번째 노드 다음은 두 번째 노드
    node2->prev = node1;                                // 첫 번째 노드를 저장
    node2->data = 10;                                   // 두 번째 노드에 10 저장
 
    struct NODE *node3 = malloc(sizeof(struct NODE));   // 세 번째 노드 생성
    node2->next = node3;                                // 두 번째 노드 다음은 세 번째 노드
    node3->prev = node2;                                // 두 번재 노드를 저장
    node3->data = 20;                                    // 세 번째 노드에 20 저장
 
    node3->next = NULL;                                 // 세 번째 노드 다음은 노드가 없음(NULL)
    struct NODE *curr = node1->next;    // 첫번째 노드 주소
    printf("node1의 주소 : %d  node2의 주소 : %d  node3의 주소 : %d\n\n", node2->prev, node3->prev, node2->next);
    while (curr != NULL)               // 다음으로 가르키는 주소가 NULL이 아니면 계속 반복
    {
        printf("  이전 주소 : %d    데이터 값 : %d   다음 주소 : %d\n",curr->prev, curr->data, curr->next);    // 데이터 출력
        curr = curr->next;             // 포인터에 다음 노드의 주소 저장
    }
 
    free(node1);     // (1)노드 메모리 해제
    free(node2);     // (2)노드 메모리 해제
    free(node3);     // (3)노드 메모리 해제
 
    return 0;
}