1579, 1/79 회원가입  로그인  
   han0161
   연결리스트

http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Lectures&no=748 [복사]


연결 리스트(Linked List)
연결 리스트는 노드(node)와 링크(link)로 구성되어 있다.노드라는 것은 실제의 정보를 담고 있는 하나의 단위를 말하며, 링크는 인접 노드의 위치를 저장고 있어 연결 리스트의 순서를 유지할 수 있게 하는 연결고리를 말한다.
연결리스트는 정적인 자료 구조인 배열과는 달리 동적인 자료 구조이다.
필요하면 할당하고 필요없으면 해제하는 식의 메모리 관리가 가능하기 때문에 배열처럼 여분의 공간을 마련할 필요가 없다. 그래서 메모리를 절약할 수 있다.
또 연결리스트가 배열과 다른점은 배열은 연속된 공간을 차지하는데 비해서 연결리스트는 동적으로 수시로 할당 해제되기 때문에 메모리의 연속된 공간을 차지하지 못한다. 그래서 연결 리스트의 순서를 유지시켜 주는 것은 링크(link)에 의해서 가능해진다.
연결리스트의 종류로는 단순연결 리스트,이중 연결리스트,환형 연결리스트 등 이 있다.
단순 연결 리스트(Simple Linked List)
단순 연결 리스트는 가장 단순한 형태이면서 가장 많이 쓰이기도 하는 형태이다.단순 연결 리스트는 정보를 저장하는 노드와 바로 다음의 노드를 가리키는 링크 하나로 구성되어 있다.
자료의 순서를 마구 바꾸어야 할 경우 배열의 경우에는 당기고 미는 등의 메모리 복사가 필요하지만, 연결 리스트의 경우에는 링크가 가리키는 방향만 바꾸어주면 된다.
단순 연결 리스트는 각각이 다음의 노드를 정확히 가리키고 있지만 제일 처음의 노드를 가르치는 머리(head)가 필요하다.
이는 일반적으로 전역 변수로 선언이 되어 모듈 내의 어떤 부분에서도 접근 가능하도록 개방되어 있고, 소멸되지 않는다.
연결리스트의 제일 마지막 노드는 항상 무엇인가를 가리켜야 하는데 특별히 마지막을 나타내는 꼬리 tail 노드를 만들어서 마지막 노드임을 표시하게 한다.
연결 리스트의 노드를 C로 정의해보자
struct _node
{
    int key;
    struct _node *next;
};
C의 초보자들은 위의 구조체 정의에 괸장한 당혹감을 느낄 것이다. 왜냐하면 위의 _node 구조체의 정의 내부에 다시 _node의 포인터가 들어가 있다. 즉, _node의 구조체가 채 정의되기도 전에 _node의 포인터가 있다는 것은 말이 되지 않는 것 같다. 이 같은 구조체 정의를 재귀적인 정의 라고 한다.
위의 재귀적인 정의가 말이 되는 이유는 포인터라는 것은 어떤 형의 데이터를 가리키든지 그 자체의 크기는 변함이 없기 때문이다. 왜냐하면 포인터는 주소를 저장하기 때문이다.
그런데 형태상으로 약간은 개선해야 할 여지가 있다. struct _node와 같이 정의할 경우 변수의 정의가 번거롭기 때문이다.
Ex)struct _node *LinkedList;
_ node 구조체를 정의할 때 앞에 계속 struct를 붙인다는 것은 정말로 귀찮은 일이다. 개선을 한 노드 정의를 보자
Ex) typedef struct _node
    {
      int key;
      struct _node *next;
     }node;
