linked list [펌]

링크드 리스트(linked list)는 뜻 그대로 연결 리스트를 의미한다. C 언어에서 링크드 리스트는 구조체를

연결하기 위해 사용되며, 아래와 같이 여러 개의 구조체가 있을 때, next 포인터는 다음 구조체의 번지를

갖게 된다. 여기서 head는 항상 맨 앞의 구조체 번지를 갖고 있고, tail은 맨 뒤의 구조체 번지를 갖고 있다.

head 포인터를 통해서 맨 처음 구조체의 번지를 구한 후, 그 구조체 안의 next 포인터를 통해서 그 다음에

연결되어 있는 구조체의 번지를 구할 수 있다. 포인터가 번지값을 갖을 수 있기 때문에 아래와 같은 링크드

리스트라은 것이 가능하다.

 

 

 

 

다음은 위 그림에 대한 간단한 예이다. int*는 struct linked_list*를 사용해야 하는데, 여기서는 예를 들기 위해

int*를 사용하였다.

 

    struct linked_list

    {

        int data;

        int* next;

    };

 

    struct linked_list  list[3];

    int* head, *tail;

    head = &list[0];

    tail = &list[2];

    list[0]->next = &list[1]; // 첫 번째 구조체의 next 포인터는 두 번째 구조체(list[1])의 번지값을 갖는다.

    list[1]->next = &list[2]; // 두 번째 구조체의 next 포인터는 세 번째 구조체(list[2])의 번지값을 갖는다.

    list[2]->next = NULL;     // 마지막 리스트는 항상 NULL이 되어야, 링크드 리스트의 끝이 어디인지 판단할 수 있음

   

    int* p = head;                 // p는 첫 번째 구조체의 번지

    int* next = p->next ;      // next는 두 번째 구조체의 번지

    int* next2 = next->next; // next2는 세 번째 구조체의 번지

 

    p->data;                        // 첫 번째 구조체의 data 값, list[0].data와 동일

    next->data;                   // 두 번째 구조체의 data 값, list[1].data와 동일

    next2->data;                 // 세 번째 구조체의 data 값, list[2].data와 동일

 

--------------------------------------------&^.^-----------------------------------------------

 

#include <stdio.h>       // printf, scanf
#include <stdlib.h>      // malloc
#include <malloc.h>     // malloc
#include <memory.h>   // memset

 

// 구조체 포인터 변수인 next는 다음 구조체의 번지값을 기억하기 위해 사용된다. next가 다음 구조체의

// 번지값을 기억하고 있기 때문에 next를 통해서 구조체를 연결할 수 있다.

struct tag_list
{
    int data;              // data
    struct tag_list* next;     // 4바이트 구조체 포인터
};

 

// struct tag_list를 좀 더 짧게 재정의한다.

typedef struct tag_list  LIST;           // struct tag_list 대신에 LIST를 사용할 수 있도록 정의
typedef struct tag_list*  PLIST;       // struct tag_list* 대신에 PLIST를 사용할 수 있도록 정의

 

void Add( PLIST plist );
void PRINT();

void FREE();

// LIST가 순차적으로 여러 개 있을 때, 맨 앞에 있는 LIST의 번지를 head 포인터가 저장하고 있으며,

// 맨 뒤에 있는 구조체의 번지는 tail이 저장한다. head 포인터는 항상 LIST의 선두를 가리키고 있기

// 때문에, head에서부터 구조체를 연속해서 찾아갈 수 있다.

PLIST  head = NULL, tail = NULL;     // 전역 변수, 맨 앞, 맨 뒤의 구조체 번지를 저장

 

void main( void )
{
    int data = 1;
    
    while( data )
    {
        PLIST plist;
        scanf( "%d", &data );

        plist = (PLIST)malloc( sizeof(LIST) );  // 메모리를 8바이트만큼 동적 할당(생성)
        memset( plist, 0, sizeof(LIST) );         // 할당 받은 메모리를 0으로 초기화

        plist->data = data;

        Add( plist );
    }

    PRINT();
}

 

// 링크드 리스트 생성

void Add( PLIST plist )
{
    plist->next = NULL;    // 새로 생성되는 것은 링크드 리스트의 맨 뒤에 더해지기 때문에 항상 NULL로 초기화 함.

    if( !head )                 // head 포인터가 아직 아무 것도 가리키지 않으면, if( head == NULL )과 동일
    {
        head = tail = plist;
        return;
    }

    tail->next = plist;
    tail = plist;
}

 

