|
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 : 7834 Date : 2007/06/21 09:34
|
1581, 
1/80 
