2011

logo_main.gif


글: 정재준 (rgbi3307@nate.com ) / 커널연구회(www.kernel.bz)   2011-09-05



연재 차례

 1. C언어 소개
 2. 형태, 연산자, 표현
 3. 제어 흐름
 4. 함수와 프로그램 구조
 5. 포인터와 배열
 6. 구조체
 7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개


요약
연 결 리스트(linked list)는 데이터가 저장되어 있는 노드들이 link(포인터)를 통하여 선형적으로 연결된 형태의 자료구조이다. 연결 리스트(linked list)는 컴퓨팅에서 가장 근본이 되는 자료구조로써 스택(stack), 큐(queue), 배열과의 연관성 등에 활용된다. 배열에 비해서 연결 리스트(linked list)의 장점은 리스트를 구성하는 요소들(노드)이 기억장소에 연속적인 순서로 할당되어 있을 필요 없이 각각 독립적으로 존재할 수 있으므로 손쉽게 추가 및 제거될 수 있다는 것이고, 또한 이러한 작업이 리스트의 전체 구조에 영향을 주지 않는 다는 점이다. 반면에, 리스트를 구성하는 요소들(노드)이 link(포인터)를 통하여 상호 연결되어 있으므로 노드들의 추가/삭제 시 link(포인터)의 상호 연결관계를 관리해야 하는 단점이 있다.
또한, 요소들(노드)을 검색할 때 무작위(random)로 접근하지 못하고 처음부터 순서대로 link(포인터)를 따라가며 탐색해야 하는 비효율성이 존재한다

연 결 리스트(Linked List)는 1955년~1956년경에 Allen Newell, Cliff Shaw, Herbert Simon에 의해서 개발되었다. 이들은 RAND라는 회사에서 IPL(Information Processing Language)를 위한 근본적인 데이터 구조체를 만들었는데 이것이 Linked List이다. 이들에 의해서 사용된 IPL은 초창기 인공지능 프로그램들, 논리 이론 기계, 일반적인 문제 풀기, 컴퓨터 체스 프로그램 등을 개발하기 위한 것이었다. 이러한 작업은 1956년 IRE Transactions on Information Theory에 보고 되었고 1957년에서 1959년 사이에 여러 군데 학회에 발표 되었다.

연결 리스트(linked list) 분류
Linked List로 연결되는 각각의 레코드를 element 혹은 node라고 한다. 노드는 데이터(information)와 link(pointer)로 구성된다.
각 각의 노드를 서로 연결하는 주소를 next link 혹은 next pointer라고 한다. 리스트의 첫 번째 노드를 head라고 하고 마지막 노드를 tail이라 한다.  Linked List는 노드들을 연결하는 방식에 따라서 선형과 원형 리스트(linear and circular list), Singly linked list, Doubly linked list 등으로 분류된다. 아래는 이들을 그림으로 나타낸 것이다.

 노드와 리스트는 C언어를 사용하여 아래와 같은 구조체로 선언한다.

typedef struct node
{
 void*  data;
 struct node* link;
} NODE;

typedef struct
{
 int count;
 NODE* pos;
 NODE* head;
 NODE* tail;
} LIST;

연결 리스트(linked list) 동작들
연결 리스트(Linked List)에 새로운 노드 삽입:

bool list_insert (LIST* pList, NODE* pPre, void* data_in)
{
 NODE* pNew;

 if (!(pNew = (NODE*) malloc(sizeof(NODE)) )) return false;

 pNew->data = data_in;
 pNew->link = NULL;

 if (pPre == NULL) {
  pNew->link = pList->head;
  pList->head = pNew;
  if (pList->count == 0) pList->tail = pNew;
 } else {
  pNew->link = pPre->link;
  pPre->link = pNew;

  if (pNew->link == NULL) pList->tail = pNew;
 }
 (pList->count)++;
 return true;
}

연결 리스트(Linked List)에서 노드 삭제:

void list_delete (LIST* pList, NODE* pPre, NODE* pLoc, void** data_out)
{
 *data_out = pLoc->data;
 if (pPre == NULL)
  pList->head = pLoc->link;
 else
  pPre->link = pLoc->link;

 if (pLoc->link == NULL) pList->tail = pPre;

 (pList->count);
 free (pLoc);

 return;
}

연결 리스트(linked list) 코딩
이제 연결 리스트를 C언어로 코딩 해보자. 먼저 다음과 같이 헤더 파일(list.h)을 작성하여 노드와 리스트 구조체를 선언하고 리스트 작업용 함수들의 원형을 코딩 한다.

(실습 소스) list.h

//
//  Source: list.h written by Jung,JaeJoon at the www.kernel.bz
//  Compiler: Standard C
//  Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//

//boolean 데이터타입(gcc: #include <stdbool.h>) -
typedef enum {
    true = 1,
    TRUE = 1,
    false = 0,
    FALSE = 0
} bool;

//리스트구조체선언-

//단방향노드(일반적인스택, 큐, 리스트)
typedef struct node
{
 void*    data;
 struct node*    link;
} NODE;

typedef struct
{
 int count;
 NODE* pos;
 NODE* head;
 NODE* tail;
 int (*compare) (void* argu1, void* argu2);
} LIST;

//리스트함수들선언-
LIST* list_create (int (*compare) (void* argu1, void* argu2) );
LIST* list_destroy (LIST* list);
int list_add_node (LIST* pList, void* data_in);
bool list_remove_node (LIST* pList, void* keyPtr, void** data_out);
bool list_search_node (LIST* pList, void* pArgu, void** data_out);
bool list_retrieve_node (LIST* pList, void* pArgu, void** data_out);
//리스트탐색
bool list_traverse (LIST* pList, int fromWhere, void** data_out);

int list_count (LIST* pList);
bool list_is_empty (LIST* pList);
bool list_is_full (LIST* pList);

//private
bool list_insert (LIST* pList, NODE* pPre, void* data_in);
void list_delete (LIST* pList, NODE* pPre, NODE* pLoc, void** data_out);
bool list_search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu);

list.h 헤더파일에서 선언한 함수들을 간단히 설명하면 아래와 같다. list_create() 함수는 LIST 구조체를 메모리 할당하고 각각의 요소들을 초기화 하는 역할을 한다.

LIST* list_create (int (*compare) (void* argu1, void* argu2) )
{
 LIST* list;

 list = (LIST*) malloc (sizeof (LIST));
 if (list) {
  list->head = NULL;
  list->pos = NULL;
  list->tail = NULL;
  list->count = 0;
  list->compare = compare;
 }
 return list;
}

list_destroy() 함수는 리스트의 링크(link)을 하나씩 따라가면서 해당 리스트의 데이터와 메모리를 해제하는 역할을 한다. 이 과정은 while 루프를 통하여 리스트에 노드가 모두 메모리 해제될 때까지 반복한다.

LIST* list_destroy (LIST* pList)
{
 NODE* node_del;

 if (pList) {
  while (pList->count > 0) {
   free (pList->head->data);

   node_del = pList->head;
   pList->head = pList->head->link;
   pList->count;
   free (node_del);
  }
  free (pList);
 }
 return NULL;
}
list_search() 함수는 리스트에서 특정 데이터 노드를 검색하는 역할을 한다. 이 함수로 전달되는 매개변수들을 보면,

첫 번째, pList는 검색대상이 되는 리스트이다.
두 번째, pPre는 검색된 데이터가 있는 노드이다.
세 번째, pLoc는 검색된 노드에서 link로 연결된 노드이다.
네 번째, pArgu는 검색하고자 하는 데이터이다.
list_search() 함수는 while 루프를 통하여 리스트의 링크를 따라가면서 COMPARE 매크로 함수에서 pArgu가 가르키는 데이터와 (*pLoc)->data가 가르키는 데이터를 상호 비교하여 같으면 검색된 것이므로 while 루프가 종료된다.  이때 검색된 리스트 노드의 포인터는 pPre와 pLoc에 있으므로 이것이 반환된다.

