반응형
링크드 리스트의 주요 연산 - 노드 추가, 노드 탐색, 노드 삭제, 노드 삽입
노드 추가
노드 추가 연산은 링크드 리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결하는 것을 의미합니다. 즉, 꼬리를 덧붙이는 것입니다.
SLL_CreateNode() 함수를 이용하여 자유 저장소에 노드를 생성한 다음, 새로 생성한 노드의 주소를 테일의 NestNode 포인터에 대입하면 될 것 같습니다. 노드 추가 연산을 수행하는 SLL_AppendNode() 함수는 다음과 같이 구현할 수 있습니다.
/* 노드 추가 */
void SLL_AppendNode(Node** Head, Node* NewNode)
{
/* 헤드 노드가 NULL 이라면 새로운 노드가 Head */
if ( (*Head) == NULL )
{
*Head = NewNode;
}
else
{
/* 테일을 찾아 NewNode를 연결하다. */
Node* Tail = (*Head);
while ( Tail->NextNode != NULL )
{
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
}
}그리고 이렇게 구현한 SLL_AppendNode() 함수는 다음과 같이 사용합니다.
Node* List = NULL;
Node* NewNode = NULL;
NewNode = SLL_CreateNode( 117 ); /* 자유 저장소에 노드 생성 */
SLL_AppendNode( &List, NewNode ); /* 생성한 노드를 List에 추가 */
NewNode = SLL_CreateNode( 119 ); /* 자유 저장소에 또 다른 노드 생성 */
SSL_AppendNode( &List, NewNode ); /* 생성한 노드를 List에 추가 */노드 탐색
탐색 연산은 링크드 리스트가 가진 약점 중의 하나입니다. 배열이 인덱스를 이용하여 즉시 원하는 요소를 취할 수 있도록 하는 것에 반하여, 링크드 리스트는 헤드부터 시작하여 다음노드에 대한 포인터를 징검다리 삼아 차근차근 노드의 수를 세어나가야만 원하는 요소에 접근할 수 있습니다.
링크드 리스트 내에서 임의의 위치에 있는 노드를 찾아 반환하는 SLL_GetNodeAt() 함수는 다음과 같이 구현할 수 있습니다.
/* 노드 탐색 */
Node* SLL_GetNodeAt(Node* Head, int Location)
{
Node* Current = Head;
While ( Current != NULL && (--Location) >= 0 )
{
Current = Current->NextNode;
}
return Current;
}그리고 이 함수는 다음과 같이 사용할 수 있습니다.
Node* List = NULL;
Node* MyNode = NULL;
SLL_AppendNode( &List, SLL_CreateNode( 117 ) ); /* 노드를 생성하여 List에 추가 */
SLL_AppendNode( &List, SLL_CreateNode( 119 ) ); /* 노드를 생성하여 List에 추가 */
MyNode = SLL_GetNodeAt( List, 1 ); /* 두 번째 노드의 주소를 NewNode에 저장 */
printf( "%d\n", MyNode->Data ); /* 119를 출력 */깔끔해 보이는 코드입니다. 그러나 다른 한 편으로는 안타까운데요. 사용은 간단한 반면 내부 구현은 엄청난 비효율성을 가지고 있기 때문입니다. 이러한 노드 탐색의 비효율성은 링크드 리스트의 숙명과도 같은 것입니다.
노드 삭제
노드 삭제 연산은 링크드 리스트 내에 있는 임의의 노드를 제거하는 연산입니다. 삭제하고자 하는 노드를 찾은 후, 해당 노드의 다음 노드를 이전 노드의 NextNode 포인터에서 제거하면 됩니다.
삭제 연산을 수행하는 SLL_RemoveNode() 함수는 다음과 같이 구현할 수 있습니다.
/* 노드 제거 */
void SLL_RemoveNode(Node** Head, Node* Remove)
{
if ( *Head == Remove)
{
*Head = Remove->NextNode;
}
else
{
Node* Current = *Head;
while ( Current != NULL && Current->NextNode != Remove )
{
Current = Current->NextNode;
}
if ( Current != NULL )
Current->NextNode = Remove->NextNode;
}
}삭제한 노드는 달리 쓸 곳이 없다면 그 자리에서 파괴하는 것이 좋습니다. 앞서 구현했던 SLL_DestoryNode() 함수를 이용하여 삭제한 노드를 소멸시키면 됩니다. SLL_RemoveNode() 함수의 호출 예는 다음과 같습니다.
Node* List = NULL;
Node* MyNode = NULL;
SLL_AppendNode( &List, SLL_CreateNode( 117 ) ); /* 노드를 생성하여 List에 추가 */
SLL_AppendNode( &List, SLL_CreateNode( 119 ) ); /* 노드를 생성하여 List에 추가 */
SLL_AppendNode( &List, SLL_CreateNode( 212 ) ); /* 노드를 생성하여 List에 추가 */
MyNode = SLL_GetNodeAt ( List, 1 ); /* 두 번째 노드의 주소를 NewNode에 저장 */
printf( "%d\n", MyNode->Data ); /* 119를 출력 */
SSL_RemoveNode( &List, MyNode ); /* 두 번째 노드 제거 */
SSL_DestroyNode ( MyNode ); /* 링크드 리스트에서 제거한 노드를 메모리에서 완전히 소멸 */노드 삽입
노드 삽입은 노드와 노드 사이에 새로운 노드를 끼워넣는 연산입니다.
노드 삽입을 수행하는 SLL_InsertAfter() 함수는 다음과 같이 구현합니다.
/* 노드 삽입 */
void SLL_InsertAfter(Node* Current, Node* NewNode)
{
NewNode->NextNode = Current->NextNode;
Current->NextNode = NewNode;
}노드 개수 세기
노드의 개수를 세는 루틴도 필요할 것입니다. 다음의 SLL_GetNodeCount() 함수는 링크드 리스트 내에 존재하는 노드의 수를 세어 그 결과를 반환합니다.
/* 노드 수 세기 */
int SLL_GetNodeCount(Node* Head)
{
int Count = 0;
Node* Current = Head;
while ( Current != NULL )
{
Current = Current->NextNode;
Count++;
}
return Count;
}링크드 리스트 예제 프로그램
이 예제 프로그램은 총 세 개의 파일로 구성됩니다. 하나는 링크드 리스트의 기본 연산을 수행하는 함수가 선언되어 있는 LinkedList.h, 다른 하나는 이 함수들을 구현하는 LinkedList.c, 그리고 마지막 하나는 구현된 내용을 테스트하는 Test_LinkedList.c 입니다.
/****************/
/* LinkedList.h */
/****************/
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct tagNode
{
ElementType Data;
struct tagNode* NextNode;
} Node;
/* 함수 원형 선언 */
Node* SLL_CreateNode(ElementType NewData);
void SLL_DestroyNode(Node* Node);
void SLL_AppendNode(Node** Head, Node* NewNode);
void SLL_InsertAfter(Node* Current, Node* NewNode);
void SLL_InsertNewHead(Node** Head, Node* NewHead);
void SLL_RemoveNode(Node** Head, Node* Remove);
Node* SLL_GetNodeAt(Node* Head, int Location);
int SLL_GetNodeCount(Node* Head);
#endif/****************/
/* LinkedList.c */
/****************/
#include "LinkedList.h"
/* 노드 생성 */
Node* SLL_CreateNode(ElementType NewData)
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = NewData; /* 데이터를 저장한다. */
NewNode->NextNode = NULL; /* 다음 노드에 대한 포인터는 NULL로 초기화 한다. */
return NewNode;/* 노드의 주소를 반환한다. */
}
/* 노드 소멸 */
void SLL_DestroyNode(Node* Node)
{
free(Node);
}
/* 노드 추가 */
void SLL_AppendNode(Node** Head, Node* NewNode)
{
/* 헤드 노드가 NULL이라면 새로운 노드가 Head */
if ( (*Head) == NULL )
{
*Head = NewNode;
}
else
{
/* 테일을 찾아 NewNode를 연결한다. */
Node* Tail = (*Head);
while ( Tail->NextNode != NULL )
{
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
}
}
/* 노드 삽입 */
void SLL_InsertAfter(Node* Current, Node* NewNode)
{
NewNode->NextNode = Current->NextNode;
Current->NextNode = NewNode;
}
void SLL_InsertNewHead(Node** Head, Node* NewHead)
{
if ( Head == NULL )
{
(*Head) = NewHead;
}
else
{
NewHead->NextNode = (*Head);
(*Head) = NewHead;
}
}
/* 노드 제거 */
void SLL_RemoveNode(Node** Head, Node* Remove)
{
if ( *Head == Remove )
{
*Head = Remove->NextNode;
}
else
{
Node* Current = *Head;
while ( Current != NULL && Current->NextNode != Remove )
{
Current = Current->NextNode;
}
if ( Current != NULL )
Current->NextNode = Remove->NextNode;
}
}
/* 노드 탐색 */
Node* SLL_GetNodeAt(Node* Head, int Location)
{
Node* Current = Head;
while ( Current != NULL && (--Location) >= 0)
{
Current = Current->NextNode;
}
return Current;
}
/* 노드 수 세기 */
int SLL_GetNodeCount(Node* Head)
{
int Count = 0;
Node* Current = Head;
while ( Current != NULL )
{
Current = Current->NextNode;
Count++;
}
return Count;
}/*********************/
/* Test_LinkedList.c */
/*********************/
#include "LinkedList.h"
int main( void )
{
int i = 0;
int Count = 0;
Node* List = NULL;
Node* Current = NULL;
Node* NewNode = NULL;
/* 노드 5개 추가 */
for ( i = 0; i<5; i++ )
{
NewNode = SLL_CreateNode(i);
SLL_AppendNode(&List, NewNode);
}
NewNode = SLL_CreateNode(-1);
SLL_InsertNewHead(&List, NewNode);
NewNode = SLL_CreateNode(-2);
SLL_InsertNewHead(&List, NewNode);
/* 리스트 출력 */
Count = SLL_GetNodeCount(List);
for ( i = 0; i<Count; i++ )
{
Current = SLL_GetNodeAt(List, i);
printf("List[%d] : %d\n", i, Current->Data);
}
/* 리스트의 세 번째 노드 뒤에 새 노드 삽입 */
printf("\nInserting 3000 After [2]...\n\n");
Current = SLL_GetNodeAt(List, 2);
NewNode = SLL_CreateNode(3000);
SLL_InsertAfter(Current, NewNode);
/* 리스트 출력 */
Count = SLL_GetNodeCount(List);
for ( i = 0; i<Count; i++ )
{
Current = SLL_GetNodeAt(List, i);
printf("List[%d] : %d\n", i, Current->Data);
}
/* 모든 노드를 메모리에서 제거 */
printf("\nDestroying List...\n");
for ( i = 0; i<Count; i++ )
{
Current = SLL_GetNodeAt(List, 0);
if ( Current != NULL )
{
SLL_RemoveNode(&List, Current);
SLL_DestroyNode(Current);
}
}
return 0;
}반응형
'IT > 알고리즘' 카테고리의 다른 글
| 스택(Stack)의 개념 및 배열로 구현하는 스택 (0) | 2020.06.26 |
|---|---|
| 환형 링크드 리스트 (원형 링크드 리스트, Circular Linked List) (0) | 2020.06.25 |
| 더블 링크드 리스트(Doubly Linked List) (0) | 2020.06.23 |
| 링크드 리스트의 주요 연산 - 노드의 생성과 소멸 (0) | 2020.06.21 |
| 링크드리스트(Linked List) (0) | 2020.06.20 |
