------------------------------------------------------------------------
제 목: 링크드 리스트(Linked List)의 구현
작성자: 이학균
U R L :
http://explore.kwangwoon.ac.kr/~k98el560 (야후에서 '학균'검색)
작성일: 2001. 07. 28일
연락처: (HP)016-411-8187 (버디버디)lobin2 (e-mail)lobin2@hanmir.com
------------------------------------------------------------------------
1. 링크드 리스트란?
링크드 리스트(Linked List)는 데이타를 저장하기위한 일종의 변수라고 생각하시면 쉽습니다.
만약에 우리가 채팅 서버를 만들면서 상대방의 IP Address를 저장하기 위한 저장공간을 만들고
싶을 때, 가장 적합한 방법이 링크드 리스트를 사용하면 방법일 것입니다. 쉽게 말해서
1 2 3 4 5 라는 각각의 데이타를 저장하고 있다가 3이라는 데이타를 지우면 1 2 4 5가 저장되고
4와 5사이에 6이라는 데이타를 넣으면 1 2 4 6 5로 저장되는 구조입니다. 만약 배열을 사용하시면
이러한 방법이 어렵다는 걸 쉽게 아실 수 있을겁니다. 또한 링크드 리스트는 앞데이타와 뒷데이타의
포인터를 저장함으로 저장할 수 있는 데이타의 양은 메모리가 허용되는 만큼입니다. 거의 무제한이죠.
2. 링크드 리스트의 기본 원리
링크드 리스트의 기본 원리는 링크드 리스트 클래스 내에서 앞단과 뒷단의 리스트를 가리키는
링크드 리스트를 변수로 가짐으로서 앞뒤의 연결관계에 의하여 데이타를 저장할 수 있습니다.
class List
{
String IPAddress;
List* previous;
List* next;
public:
// 각종 함수들
__fastcall List(String IP);
List* __fastcall GetNext(void);
List* __fastcall GetPrevious(void);
String* __fastcall GetData(void);
List* __fastcall Remove(List* FirstList);
void __fastcall Add(List* PreviousList);
}
위와같이 간단히 구현할 수 있습니다. 즉.. 현재 리스트 클래스는 전단의 리스트 클래스의 주소와
앞단의 리스트 클래스의 주소와 고유의 IPAddress를 가져서 서로의 연관 관계에 의해서 데이타를
정렬하고 가공할 수 있는 것입니다. 생성자에 IPAddress의 값을 저장해서 새로생긴 리스트의
IPAddress 변수에 그 값을 저장하고, Add함수의 경우 전단의 리스트 객체를 넘겨서 넘겨받은 객체의
next를 현재 리스트로 저장해 주고 현재 리스트의 next값은 NULL로 저장을 해 주는 것으로 끝나고
Remove함수의 경우 현재 함수를 호출한 리스트 객체의 previous리스트를 참조해서 이 값의 next를
현재 자신이 가지고 있는 next를 넣음으로써 자신을 건너뛰게 하면 됩니다. 단, 지우려는 데이타가
가장 처음 데이타일 경우에는 현재 List 구조체의 FirstList값을 현재 List의 next로 저장을 함으로써
구현이 되므로 현재 호출한 구조체의 FirstList값을 인자로 넘겨서 FirstList값을 결과로 받아 처리합니다.
그리고 delete해 주면은 깨끗하게 지워집니다.
3. 링크드 리스트의 관리
기본적인 링크드 리스트 클래스의 이해 하에 여러 리스트를 만들 필요가 있을 때 이 자체를 구조체로
관리하면 훨씬 편리합니다. 예를 들어 서버에 접속한 전체 Client의 IP를 저장할 리스트 구조체가 필요하고
또 각 채팅방별로 BroadCast하기 위한 ClientIP를 저장할 리스트 구조체가 필요합니다. 이를 위해
간단히 리스트 구조체를 만들어 보면...
struct LiskKind {
List* MainList;
List* FirstList;
List* LastList;
}
로 지정을 하면 됩니다. MainList는 실재로 참조되는 리스트이고 FirstList와 LastList는 각종
Add나 View하기 위한 함수에서 최초와 최종의 리스트값이 요구되는 데 이 때 쓰기 위해 필요로
하는 것들입니다. 이제 전체 접속 리스트는 ListKind *AllClient라고 선언하시고 각 채팅방별로는
ListKind *ChatList[종류][방번호];라는 식으로 선언하셔서 사용하시면 됩니다.
4. 예제
기본적인 이론은 설명했으나 첨에 개념잡기가 힘든 부분이라 이해가 안되시는 분들이 많으실 겁니다.
프로그래밍의 왕도는 역시 소스 분석입니다. 아무리 좋은 스승이 백번말하는 것보다 자신이 한번 깨달
은게 훨씬 좋은거니깐 소스를 보시며 직접 찾아보세요...
해더 파일...
//---------------------------------------------------------------------------------
class TfmServer : public TForm
{
friend class List;
public:
struct ListKind { // 구조체 선언
List* MainList;
List* FirstList;
List* LastList;
}
__fastcall TfmServer(TComponent* Owner);
void __fastcall ViewList(ListKind *View); // 내용 보기
void __fastcall AddClientIP(ListKind *ClientList, String ClientIP); // 추가
};
// Linked List Class
class List
{
public:
String IPAddress;
List* previous; //이전 리스트
List* next; //다음 리스트
__fastcall List(String IP);
void __fastcall NewAdd(List* IP);
List* __fastcall Remove(List* FirstList);
String __fastcall GetData(void); // 현재 IPAddress 얻기
List* __fastcall GetNext(void); // 다음 리스트 얻기
List* __fastcall GetPrevious(void); // 전 리스트 얻기
};
위에서 설명을 드렸구요.. 이제.. 리스트 관련 함수들을 보겠습니다.
//------------------------------------------------------------------------------
// Linked List 함수들
__fastcall List::List(String IP)
{
IPAddress=IP;
next=NULL;
}
void __fastcall List::NewAdd(List* IP) //IP는 새로 생긴 바로 전의 노드이다.
{
IP->next=this; //IP->next=this 는 이전 노드가 새로 생긴 노드 (자신 : this)를 가리키라는 뜻
next=NULL;
}
List* __fastcall List::Remove(List* FirstList)
{
if(previous==NULL) {
FirstList=next;
}
else {
previous->next=next;
}
delete this;
return FirstList;
}
String __fastcall List::GetData(void)
{
return IPAddress;
}
List* __fastcall List::GetNext(void)
{
return next;
}
List* __fastcall List::GetPrevious(void)
{
return previous;
}
이상이 리스트 관련 함수들의 구현 부분이고.. 실재로 사용하는 예를 보겠습니다.
현재 가지고 있는 리스트의 내용 모두를 보여주는 함수 ViewList의 경우
메인 클래스에서 void __fastcall ViewList(ListKind *View); 라는 형식으로 선언하고
아래와 같이 구현하면 됩니다.
void __fastcall ViewList(ListKind *View)
{
// 모든 ClientIP를 mbStat에 표시
View->MainList=View->FirstList;
while (View->MainList) {
mbStat->Lines->Add(View->MainList->GetData());
View->MainList=View->MainList->GetNext();
}
View->MainList=View->LastList;
}
데이타를 추가하기 위해서는 해더에 void __fastcall AddClientIP(ListKind *ClientList, String ClientIP);로
선언을 하셔서 현재 리스트가 저장되길 원하는 구조체와 IP 값을 넘겨 주면 됩니다.
void __fastcall TfmServer::AddClientIP(ListKind *ClientList, String ClientIP)
{
bool isFind=false;
if(ClientList->MainList==NULL) { // 등록된 IP가 없을 떄
ClientList->FirstList= new List(ClientIP);
ClientList->MainList=ClientList->FirstList;
ClientList->LastList=ClientList->FirstList;
}
// List내에 있는지 검색
ClientList->MainList=ClientList->FirstList;
while(ClientList->MainList!=NULL && isFind==false) {
if(ClientList->MainList->GetData()==ClientIP) isFind=true;
ClientList->MainList=ClientList->MainList->GetNext();
}
if(!isFind) { // List에 없으면 추가
ClientList->MainList = new List(ClientIP);
ClientList->MainList->NewAdd(ClientList->LastList);
ClientList->MainList->previous=ClientList->LastList;
ClientList->LastList=ClientList->MainList;
}
}
이렇게 저장을 하시면 됩니다.
어떻게 생각하면 되게 간단하고 포인터에 대한 개념이 없으시면 많이 헷갈리실 텐데.. 꼭 확실히
배우고자 하시는 분은 먼저 포인터에 대한 개념을 먼저 잡으세요. 링크드 리스트.. 복잡한거 같지만
알고 보면 쉽고, 데이타의 저장이 무제한이라는 점과 previous와 next의 조정으로 각종 정렬이 쉽고
또한 중간에 데이타를 지울경우 그 사이의 연결이 간단해서 예전부터 많이 사용된 개념입니다.
시간이 부족하여 자세한 설명은 못드렸는데, 이해가 안가시는 분이 계시면은 E-mail이나 제 홈으로
연락 주시면 바로바로 답변 드릴께요..