void PRINT()
{
    PLIST plist = head;         // 맨 앞의 링크드 리스트 위치로 설정

    while( plist )                  // while( plist != NULL )
    {
        printf( "%d \n", plist->data );
        plist = plist->next;    // 다음 리스트의 번지값으로 plist의 값을 변경
    }
}

void FREE()
{
    PLIST plist = head;

    while( plist )
    {
        head = plist->next;
        free( plist );           // 할당한 메모리 해제
        plist = head;
    }

 

    head = tail = NULL;      // 포인터 초기화, 재 사용 시 필요
}

 

--------------------------------------------&^.^-----------------------------------------------

 

malloc() 함수

 

메모리를 할당하는 malloc 함수는 다음과 같이 사용할 수 있다. malloc() 함수는 void*형을 반환하기 때문에

데이터형을 일치시켜야 한다. 왜 void*형을 반환하는가? 만약 int*형을 반환한다면 int*형만 사용하는 것이고

char*형을 반환한다면, char*형만 사용하는 것이 될 것이다. 그래서 모든 포인터에서 다 사용할 수 있도록

malloc() 함수는 void*형을 리턴한다.

 

    int* pi = (int*)malloc( 4 );     // 4바이트 할당

    ...

    free( pi );                         // 할당된 메모리 해제

 

    char* p = malloc( 100 );        // 100 바이트 할당

    ...

    free( p );

 

이런 원리를 이용해서 다음과 같이 LIST 구조체의 메모리를 할당한다.

 

    plist = (PLIST)malloc( sizeof(LIST) );  // 메모리를 8바이트만큼 동적 할당(생성)
    memset( plist, 0, sizeof(LIST) );         // 할당 받은 메모리를 0으로 초기화

 

malloc() 함수는 메모리 할당 후 그 영역을 초기화하지 않고 돌려 준다. 그러므로 항상 memset() 함수를

사용해서 초기화 해 주는 습관을 갖는 것이 좋다. 위 예제에서는 반드시 초기화할 필요는 없다. 초기화하지

않아도 다른 값으로 초기화되기 때문이다.

 

링크드 리스트 생성 및 연결

 

// 링크드 리스트 생성

void Add( PLIST plist )
{
    plist->next = NULL;

    if( !head )

    {
        head = tail = plist;
        return;
    }

    tail->next = plist;
    tail = plist;
}

 

위 코드를 한 줄씩 분석해 보자.

 

    plist->next = NULL;

 

plist는 동적으로 할당된 메모리의 번지의 값을 저장하고 있는 포인터이다. 링크드 리스트를 생성해서

맨 뒤에 붙일 것이기 때문에 NULL로 초기화를 한다. 링크드 리스트는 맨 뒤의 구조체의 next는 항상

NULL로 끝나야 한다.

 

    if( !head )

    {
        head = tail = plist;
        return;
    }

 

head가 NULL이면, 아직 링크드 리스트가 하나도 없는 상태이다. 이 코드는 링크드 리스트에서

단 한 번만 실행된다. head와 tail은 맨 처음 생성된 구조체의 포인터 값으로 초기화 된다.

 

    tail->next = plist;

 

이 코드는 두 번째 구조체부터 적용된다. 첫 번째 구조체는 위의 코드에서 if( !head )에 의해 head와

tail을 초기화한 후 리턴한다. tail은 첫 번째 구조체의 번지를 갖고 있기 때문에 첫 번째 구조체의 next

에 지금 추가할 구조체의 번지값을 대입한다. 그리고 나서 다음과 같이 tail을 추가할 구조체의 번지로

재 설정한다. 그러면 head와 tail의 값은 서로 틀려지고, tail은 두 번째(또는 마지막) 구조체의 번지를

갖게 된다. 

 

    tail = plist;

 

다시 정리해 보면, 첫 번째 호출에서는 다음 코드만 실행된다.

 

void Add( PLIST plist )
{
    plist->next = NULL;

    if( !head )

    {
        head = tail = plist;
        return;
    }

}

 

두 번째를 포함한 이후의 호출에서는 다음 코드만 실행된다.

 

void Add( PLIST plist )
{
    plist->next = NULL;

    tail->next = plist;
    tail = plist;
}

 