bool list_search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu)
{
 #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->data)) )
 #define COMPARE_LAST ((* pList->compare) (pArgu, pList->tail->data))

 int result;

 *pPre = NULL;
 *pLoc = pList->head;
 if (pList->count == 0) return false;

 if ( COMPARE_LAST > 0) {
  *pPre = pList->tail;
  *pLoc = NULL;
  return false;
 }

 while ( (result = COMPARE) > 0 )
 {
  *pPre = *pLoc;
  *pLoc = (*pLoc)->link;
 }

 if (result == 0) return true;  //found
 else return false;
}
list_add_node() 함수는 리스트에서 data_in을 검색하여 있으면 동일한 데이터가 있는 것이므로 저장하지 않고, data_in이 없으면 새로운 데이터이므로 list_insert()함수를 통하여 새로운 노드를 할당하여 입력하는 역할을 한다.

int list_add_node (LIST* pList, void* data_in)
{
 bool found;
 bool success;

 NODE* pPre;
 NODE* pLoc;

 found = list_search (pList, &pPre, &pLoc, data_in);
 if (found) return (+1);

 success = list_insert (pList, pPre, data_in);
 if (!success) return (-1); //Overflow

 return (0);
}
list_remove_node() 함수는 리스트에서 keyPtr를 검색하여 있다면 list_delete() 함수를 호출하여 이 노드를 삭제하는 역할을 한다.

bool list_remove_node (LIST* pList, void* keyPtr, void** data_out)
{
 bool found;
 NODE* pPre;
 NODE* pLoc;

 found = list_search (pList, &pPre, &pLoc, keyPtr);
 if (found) list_delete (pList, pPre, pLoc, data_out);

 return found;
}
위에서 언급한 함수들뿐만 아니라 리스트 작업을 위한 모든 함수들을 list.c 파일로 코딩 하면 아래와 같다.

(실습 소스) list.c

//
//  Source: list.c written by Jung,JaeJoon at the www.kernel.bz
//  Compiler: Standard C
//  Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//

#include <stdlib.h>
//#include <malloc.h>
#include "list.h"

LIST* list_create (int (*compare) (void* argu1, void* argu2) )
{
 LIST* list;

 list = (LIST*) malloc (sizeof (LIST));
 if (list) {
  list->head = NULL;
  list->pos = NULL;
  list->tail = NULL;
  list->count = 0;
  list->compare = compare;
 }
 return list;
}

LIST* list_destroy (LIST* pList)
{
 NODE* node_del;

 if (pList) {
  while (pList->count > 0) {
   free (pList->head->data);

   node_del = pList->head;
   pList->head = pList->head->link;
   pList->count;
   free (node_del);
  }
  free (pList);
 }
 return NULL;
}

int list_add_node (LIST* pList, void* data_in)
{
 bool found;
 bool success;

 NODE* pPre;
 NODE* pLoc;

 found = list_search (pList, &pPre, &pLoc, data_in);
 if (found) return (+1);

 success = list_insert (pList, pPre, data_in);
 if (!success) return (-1); //Overflow

 return (0);
}

bool list_remove_node (LIST* pList, void* keyPtr, void** data_out)
{
 bool found;
 NODE* pPre;
 NODE* pLoc;

 found = list_search (pList, &pPre, &pLoc, keyPtr);
 if (found) list_delete (pList, pPre, pLoc, data_out);

 return found;
}

bool list_search_node (LIST* pList, void* pArgu, void** data_out)
{
 bool found;
 NODE* pPre;
 NODE* pLoc;

 found = list_search (pList, &pPre, &pLoc, pArgu);
 if (found)
  *data_out = pLoc->data;
 else
  *data_out = NULL;

 return found;
}