위의 typedef의 뜻은 struct _node와 같은 구조체를 node라는 데이터형으로 정의한다는 뜻이다.
변수 정의를 하게 되면 node *LinkedList;
훨씬 간편하고 보기 좋지 않습니까?
이젠 node 정의를 가지고 node로 구성되는 연결리스트를 초기화 하는 init-list()함수를 만들어 보자
node *head, *tail;
void init_list(void)
{
head=(node*) malloc(sizeof(node));
tail=(node*) malloc(sizeof(node));
head->next=tail;
tail->next=tail;
}
tail->next = tail;는 꼬리의 다음은 꼬리 라고 해석이 된다. 이렇게 하는 것은 중요한 이유가 있기 때문이다.
t=t->next; 와 같은 문장이 있어서 계속 그 다음 노드로 이동하는 경우에 프로그래머의 실수로 루프를 끝내지 못할 경우 tail에 까지 이르게 되는데 이 tail이 NULL이나 기타 엉뚱한 곳을 가리 키고 있다면 t는 메모리의 황량한 곳으로 숨어버리고 만다.
대신에 꼬리의 다음은 꼬리라고 순환적인 구조를 해 둘 경우 다운은 되지 않고 무한 루프에 빠지게 된다.
위 정의한 대로 초기화 하면 이 연결리스트는 실제 내용은 아무것도 없는 빈 연결 리스트이다.
이제 빈 연결 리스트에 다른 노드를 삽입하는 함수 insert_atfer()함수를 만들어 보자
단순 연결 리스트는 t는 뒤의 노드만을 알 수 있지 앞의 노드가 무엇인지는 알 수 없다.
그래서 t의 뒤의 노드를 가리키는 링크만을 조작할 수 있어 뒤에다가 삽입을  할 수 밖에 없는 것이다.
Ex) node *insert_after(int k, node* t)
{
    node *s;
    s=(node*)malloc(sizeof(node));
    s->key =k;
    s->next=t->next;
    t->next=s;
    return s;
}
이제는 삭제하는 함수 delete_next() 함수는
int  delete_next (node *t)
{
   node *s;  //노드의 포인터 정의
   if(t->next ==tail) //t의 다음노드가 tail과 같은가? 맞으면 리턴 0
       return 0;
s=t->next;// t의 다음노드가 tail과 같은가? 아니면 s에 t의 다음 노드의 주소값을 넘긴다.
t->next = t->next->next;//t의 next에 삭제할 노드의 다음 노드의 주소값을 저장한다.
free(s);//s가 가지고 있는 주소값의 노드를 삭제한다. (free는 malloc함수로 정의한 데이터를 삭제할 때 사용한다.
return 1;
}
위에 주석을 보고 소스를 분석해 보자.
처음보시는 분도 몇번보면 이해가 되실 것이다.
그럼 나머지 검색하는 함수나 전체삭제 검색한 다음 삽입 혹은 삭제 등 함수들은 여러분들이 직접 만들어 보세요 ^^.

  Hit : 6142     Date : 2007/06/21 09:34
[불법/스팸글로 신고하기]



    
1579   왠만한사람들은다알지도모르겠지만[6]     백룡출해
03/17 10326
1578   원격종료....[39]     bsjzzz
01/02 9934
1577   원재아빠님의 gcc 2.96에서의 버퍼 구조 강좌.[9]     ttongfly
09/19 10607
1576   열(TR)과 행(TD)의 확장(펌)     rahzzang
11/21 5137
  연결리스트     han0161
06/21 6141
1574   여러선배님들 좀도와주십시오..[2]     appleone
06/29 5857
1573   여러분! net send 정리해 드립니다.[11]     idl0521
12/13 8452
1572   여러분[1]     phan_tom1
11/18 5768
1571   에그쉘 쓸줄 모르시는분..-_-필독[9]     은조
09/28 9072
1570   워게임을 해봅시다.hackthissite(basic 1)[2]     kjwon15
09/10 7555
1569   워게임 사이트입니다. [4]     wkdqkf2
03/18 5100
1568   워게임 문제 힌트좀 주실분 구함     rabbitlycat
04/30 3985
1567   왜 고등학교[5]     파란눈물
02/05 5517
1566   왜 해커가 되려는가[6]     dontknow
07/22 8272
1565   왜 C 이어야 하는가 ?[96]     소유
04/09 20463
1564   요즘 공부하고 있는 JAVA에 대한 질문과 답변[3]     장세만
07/14 6200
1563   왕초보자 들을 위한 C 언어 강좌[7]     kevin0960
01/25 7000
1562   왕초보 파이썬 (Python) 언어 배우기 - Site 추천[5]     푸른하늘
12/14 9262
1561   와우해커level2 문제풀이[3]     프라이드
08/20 7352
1560   와우해커 level1[3]     프라이드
08/20 7453
1 [2][3][4][5][6][7][8][9][10]..[79]

Copyright 1999-2021 Zeroboard / skin by Hackerschool.org / Secure Patch by Hackerschool.org & Wowhacker.com