19-2-라.연결 리스트의 활용
동적 배열과 연결 리스트는 구조가 조금 다르기는 하지만 같은 타입의 데이터 집합을 다룬다는 면에서 용도가 완전히 동일하며 서로 대체 가능하다. 즉, 동적 배열로 풀 수 있는 문제라면 연결 리스트로 풀 수 있고 반대의 경우도 마찬가지다. 노드나 요소의 크기, 삽입과 삭제의 빈도, 검색 속도 요구치, 메모리 소모량 등에 따라 둘 중 하나를 선택해서 사용하면 된다.
앞에서 동적 배열로 간단한 주소록을 만들어 본 적이 있는데 이번에는 똑같은 예제를 이중 연결 리스트로 작성해 보도록 하자. 자료 구조의 형태가 바뀌었을 뿐이지 프로그램 자체는 거의 동일하게 동작한다. 전체 소스는 다음과 같다.
|
예 제 : JusoList |
#include <Turboc.h>
// 노드 구조체
struct Node
{
char name[10];
char tel[15];
char addr[32];
Node *prev;
Node *next;
};
==================== 소스 생략 =====================
Node *head; ~ UnInitList까지 DoubleList 예제와 동일함
// 이름으로 노드를 찾는다.
Node *FindNode(Node *Start,Node *aNode)
{
Node *Now;
for (Now=Start->next;Now;Now=Now->next) {
if (strcmp(Now->name,aNode->name)==0) {
return Now;
}
}
return Now;
}
void main()
{
char ch;
Node *Now;
Node Temp;
InitList();
for (;;) {
printf("명령을 입력하세요(1:보기, 2:추가, 3:삭제, Q:종료) > ");
ch=getch();
printf("\n");
if (ch == 'Q' || ch == 'q') {
break;
}
switch(ch) {
case '1':
if (head->next == NULL) {
printf("등록된 내용이 없습니다.\n");
} else {
Now=head->next;
do {
printf("이름:%s, 전화:%s, 주소:%s\n",Now->name,
Now->tel,Now->addr);
Now=Now->next;
} while (Now);
}
break;
case '2':
printf("이름을 입력하세요(9자) : ");gets(Temp.name);
printf("전화번호를 입력하세요(14자) : ");gets(Temp.tel);
printf("주소를 입력하세요(31자) : ");gets(Temp.addr);
AppendNode(&Temp);
break;
case '3':
printf("삭제할 사람의 이름을 입력하세요 : ");gets(Temp.name);
Now=FindNode(head,&Temp);
if (Now != NULL) {
DeleteNode(Now);
} else {
printf("등록되지 않은 사람입니다.\n");
}
break;
}
}
UnInitList();
}
Node 구조체에 이름, 전화번호, 주소 등을 저장하는 name, tel, addr 등이 포함되었다. 연결 리스트를 관리하는 함수들의 코드는 DoubleList 예제와 동일하므로 앞 예제의 코드를 그대로 가져오되 다만 노드가 바뀜에 따라 검색 방법은 달라지므로 FindNode 함수만 별도로 만들었다. 이 예제의 노드는 문자열로 된 이름으로 검색해야 하므로 순회하면서 비교할 때 strcmp 함수를 사용해야 한다.
그 외의 논리는 JusoArray 예제와 거의 유사하다. 검색 함수를 한 번 써 먹어 보기 위해 삭제할 대상을 입력받을 때 번호 대신 이름을 입력하도록 했을 뿐이다. 실제로 실행해 보면 별 차이를 느낄 수 없으며 성능상의 차이도 체감하기 어렵다. 이 예제는 회원 관리, 비디오 대여점, 개인 정보 관리 등의 간단한 프로그램에 대한 원형으로 충분히 쓸만한 가치가 있으므로 잘 분석해 보기 바란다.
이 절의 마지막으로 연결 리스트라는 자료 구조의 실용성에 대해 고찰해 보자. 연결 리스트는 포인터를 사용하기는 하지만 그리 복잡하지는 않고 관리 함수들도 상식 수준에서 어렵지 않게 이해할 수 있다. 내부 구조가 직관적이며 링크를 조작하는 기법도 나름대로 재미 있어서 자료 구조를 처음 접하는 사람에게는 상당히 흥미로운 주제이다. 또한 자료 구조의 가장 기본적이고도 고전적인 주제로서 학술적인 가치도 높다.
연결 리스트를 처음 배운 사람들은 다음에 실무를 할 때 한 번씩 꼭 써보고 싶다는 생각이 들 정도로 매력적이기도 하다. 그러나 사실 현대의 컴퓨터 환경에서 연결 리스트의 실용성은 거의 빵점에 가까울 정도로 형편없다. 동적 배열과 비교되는 연결 리스트의 주요 단점들을 간략하게 정리해 보면 다음과 같다.
① 읽기 속도가 형편없이 느리다. 노드간의 관계가 링크로만 저장되기 때문에 중간의 한 노드를 찾으려면 순회하는 것만이 유일한 방법이다. 10만개의 노드 중 78000번째 노드를 읽어야 한다면 정말 끔찍할 것이다. 링크에 의해 삽입, 삭제는 빨라졌지만 대신 검색 속도가 느려진 것이다. 자료를 다루는 동작의 90%는 읽기이며 삽입, 삭제는 상대적으로 흔한 동작이 아니므로 읽는 동작이 느리다는 것은 치명적인 단점이다.
② 메모리 효율이 아주 좋지 못하다. 데이터 외에 링크를 별도로 가져야 하므로 링크분만큼의 메모리가 더 소모됨은 물론이고 개별 노드를 동적으로 할당해야 하므로 할당 헤더에 의한 메모리 소모도 만만치 않다. 게다가 삽입, 삭제를 빈번하게 할 경우 메모리 단편화가 심해져 시스템의 전체적인 성능도 떨어진다. 똑같은 양의 자료를 저장하는 배열과 비교한다면 최소한 2배, 많게는 6배 정도의 메모리가 더 필요하다.
③ 코드가 그리 어렵지는 않지만 배열과 비교했을 때 상대적으로 복잡하고 포인터 구문이 많아 개발자가 실수를 할 가능성이 많다. 링크 자체가 포인터인데다가 데이터에 포인터가 포함되어 있으면 a->next->b->data[3].c 따위의 복잡한 구문도 자주 사용된다. 이런 다단계 참조문을 다룰 때는 항상 주의해야 하며 직관적이지도 못해서 읽기 어렵고 유지, 보수 비용도 증가한다. 개발 시간이 더 오래 걸리며 개발 비용도 결국 비싸진다.
④ 자료 구조의 내부적인 모양이 선형(linear)이 아닌 입체적인 모양을 하고 있어 스트림 입출력이 번거롭다. 연결 리스트를 파일로 저장하려면 링크는 빼고 데이터만 저장해야 하며 다시 불러 올때는 일일이 링크를 복원해야 한다. 링크는 메모리상에서만 의미가 있는 값이므로 저장 대상이 아니다. 리스트 전체를 화면으로 출력하거나 네트워크로 전송할 때도 여러 모로 불편한 점이 많다.
⑤ qsort, bsearch 등의 알고리즘을 구현하는 표준 함수들은 기본적으로 배열에 대해 동작하도록 작성되어 있다. 정렬, 이분 검색은 둘 다 임의 접근을 요구하는데 연결 리스트는 임의 접근을 지원하지 않으므로 이런 표준 함수의 서비스를 받을 수 없다.
연결 리스트는 삽입과 삭제가 엄청나게 빠르다는 유일한 장점을 하나 가지고 있다. 그러나 이것조차도 항상 진실이라고 보기 어렵다. 동시에 다량의 데이터를 삽입할 때는 그야말로 내부에서 엄청난 포인터 조작을 해야 하는데 이에 비해 배열은 웬만한 대용량이라도 간단하고 빠르게 삽입된다. 동적 배열의 삽입 속도는 연결 리스트보다 확실히 느렸다. 그러나 이런 사정이 컴퓨터가 빨라지면서 달라져 현대의 컴퓨터 환경에서 수천~수만 건의 자료는 배열로 밀고 당겨도 속도 감소를 체감하지 못할 정도이며 수백건인 경우는 오히려 배열이 훨씬 더 빠르다.
연결 리스트의 빠른 삽입 속도가 배열을 압도할 정도가 되려면 자료가 수십만 건 정도 되어야 하며 백만건 정도 된다면 배열보다 연결 리스트가 확실히 나은 성능을 보일 것이다. 그러나 이 정도의 자료라면 당연히 트리 구조를 쓰는 것이 합리적이다. 결국 연결 리스트는 중소 규모에서는 배열에게 밀리고 대규모에서는 트리에게 밀려 지금은 설 자리가 마땅치 않은 단점 투성이의 자료 구조가 된 것이다. 연결 리스트가 월등히 우월한 경우라면 PDA나 핸드폰 등 느린 프로세서를 가진 기계에서 삽입, 삭제가 아주 빈번하고 자료의 양이 많을 때 정도에 국한된다.
그러나 연결 리스트에 대한 이론적 학습은 여전히 중요하다. 연결 리스트는 동적 메모리 할당과 포인터에 대한 생생한 실습 도구로서 학술적 가치가 높고 또한 노드를 관리하는 기법은 상위 자료 구조인 트리에서 그대로 적용되므로 자료 구조의 한 과목으로서 생략할 수 없는 주제이기도 하다. 분석해 볼만한 예제들 중에 연결 리스트로 작성되어 있는 것들도 많기 때문에 이런 좋은 예제들의 기법을 흡수하기 위해서라도 연결 리스트는 꼭 연구해야 봐야 한다.
실무에서 연결 리스트를 쓸 것인가 동적 배열을 쓸 것인가는 개인의 취향과 문제의 특수성에 따라 결정되어야 할 것이다. 사실 최근의 객체 지향 기법에서는 둘 다 객체로 포장해 버리면 외부에서 보기에는 차이점이 거의 없어 중소 용량인 경우 어떤 쪽을 선택하나 결과는 마찬가지라고 할 수 있다. 아뭏든 삽입과 삭제가 필요할 때 쓸 수 있는 자료 구조는 연결 리스트뿐이며 오로지 연결 리스트만이 최선의 해결책이라는 고정관념은 버려야겠다. 10여년전에는 사실이었지만 지금은 그렇지 않다.
CharList
문자형 변수 하나를 데이터로 가지는 이중 연결 리스트를 만들고 키보드로 입력받은 문자들을 이 리스트에 저장하라. 노드를 삽입할 때 문자의 크기순으로 정렬하여 삽입해 보자. 삭제나 보기 기능은 빼고 한 문자가 입력될 때마다 리스트를 덤프하여 출력하라.
JusoRok
주소록 프로그램을 작성하라. 다음과 같이 구조체를 정의하고 이 구조체의 집합을 출력, 편집, 삽입, 삭제, 파일 입출력하는 기능을 작성한다. 데이터를 관리하는 방법은 이 장의 내용을 참조하고 파일 입출력 방법은 17장을 참조하라.
struct tag_Juso {
int Id;
char Name[16];
char Age;
char Tel[15];
char Addr[64];
};
이 구조체에서 Id는 중복되지 않는 일련 번호(Primary Key)이다. 자료 구조로 동적 배열과 연결 리스트 중 하나를 사용할 수 있으며 노드(동적 배열인 경우는 요소)는 구조체 또는 구조체 포인터로 작성할 수 있다.