static bool list_retrieve_node (LIST* pList, void* pArgu, void** data_out)
{
 bool found;
 NODE* pPre;
 NODE* pLoc;

 found = list_search (pList, &pPre, &pLoc, pArgu);
 if (found) {
  *data_out = pLoc->data;
  return true;
 }
 *data_out = NULL;
 return false;
}

bool list_is_empty (LIST* pList)
{
 return (pList->count == 0);
}

bool list_is_full (LIST* pList)
{
 NODE* temp;

 if ((temp = (NODE*)malloc(sizeof(*(pList->head))))) {
  free (temp);
  return false;
 }
 return true;
}

int list_count (LIST* pList)
{
 return pList->count;
}

bool list_traverse (LIST* pList, int fromWhere, void** data_out)
{
 if (pList->count == 0) return false;

 if (fromWhere == 0) {
  pList->pos = pList->head;
  *data_out = pList->pos->data;
  return true;
 } else {
  if (pList->pos->link == NULL)
   return false;
  else {
   pList->pos = pList->pos->link;
   *data_out = pList->pos->data;
   return true;
  }
 }
}

bool list_insert (LIST* pList, NODE* pPre, void* data_in)
{
 NODE* pNew;

 if (!(pNew = (NODE*) malloc(sizeof(NODE)) )) return false;

 pNew->data = data_in;
 pNew->link = NULL;

 if (pPre == NULL) {
  pNew->link = pList->head;
  pList->head = pNew;
  if (pList->count == 0) pList->tail = pNew;
 } else {
  pNew->link = pPre->link;
  pPre->link = pNew;

  if (pNew->link == NULL) pList->tail = pNew;
 }
 (pList->count)++;
 return true;
}

void list_delete (LIST* pList, NODE* pPre, NODE* pLoc, void** data_out)
{
 *data_out = pLoc->data;
 if (pPre == NULL)
  pList->head = pLoc->link;
 else
  pPre->link = pLoc->link;

 if (pLoc->link == NULL) pList->tail = pPre;

 (pList->count);
 free (pLoc);

 return;
}

bool list_search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu)
{
 #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->data)) )
 #define COMPARE_LAST ((* pList->compare) (pArgu, pList->tail->data))

 int result;

 *pPre = NULL;
 *pLoc = pList->head;
 if (pList->count == 0) return false;

 if ( COMPARE_LAST > 0) {
  *pPre = pList->tail;
  *pLoc = NULL;
  return false;
 }

 while ( (result = COMPARE) > 0 )
 {
  *pPre = *pLoc;
  *pLoc = (*pLoc)->link;
 }

 if (result == 0) return true;  //found
 else return false;
}

위의 소스파일 list.h와 list.c을 통하여 다양한 리스트 응용 프로그래밍을 할 수 있는데, 간단한 영한사전 파일을 리스트에 입력한 후 이것을 검색하는 프로그래밍을 해보도록 하자.

먼저, 간단한 영한사전 파일(eng_kor_dic.dat)의 내용은 다음과 같다.(탭 문자로 컬럼구분)

-

1 “Apple” “사과”
2 “Banana” “바나나”
3 “Car” “자동차”
4 “Dinosour” “공룡”
5 “Eagle” “독수리”
6 “Fish” “물고기”
7 “Giraffe” “기린”
8 “Hippo” “하마”
9 “Iron” “철”

위의 파일을 읽어서 아래와 같은 작업메뉴를 통하여 영한사전 파일의 단어들을 출력하고 검색한다.

-

============ MENU ==============
    S: 단어검색
    P: 영한사전 모두 출력
    Q: 종료

메뉴문자 선택 후 Enter: p

영한사전 리스트 출력 시작
134479873 Apple 사과
134479874 Banana 바나나
134479875 Car 자동차
134479876 Dinosour 공룡
134479877 Eagle 독수리
134479878 Fish 물고기
134479879 Giraffe 기린
134479880 Hippo 하마
134479881 Iron 철
영한사전 리스트 출력 종료

