싱글 링크드 리스트의 구현이다.
일단 구현을 하기 전에 왜 링크드 리스트를 사용 하는지에 대하여 알아보자.
우선 배열에 대하여 생각해봐야 하는데 우선 배열의 특징은 다음과 같다.
1. 구현하기가 쉽다.
2. 빠르다.
하지만 그만큼 단점이 존재 하는데
1. 데이터의 삽입/삭제시 데이터의 이동연산이 많다.
2. 배열 사이즈의 변경이 힘들다.
이와 같은 이유로 링크드 리스트를 사용하게 된다.
우선 이번에 구현할 싱글 링크드 리스트의 그림을 보면 다음과 같다.
그림의 A ,B ,C ,D 부분이 데이터부분 그리고 옆에 작은 네모 (링크)가 다음 리스트를 가르
키는 포인터이다. 이러한 데이터 부분과 링크부분을 합쳐서 노드라고 부르는데 일단 C언어로
구현한다고 생각해보면 데이터부분과 링크부분을 하나의 집합으로 구현하여야 하기 때문에
구조체를 이용한다. ( 이 포스트에서는 간단한 구현을 위해 데이터부분에는 int형 정수 하나
만 들어가도록 만든다. )
typedef struct _Node{
int key;
struct _Node* next;
} Node;
Node* head = NULL;
Node 구조체는 앞에서 설명한데로 int형이 들어가는 데이터부분( int key )과 다음 리스트를
가르키는 링크부분 ( struct_Node * next )가 존재하며 앞에서 설명하지 않은 전역 변수인
Node * head를 선언하는 부분이 있는데 변수의 이름을 보면 알수 있듯이 링크드리스트의 처
음 부분을 가르키는 포인터 이다. 이 포인터를 만드는 이유는 배열의 배열명처럼 링크드리스
트의 시작번지를 가르키는 포인터가 필요하기 때문이다.
이 리스트를 관리 하기 위해서 이번 포스트에서는 다음과 같은 함수들을 만든다.
int InsertHead( int key );
int RemoveHead();
void PrintList();
함수들의 이름만 봐도 어떠한 기능을 하는 함수 인지 알수 있을테니 하나씩 구현을 해보자
우선
int InsertHead( int key )
1. 인자로 들어온 key값으로 노드를 만들어서
2. 만얀 리스트가 비어 있다면 이 노드를 리스트의 헤드로
3. 리스트가 비어있지 않다면 이 노드를 기존의 헤드를 새로만든 노드의 다음 리스트로 연결하고 새로만든 노드를 헤드로 선언한다.
이런식으로 돌아가는 함수이다. 이 것을 코드로 나타내면 다음과 같다.
int InsertHead( int key ){
//1. 노드를 생성한다
Node* node = NULL;
node = (Node*)malloc( sizeof(Node) );
if( node == NULL ){
return -1;
}
node->key = key;
// 2.리스트가 비어 있다면
if( head == NULL ){
node->next = NULL;
tail = node;
}
else{ 3. 리스트가 비어 있지 않다면
node->next = head;
}
head = node; // 2,3번의경우 둘다 사용되는 코드부분이므로 코드중복을 피하려고 밖으로 빼준다.
return 1;
}
int RemoveHead()
1. 지울 노드를 가르킬 포인터를 만들고 그 포인터가 리스트의 헤드를 가르키게 한다.
2. 리스트가 비어 있는 경우 지울것이 없기때문에 -1을 리턴한다.
3. 리스트의 노드가 한개인 경우 그 노드를 지우고 리턴한다.
4. 리스트의 노드가 여러개인 경우 지울 노드의 링크부분이 가르키고 있는 노드를 헤드로 만든다. 지울 노드를 메모리 free해준다.
이것을 코드로 나타내면 다음과 같다.
int RemoveHead()
{
Node * removeNode = head;//1. 지울 노드를 가르킬 포인터를 만들고 그 포인터가 리스트의 헤드를 가르키게 한다.
if( removeNode == NULL )
{
return -1; // 2. 리스트가 비어 있는 경우 지울것이 없기때문에 -1을 리턴한다.
}
else
{
if(removeNode->next == NULL)
{
head = NULL; //3. 리스트의 노드가 한개인 경우 그 노드를 지우고 리턴한다.
return 0;
}
head = removeNode->next; //4. 리스트의 노드가 여러개인 경우 지울 노드의 링크부분이 가르키고 있는 노드를 헤드로 만든다. 지울 노드를 메모리 free해준다.
free(removeNode);
return 0;
}
}
마지막으로
void PrintList()
리스트의 내용을 화면에 출력 하는 함수 이다.
1. 리스트를 탐색할 커서 노드 포인터를 만든다.
2. 노드 포인터를 헤드를 가르키게 한다.
3. 노드 포인터를 다음 링크의 주소로 바꿔주면서 노드의 값을 출력한다.
코드로 나타내면 다음과 같다.
void PrintList(){
int i = 1;
Node* cur = NULL; //1. 커서 노드 포인터를 만든다.
cur = head; // 2. 노드 포인터를 헤드를 가르키게 한다.
while( cur != NULL ){
printf( "%2d list key is %d\n",i++, cur->key );
cur = cur->next; //3. 노드 포인터를 다음 링크의 주소로 바꿔주면서 노드의 값을 출력한다.
}
}