코드에서 보듯이 tail은 계속 맨 뒤에 붙여지는 포인터의 값을 저장하고 있다. 그래서 tail 포인터의

값을 통해 항상 맨 뒤의 구조체에 접근할 수 있게 되며, head 포인터를 통해서 맨 앞의 구조체에

접근할 수 있게 된다.

 

 

링크드 리스트로 연결된 구조체를 맨 앞부터 맨 뒤까지 접근

 

 

void PRINT()
{
    PLIST plist = head;         // 맨 앞의 링크드 리스트 위치로 설정

    while( plist )
    {
        printf( "%d \n", plist->data );
        plist = plist->next;    // 다음 리스트의 번지값으로 plist의 값을 변경
    }
}

 

링크드 리스트는 항상 맨 앞부터 접근하기 때문에 다음과 같이 맨 앞의 구조체 번지를 갖고 있는

head 포인터의 값을 얻어 온다.

 

    PLIST plist = head;

 

그런 후 plist가 NULL이 아닌 동안 링크드 리스트를 순회하면서 다음과 같이 값을 출력한다.

 

    printf( "%d \n", plist->data );

 

다음 문장은 링크드 리스트를 이해하는 핵심이므로 주의해서 생각해야 한다.

 

    plist = plist->next;        // 두 번째, 세 번째, 네 번째, ... n 번째 링크드 리스트의 번지를 가져옴.

 

맨 처음에 plist는 구조체의 선두(head) 번지값을 갖고 있다. 그리고 위의 코드에 의해 다음 구조체의

번지를 얻어 온다. 이제는 plist는 더 이상 첫 번째 구조체를 가리키지 않고, 두 번째 구조체를 가리키게

된다. plist가 두 번째 구조체를 가리키기 때문에 plist 구조체 포인터를 통해서 두 번째 구조체의 data 값과

next 포인터를 접근할 수 있다. 만약 구조체가 위의 그림과 같이 1000번지, 2000번지, 3000번지에 저장되어

있다면, head의 값은 1000이고, plist의 값도 1000으로 초기화 된다. 그리고 나서 plist = plist->next에 의해

plist는 2000으로 값이 변경된다. 2000은 두 번째 구조체의 번지이므로 plist를 통해 두 번째 구조체를 마음

대로 접근해서 사용할 수 있다. 만약 더 이상 링크드 리스트가 존재하지 않으면 plist는 NULL이 된다. 그러면

while( plist )에 의해 while문은 종료된다.

 

 

링크드 리스트의 메모리 해제

 

 

void FREE()
{
    PLIST plist = head;

    while( plist )
    {
        head = plist->next;
        free( plist );           // 할당한 메모리 해제
        plist = head;
    }

 

    head = tail = NULL;      // 포인터 초기화, 재 사용 시 필요
}

 

malloc() 함수에 의해 할당된 메모리는 반드시 free() 함수에 의해 해제 되어야 한다. 만약 메모리를

할당한 후 해제하지 않는다면, 언젠가는 메모리가 부족해질 것이다. 그러므로 malloc()에 의해 할당된

메모리는 free() 함수로 해제하도록 하자.

 

    PLIST plist = head;

 

우선 맨 처음의 구조체 번지를 갖고 있는 head 포인터로 초기화한다.

 

    while( plist )
    {
        ...   

    }

 

plist가 NULL이 아닌 동안 메모리를 루프를 순환한다.

 

    head = plist->next;

 

head 구조체 포인터는 더 이상 필요하지 않기 때문에 다음 구조체의 번지를 임시 저장한다.

    free( plist );           // 할당한 메모리 해제
  

plist가 가리키는 번지부터 메모리 할당을 해제한다.

 

    plist = head;

 

plist에 다음 구조체 번지를 대입한다. head에는 조금 전에 다음 구조체의 번지를 임시로

저장해 두었다. 이렇게 끝까지( plist->next가 NULL일 때까지) 링크드 리스트를 순회화면서

malloc() 함수에 의해 할당 받은 메모리를 모두 해제한다.

 

    head = tail = NULL;      // 포인터 초기화, 재 사용 시 필요

 

모든 링크드 리스트가 해제 되었기 때문에 head와 tail은 NULL로 초기화한다.

출처 : http://blog.naver.com/PostList.nhn?blogId=eunchol71