============ MENU ==============
    S: 단어검색
    P: 영한사전 모두 출력
    Q: 종료

메뉴문자 선택 후 Enter: s
영단어를 입력하세요: Car
134479875 Car 자동차
============ MENU ==============
    S: 단어검색
    P: 영한사전 모두 출력
    Q: 종료

메뉴문자 선택 후 Enter:

-

위의 내용을 구현한 전체 프로그램 소스는 아래와 같다.

(실습 소스) main_dic.c
-

//
//  Source: list_dic.c written by Jung,JaeJoon at the www.kernel.bz
//  Compiler: Standard C
//  Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "list.h"

#define STR_MIN  20
#define STR_MAX 200

typedef struct
{
 int  pno;
 char eng [STR_MIN];
 char kor [STR_MAX];
} ENG_KOR_WORD;

LIST* user_list_build (char *fname_dic); //단어사전파일을읽어서메모리에Linked List 생성
void user_list_print (LIST* list);  //Linked List 내용을모두출력

void user_list_search (LIST* list);  //Linked List 검색

int word_compare (void* ptr1, void* ptr2);    //단어비교첫문자
int word_compare_full (void* ptr1, void* ptr2);    //단어비교full

void user_menu (LIST* list); //작업메뉴
char user_menu_choice (void); //메뉴선택

int main (void)
{
 LIST* list;

 printf ("English-Korean 사전시작n"
  "-n");

 list = user_list_build ("eng_kor_dic.dat");
 user_menu (list);

 printf ("n"
   "English-Korean 사전종료n");
 return 0;
}

