한빛 소프트 [이것이 자료구조 + 알고리즘이다. with C언어, 박상현 저]
책을 참고해서 공부 한 내용을 정리한 것입니다.
List는 목록이라는 뜻을 가지고 있습니다.
리스트를 이루는 개별 요소들을 Node 라고 부릅니다.
노드(Node) 개념은 자료구조에서 계속 등장하는 개념이니 숨쉬듯이 써야 합니다.
리스트에서 첫번째 노드는 Head 라고 부릅니다.
마지막 노드는 Tail 이라고 부르죠.
리스트가 갖춰야 할 연산은 5가지가 있습니다.
CreateNode (노드 생성)
DestoryNode (노드 파괴)
AppenNode (노드 추가)
RemoveNode (노드 제거)
InsertNode / Insert NewHead (노드 삽입)
단어 뜻을 보면 append는 맨 뒤에 덧붙이는 것이고, Insert는 중간에 끼워넣는 뜻임을 알 수 있습니다.
Create/Destroy는 완전히 새로 만드는 것, 없애는 것이 겠죠
Node를 한번 만들어 볼까요
typedef int ElementType;
typedef struct Node {
ElementType Data; // 데이터
struct Node* NextNode; //다음 노드
}Node;싱글 링크드 리스트의 노드 입니다.
싱글 링크드 리스트에서 하나의 노드는 위와 같이 데이터와 다음 노드로 구성되어있습니다. 데이터는 여러개가 될 수도 있고, 여러가지 타입이 올 수가 있겠죠.
중요한것은 데이터 다음에 다음 노드의 포인터가 온다는 것. 이것만 기억하면 됩니다.
1. 노드 생성(CreateNode) 구현하기
CreateNode를 직접 구현해 보겠습니다.
포인터를 사용해서 리스트를 다루어야 하기 때문에 반환값은 포인터입니다.
Node* SLL_CreateNode(ElementType argData)
{
Node newNode;
newNode.Data = argData;
newNode.NextNode = NULL;
return &newNode;
}newNode 라는 Node타입의 메모리를 할당 했습니다.
newNode에 입맛대로 수정을 하고서
newNode의 주소값을 반환하면서 끝이 납니다.(&는 여기서 주소 연산자로 쓰였습니다.)
만들어 보긴 했지만 이 코드는 잘못 된 코드입니다.
프로그래머는 노드를 만들고 만들어진 노드의 주소를 반환 받고 싶어합니다.
그래서 newNode의 주소값을 가져오려 하지만 해당 주소의 메모리는 이미 해제되어있습니다.
함수가 종료될 때, 함수에서 할당했던 지역 변수들은 모두 해제되기 때문입니다.
이상태로 저 주소를 사용했다가는 어떤 사고가 발생할지 아무도 모르는 폭탄같은 상태가 될 수 있습니다.
그러므로 포인터를 사용하고 싶다면 Stack 메모리를 사용하는것은 좋지 않아 보입니다.
이제 C++ 문법에 맞게 동적할당을 사용할 것입니다.
#include <iostream>
typedef int ElementType;
typedef struct Node {
ElementType Data; // 데이터
struct Node* NextNode; //다음 노드
}Node;
Node* SLL_CreateNode(ElementType argdata)
{
Node* NewNode = new Node; //동적 할당 하기
NewNode->Data = argdata; //데이터 넣기
NewNode->NextNode = NULL;
return NewNode; //동적할당한 메모리를 리턴함
}이렇게 리턴값으로 동적할당된 메모리를 받게 되었죠.
2. 노드 파괴(Destory Node) 구현하기
리턴타입 없이 delete 를 써주면 끝이 납니다.
void SLL_DestroyNode(Node* argNode)
{
delete(argNode);
}3. 노드 추가 (Append Node) 구현하기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void SLL_AppendNode(Node** Head, Node* NewNode)//매개변수는 Head의 주소(&Head), NewNode(새로운 노드 포인터)이다.
{
//Head Node 가 NULL 인 경우 새로운 Node가 Head 가 된다.
if ((*Head) == NULL) //여기서 *Head는 Node* 타입이다. Head가 Node**타입이기 때문에.
{
*Head = NewNode; //같은 Node* 타입인 NewNode와 호환 되어 값 복사 등식이 성립한다.
}
else//Head가 이미 존재하는 경우
{
Node* Tail = (*Head); //Tail이라는 Node 타입 포인터를 생성하고 거기에 Head의 값을 복사한다.
while (Tail->NextNode != NULL) //Tail에 있는 NextNode 가 NULL 이 아니면 13라인 실행(지금이 Tail이 문자그대로 Tail 인지 검사함)
{
Tail = Tail->NextNode; // 지금 Tail이 '찐'Tail이 아닐 경우 다음 Tail로 간다.
}
Tail->NextNode = NewNode; //'찐' Tail을 만나면 그곳의 NextNode를 자신(매개변수)으로 변경한다.
}
}
|
cs |
코드가 잘 이해되지 않을때는 한줄 한줄 주석을 달면서 의미를 곱씹다 보면 이해가 됩니다.
그림으로 표현하자면 위와 같이 SingleLinkedList가 있다고 하면
위의 그림은 코드가 실행중인 어딘가에서 멈추었을 때 입니다.
Tail이 Head 부터 차례 차례 NextNode가 NULL인지를 검사하며 최종 Tail까지 검사합니다.
맨 마지막 Tail까지 와서는 15번행이 실행되면서 NULL 이었던 NextNode를 매개변수로 받은 NewNode로 변경합니다.
그렇게, 자신이 '찐' Tail이 되는 거죠.(자신의 NextNode는 NULL 일 테니까)
이 AppendNode 코드를 처음 접한 순간 익숙하지 않은 포인터가 혐오스럽게 보입니다.
맙소사 더블포인터 까지 있어요.
이 코드에 왜 더블포인터를 써야만 했을지 한번 보겠습니다.
SLL_AppendNode함수의 원형이 만약 싱글포인터만 쓴 형태였다면?
void SLL_AppendNode(Node* Head, Node* NewNode)
이런 코드를 실행한다고 하겠습니다.
Node* List = NULL;
Node* NewNode = NULL;
NewNode = SLL_CreateNode(801);
SLL_AppendNode(List, NewNode);여기까지 상황을 그림으로 표현 해 보겠습니다. 편의상 Stack의 메모리는 300부터 시작하고
Heap 메모리는 100부터 시작한다고 하겠습니다.
(32bit 프로세서에서 메모리는 4씩 증가하지만 직관적으로 예를들기 위해 10씩 증가하게 하였습니다.)
4번행을 실행하기 직전의 메모리 모습을 그림으로 표현한 상태입니다.
List 는 아무것도 가리키지 않고 있고, NewNode는 100을 가리키고 있고, 100은 동적할당받은 주소를 의미합니다.
4번행을 실행하면아래와 같은 그림이 됩니다.
매개변수 Node* Head에 List값을 복사하게되는데 포인터끼리의 복사라는 것은 포인터가 가리키고 있는 대상을 복사한다는 것을 의미 합니다.
따라서 List가 가리키는 주소가 복사가 되면 정답이지만 List는 NULL 을 가리키고 있죠.
그래서 Head도 NULL을 가지게 됩니다만.
그 순간을 살펴 보면 함수 밖의 List와 함수안의 Head는 아무런 관련도 없는 사이라는 걸 알 수 있습니다
둘다 값이 NULL 일 뿐이지요.
List의 값이 꼭 NULL 이 아니더라도 마찬가지 입니다.
포인터가 가리키는 대상을 변경한다는 것은 변수의 값을 수정한다는 것과 같습니다.
일반 변수가 어떤 값(Value)를 가지고 있듯이.
포인터 변수가 가지고 있는 값(Value)은 가리키고 있는 대상(주소)이 거든요.
함수 안에서 값을 바꾸려면 Call By Value 로는 불가능하죠? 포인터를 사용할 수 밖에 없는 겁니다. Call by Reference를 쓰기 위해서요.
포인터로 Call By Reference를 쓴겁니다.
노드 탐색 연산 구현하기(Get Node At)
링크드 리스트 자료 구조에서 탐색 연산은 취약점이라고 할 수 있습니다.
배열 같은 경우 탐색하고자 하는 index를 입력해서 바로 바로 그 값을 볼 수 가 있습니다.
9,999,999개의 자료 중에 9,999,999번째 자료를 찾아 보고 싶다면 arr[9999998] 로 접근하면 바로 접근할 수 있는 것이죠.
하지만 Linked List는 가지고 있는 정보가 다음 녀석의 주소 뿐입니다. 내가 찾는 자료가 9999번째에 있다는 것을 알고 있어도, 9999번째 자료에 접근하려면 맨 앞부터 차근차근 접근하는 방법 밖에는 없어요. 특히나 SingleLinkedList의 경우에는 내 뒤에올 녀석은 알아도 내 앞에있는 녀석은 모릅니다. 차례차례 정주행 하는 방법 뿐이죠.
옛날 비디오 방에서 빌려보던 비디오 테이프를 생각 해 봅니다.
저는 어렸을 때부터 전쟁 영화 광팬이었습니다. 블랙호크 다운 비디오를 빌려서 수십번 보고, 되감기 해서 보고 그랬죠.
저는 이 영화에서 지미핸드릭스의 voodoo child 가 흘러나오면서 수십대의 차량과함께, 수많은 헬기들이 사열하고, 출동하는 씬을 가장 좋아했습니다.
이 장면이 몇시 몇분 몇초부터 시작하는지 외울 정도였어요.
그런데 그 장면이 어딘지 알고 있어도 재생하려면 처음부터 빨리감기로 돌려서 그 시간까지 가야 합니다.
요즘 유튜브 같은 플랫폼에서는 그 시간대를 클릭만 하면 바로 그쪽으로 이동해서 볼 수 있습니다.
하지만 비디오 테이프로 보던 시절에는 그런게 불가능했어요.
링크드 리스트의 탐색을 여기에 비유하면 찰떡이겠구나 하는 생각이 들었습니다.
아래는 구현한 SLL_GetNodeAt 함수입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
Node* SLL_GetNodeAt(Node* Head, int Location)//Head는 말 그대로 포인터 HeadNode 이며 Location은 몇번째 위치인가를 의미함
{
//Current 라는 포인터 변수를 만들고 Head와 같은곳을 가리키게 함
Node* Current = Head;
//Current가 NULL이 아니고, Location - 1 = 0 이 될 때 까지 반복 (Location번 반복)
while (Current != NULL && (--Location) >= 0)
{
//Current가 가리키는 곳을 다음 노드로 변경함.
Current = Current->NextNode;
}
return Current;
}
|
cs |
return 값이 Current 라는 것은 함수내에서 Current의 값을 복사하고
그 복사한 값을 가지고 있는 녀석을 return 받는다는 이야기죠.
여기서 Current는 포인터니까 값이 주소입니다.
아래 while문 진입표에 따르면 이 함수가 HEAD + Location 번째 주소를 들고 나왔다는 이야기 입니다.
(--Location) >= 0
이것을 풀어서 설명하면 그냥 Location 만큼 반복한다는 의미입니다.
| Current의 값 | Head + 0노드 | Head+1노드 | Head+2노드 | Head+3노드 | Head+4노드 |
| Location 이 0인 경우 | while문 진입X | ||||
| Location 이 1인 경우 | while1번 진입 | 1 - 1 >= 0 | |||
| Location 이 2인 경우 | while2번 진입 | 2 - 1 >= 0 | 1 - 1 >= 0 | ||
| Location 이 3인 경우 | while3번 진입 | 3 - 1 >= 0 | 2 - 1 >= 0 | 1 - 1 >= 0 | |
| Location 이 4인 경우 | while4번 진입 | 4 - 1 >= 0 | 3 - 1 >= 0 | 2 - 1 >= 0 | 1 - 1 >= 0 |
Max_Size개의 element를 가진 배열에서 n번째 위치에 접근하려면
arr[n-1]
을 해야 하는 것처럼
Max_Size 개의 링크드 중 n번째 위치에 접근하려면
SLL_GetNodeAt(n-1)
을 해야 합니다.
노드 삭제 연산 (RemoveNode)
삭제 연산은 배열에 비하면 아주 간단합니다.
앞에있는 녀석의 NextNode만 삭제된 다음 노드로 변경해주면 끝납니다.
삭제는 DestroyNode 함수로 구현해 놓았으니 노드끼리의 연결만 재설정 해주도록 하겠습니다.
하나 더 고려 해야 할 것은 삭제 하는 노드가 중간에 있는 노드가 아닌 경우, 그러니까 Head 인 경우와 Tail인 경우가 되겠네요.
Tail인 경우는 NextNode가 NULL 인 것으로 알 수 있으며, 만약 그렇게 되어도 알고리즘에 차이는 없습니다.
위 그림에서 N2의 Next 가 NULL 인 경우 N1의 Next도 NULL 로 만들어 버리면 자동으로 N1이 Tail이 되겠지요.
Head의 경우는 따로 Head를 명시해주어야 해서 Append 함수를 만들 때와 같이 매개변수로 Head 를 하나 더 넣어서 구현 합니다.
구현한 삭제 연산입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
//Head의 값을 직접 수정하는 Call by reference 함수
void SLL_RemoveNode(Node** Head, Node* Remove)
{
if (*Head == Remove)
{
//삭제 할 함수가 Head 인 경우 Head를 다음 노드로 설정한다.
*Head = Remove->NextNode;
}
else
{
Node* Current = *Head;
/**************************************************************
* Current != NULL은 Remove 가 리스트내에 존재하지 않는 경우.
리스트의 끝까지 탐색 하게 될 경우 마지막 Tail의 NextNode는 NULL이므로
NULL 포인터에 접근하는 오류를 막기 위해 존재하는 조건식입니다.
***************************************************************/
while (Current != NULL && Current->NextNode != Remove)
{
Current = Current->NextNode;
}
if (Current != NULL)
Current->NextNode = Remove->NextNode;
}
}
|
cs |
주석에도 적혀 있듯이, Remove 가 List 내에 존재하지 않을 경우, Current 가 Head부터 해서 쭉쭉 탐색해 나가는 과정 끝에 Tail에 다다르면 Current->NextNode 가 NULL이 될 것입니다.
이것을 Current가 값 복사로 가지게 되죠. Current는 NULL 포인터가 되었습니다. 여기까지는 오케이.
하지만 if문에 Current != NULL 이 없다면 어떻게 될까요?
Current -> NextNode 시점에서 널 참조 오류(Null Reference Exeption)가 발생하는것이 자명합니다.
NULL 은 참조 할 수 없는 메모리인데 NULL안에서 맴버를 꺼내와라 하고 있으니까요.
프로그램이 비정상적으로 종료 될 위기에 처하죠.
이를 막기 위해 Current != NULL 조건을 추가 해 준 것이죠.
결국 삭제 동작은 다음 노드가 Remove 인 노드를 탐색하면서 내려가다가 그 노드를 만나면.
Remove의 다음 노드를 해당 노드의 다음노드에 연결 하고 끝입니다.
만약 Remove 가 Tail이라면?
Current는 Remove 바로 전까지 리스트를 종단 하면서 내려 올 것이고 최종적으로 Tail의 바로 전 노드가 될 것입니다.
Tail(Remove).NextNode = NULL 이죠? (Tail 이므로)
Current.NextNode = Tail.NextNode 는 NULL 값의 복사 이므로 오류 없이 잘 작동합니다.
Current.NextNode가 NULL 이 됨으로서 Current가 자연스럽게 Tail이 되고, Remove는 이제 삭제 해도 상관 없는 노드가 됩니다.
노드 삽입 (Insert Node)
노드 삽입의 경우 노드 삭제(Remove)를 반대로 하면 된다고 이해해도 무방합니다.
void SLL_InsertNode(Node* Current, Node* Insert)
{
Insert->NextNode = Current->NextNode;
Current->NextNode = Insert;
}Current 다음에 Insert 를 삽입하도록 한 코드입니다.
짧은 코드이며 그림으로 보면 주석 없이도 이해하기가 어렵지 않습니다.
노드 개수 세기 (Count)
노드의 개수를 세는 연산도 구현 해 봅니다.
int SLL_GetNodeCount(Node* Head)
{
//cnt 초기화
int cnt = 0;
Node* tempNode = Head;
//while문이 순환하는 조건은 TailNode를 만날 때(포함) 까지이다.
//TailNode->NextNode 가 NULL 이기 때문에.
while (tempNode != NULL)
{
tempNode = tempNode->NextNode;
++cnt;
}
return cnt;
}
'자료구조와 알고리즘' 카테고리의 다른 글
| 스택(Stack) - 배열로 구현하기 (0) | 2023.07.31 |
|---|