LIST* user_list_build (char *fname_dic)
{
 FILE*  fpData;
 LIST*  list;
 int    pnoIn;
 int    addResult;
 ENG_KOR_WORD* pWord;
 char  pEng[STR_MIN];

 list = list_create (word_compare_full);
 if (!list)
  printf ("aCannot create listn"),
   exit (100);
 fpData = fopen (fname_dic, "r");
 if (!fpData)
  printf ("aError opening input filen"),
   exit (110);

 while (fscanf (fpData, " %hd", &pnoIn) == 1)
 {
    pWord=(ENG_KOR_WORD*) malloc(sizeof(ENG_KOR_WORD));
    if (!(pWord))
  printf ("aOut of Memory in build listn"),
   exit (100);

  pWord->pno = pnoIn;
  pEng[0] = ‘‘z‘‘;
  pWord->eng[0] = pEng[0];

  while ((fgetc(fpData)) != ‘‘t‘‘);
  while ((fgetc(fpData)) != ‘‘"‘‘);
  fscanf (fpData, " %40[^"], %*c", pWord->eng );
  while ((fgetc(fpData)) != ‘‘t‘‘);
  while ((fgetc(fpData)) != ‘‘"‘‘);
  fscanf (fpData, " %40[^"], %*c", pWord->kor );

  addResult = list_add_node (list, pWord);
  if (addResult != 0)
    if (addResult == -1)
    printf ("Memory overflow adding moviean"),
   exit (120);
    else
   printf ("Duplicate Word %hd not addedan", pWord->eng );
  while (fgetc(fpData) != ‘‘n‘‘);
 } //while
 return list;
}

void user_list_print (LIST* list)
{
 ENG_KOR_WORD* pWord;

 if (list_count (list) == 0)
  printf("Sorry, nothing in listna");
 else {
  printf("n영한사전리스트출력시작n");
  list_traverse (list, 0, (void**)&pWord);
  do {
    printf("%hd %-40s %sn", pWord->pno , pWord->eng , pWord->kor );
  } while (list_traverse (list, 1, (void**)&pWord));
 } //else

 printf("영한사전리스트출력종료nn");
}

void user_list_search (LIST* list)
{
 char  pEng[STR_MIN];
 bool  found;
 ENG_KOR_WORD SrchArgu;
 ENG_KOR_WORD* pWord;

 printf("영단어를입력하세요: ");
 scanf("%s", pEng);
 strcpy(SrchArgu.eng, pEng);
 found = list_search_node (list, &SrchArgu, (void**)&pWord);

 if (found)
    printf ("%hd %-40s %sn", pWord->pno , pWord->eng , pWord->kor );
  else
  printf ("죄송합니다. 검색한단어가없습니다.n");

 return;
}

int word_compare (void* ptr1, void* ptr2)
{
 int result;

 if(*(((ENG_KOR_WORD*)ptr1)->eng)< *(((ENG_KOR_WORD*)ptr2) ->eng) ) result = -1;
 else if ( *(((ENG_KOR_WORD*)ptr1)->eng) > *(((ENG_KOR_WORD*) ptr2)->eng) ) result = +1;
 else result = 0;

 return result;
}

int word_compare_full (void* ptr1, void* ptr2)
{
 return strcmp ( ((ENG_KOR_WORD*)ptr1)->eng, ((ENG_KOR_WORD*)ptr2)->eng );
}

void user_menu (LIST* list)
{
 char choice;

 do {
  choice = user_menu_choice ();
  switch (choice) {
    case ‘‘P‘‘: user_list_print (list);    break;

    case ‘‘S‘‘: user_list_search (list);

    case ‘‘Q‘‘: break;
  }
 } while (choice != ‘‘Q‘‘);

 return;
}

char user_menu_choice (void)
{
 char choice;
 bool valid;

 printf("============ MENU ============== n"
  " S: 단어검색n"
  " P: 영한사전모두출력n"
  " Q: 종료nn"
  "메뉴문자선택후Enter: ");

 do {
  scanf(" %c", &choice);
  choice = toupper(choice);
  switch (choice) {
    case ‘‘S‘‘:
    case ‘‘P‘‘:
    case ‘‘Q‘‘: valid = true;
   break;
    default: valid = false;   printf("a메뉴문자(S,P,Q) 잘못선택n"
    "다시선택해주세요: ");
   break;
  }
 } while (!valid);

 return choice;
}

-

맺음말
링 크드 리스트(Linked List)는 컴퓨터에서 아주 기본이 되는 자료구조로써 스택(stack), 큐(queue), 배열과의 연관성 등에 활용된다. 따라서 링크드 리스트의 동작방식을 잘 이해해 두면 코딩 기술이 향상될 뿐만 아니라 다양하게 응용해 나갈 수 있다. 앞으로 링크드 리스트에 사용된 노드와 포인터의 연결관계는 여러 가지 자료구조 형태로 계속 등장 하므로 잘 익혀 두도록 하자.


필 / 자 / 소 / 개

000000005173-0006.jpg
(정 재준) 필자는 학창시절 마이크로프로세서 제어 기술을 배웠고, 10여년동안 쌓아온 IT관련 개발 경험을 바탕으로 “오라클실무활용SQL튜닝(혜지원)” 책을 집필하고, “월간임베디드월드” 잡지에 다수의 글을 기고하였다.  서울대병원 전산실에서 데이터베이스 관련 일을 하면서 학창시절부터 꾸준히 해온 리눅스 연구도 계속하고 있다.  특히, 스탠포드대학교의 John L. Hennessy 교수의 저서 “Computer Organization and Design” 책을 읽고 깊은 감명을 받았으며, 컴퓨터구조와 자료구조 및 알고리즘 효율성 연구를 통한 기술서적 집필에 노력하고 있다.  또한, 온라인 상에서 커널연구회 (http://www.kernel.bz/ )라는 웹사이트를 운영하며 관련기술들을 공유하고 있다.


※ 본 내용은 (주)테크월드(http://www.embeddedworld.co.kr)의 저작권 동의에 의해 공유되고 있습니다.
Copyright ⓒ
Techworld, Inc. 무단전재 및 재배포 금지

맨 위로
맨 위로