C언어에서는 배열은 크기의 고정으로 유연하게 변경할 수 없다는 단점이 있습니다.
이를 해결하기 위해 리스트의 자료구조를 사용합니다.
리스트는 스택, 큐 등의 자료 구조를 구현에 사용됩니다.
링크드 리스트(Linked List)
링크드 리스트는 각 노드의 연결로 구성되어 있습니다.
노드는 데이터를 보관하는 필드와 다음 노드를 연결해줄 포인터로 구성됩니다.
▲ 단일 노드의 구성
노드를 여러 개를 만들고 포인터에 다음 노드에 대한 포인터를 사용하면 연결 리스트가 됩니다.
연결 리스트의 맨 앞 노드는 Head이고, 마지막 노드는Tail입니다.
▲ 연결 리스트의 구성
이렇게 노드를 통해 연결을 해주면, 필요할 경우 새 노드를 만들어서 연결해주면 됩니다.
구현
그럼 C 언어로 노드를 표현해봅시다!
|
1
2
3
4
5
|
typedef struct tageNode
{
int Data;
struct tageNode* NextNode;
} Node;
|
▲ struct를 사용한 구조체로 노드를 표현합니다.
이전 그림에서의 노드 한 개를 만들었다고 생각하면 됩니다.
데이터를 담을 공간인 Data와 다음 노드를 가리킬 포인터 변수인 NextNode를 만들어줍니다. (Data를 담을 자료형은 자유롭게 설정 가능합니다.)
이때 구조체를 간편하게 사용하기 위해서 typedef를 사용해줍니다. ▶ struct의 번거로움 때문입니다! 코드도 길어지고 가독성도
노드에 대한 구조체를 만들었고 노드를 생성해봅시다!!
( 생성의 개념은 한 번에 이해가 안 될 수 있는데, 프로그램에서 사용될 공간에서 넣는다는 개념으로 이해했습니다. 특정 함수에서 사용할 것인지, 아님 전역으로 사용할 것인지 )
이때 노드에 대한 생성 함수가 끝나도 해당 노드가 제거되지 않고 계속 사용할 수 있도록 자유 저장소에 만들어줘야 합니다.
▶ 메모리 공간 참조 링크 - 이건 꼭 알고 있어야 합니다.(만들 예정)
우리는 C언어에서 malloc() 함수를 통해 자유 저장소에 메모리를 할당할 수 있습니다.
|
1
|
Node* NewNode = (Node*)malloc(sizeof(Node));
|
▲ malloc 함수로 sizeof 연산자로 Node 크기만큼을 자유 저장소에서 할당하여 NewNode에 메모리 주소를 저장합니다.
malloc() 함수는 다음 포스트를 참고해주세요.
https://codeomni.tistory.com/885
c언어 총정리8 - 메모리 관리와 동적 할당 - malloc, calloc, realloc, free 함수
메모리 구성 프로그램 실행 시 운영체제에 의해 마련되는 메모리의 구조는 코드, 데이터, 힙, 스택 영역으로 구분된다. 코드 영역 - 프로그램의 코드가 저장, CPU가 저장된 명령문을 하나씩 가져
codeomni.tistory.com
단일 연결 리스트의 연산
노드의 구조체를 만들고 자유 저장소에서 할당까지 했습니다.
해당 노드를 가지고 자료 구조를 구현해봅시다!!
자료구조를 사용할 때는 데이터를 추가하거나 삭제, 변경 등을 합니다.
배열을 가지고 데이터를 넣거나 빼고 연산을 하는 것처럼!
링크드 리스트를 만들고 포함된 자료를 사용하기 위해 사용하는 연산은 다음과 같습니다.
- 노드 생성, 소멸
- 노드 추가
- 노드 삽입
- 노드 삭제
- 노드 탐색
여기서 추가는 Tail 뒤에 이어서 노드를 생성해주는 것이고 삽입은 특정 위치에 새로운 노드를 넣어주는 것입니다.
1. 노드 생성
먼저 노드의 생성입니다.
|
1
2
3
4
5
6
7
8
9
10
|
// SLL 노드 생성
Node* SSL_CreateNode(int NewData)
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = NewData;
NewNode->NextNode = NULL;
return NewNode;
}
|
▲ 노드를 생성하는 함수로 생성된 노드의 주소를 반환합니다.
malloc으로 노드 구조체의 크기만큼 자유 저장소에서 할당받아서 NewNode에 메모리 주소를 저장합니다.생성된 노드에 데이터를 저장해주고 다음 노드에 대한 포인터를 NULL로 초기화 합니다.
2. 노드 소멸
노드의 소멸은 생성보다 간단합니다.
자유 저장소에 생성된 노드를 해제해주면 됩니다!!
free() 함수로 노드의 주소를 넘겨주면 소멸됩니다.
|
1
2
3
4
5
|
// SLL 노드 소멸
void SLL_DestroyNode(Node* Node)
{
free(Node);
}
|
▲ free() 함수로 노드를 소멸시킵니다.
3. 노드 추가
노드 하나로만 자료를 구현할 수 없습니다!
종이를 엮어서 책을 만드는 것처럼 노드를 연결해봅시다.
▲ tail 뒤에 새로운 노드를 연결해줍니다.
노드 구조체의 다음 노드의 포인터를 사용해서 다음 노드의 위치를 알려줍니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// SLL 노드 추가
void SLL_AppendNode(Node** Head, Node* NewNode)
{
if ((*Head) == NULL)
{
*Head = NewNode;
}
else
{
Node* Tail = (*Head);
while (Tail->NextNode != NULL)
{
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
}
}
|
Tail 뒤에 노드를 연결해줍니다.
노드가 하나도 없을 경우 새 노드를 추가해주고 해당 노드는 Head가 됩니다.
4. 노드 탐색
연결 리스트의 헤드부터 원하는 노드까지 순차적으로 탐색을 해줍니다.
여기서 SLL의 단점이 보이는데 다음 노드에 대한 포인터만 가지고 있기 때문에 head 부터 tail까지 순차적으로만 탐색이 가능하는 것입니다. (이중 연결 리스트를 구현하는 이유)
|
1
2
3
4
5
6
7
8
9
10
11
|
// SLL 노드 탐색
Node* SLL_GetNode(Node* Head, int Location)
{
Node* Current = Head;
while (Current != NULL && (--Location) >= 0)
{
Current = Current->NextNode;
}
return Current;
}
|
Head부터 원하는 노드가 나올 때까지 while문을 통해서 탐색합니다.
while문을 사용하는 이유에 대해서 생각해볼만 한데, 노드의 개수를 얼마나 만들지, 사용할지 모르기 때문에 사용합니다.
5. 노드 삽입
노드와 노드 사이에 새 노드를 만들어줍니다.
우리는 노드 안에 포인터를 이용해서 추가를 해주면 되는데 이 때 다음 포인터을 잘 연결(저장)해줘야 노드를 잃어버리는 미아 상태가 되지 않습니다.
따라서, 새로 만든 노드에 다음 포인터를 이전 노드가 가리키고 있는 포인터를 연결해주고 이전 노드의 포인터를 새 노드에 연결시켜주면 됩니다.
|
1
2
3
4
5
6
|
// SLL 노드 삽입
void SLL_InsertNode(Node* Current, Node* NewNode)
{
NewNode->NextNode = Current->NextNode;
Current->NextNode = NewNode;
}
|
▲ 먼저 새 노드의 포인터를 현재 노드의 다음 주소를 연결해줍니다.
6. 노드 삭제
이번 기능의 구현은 생각보다 어려울 수 있습니다.
중간에 노드를 삭제하면 포인터들이 끊어져서 어떻게 연결해줄지 고민해야 하기 때문입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
// SLL 노드 제거
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;
}
}
}
|
탐색처럼 while문을 사용해서 제거할 노드를 찾고 먼저 해당 노드의 다음 노드를 이전 노드의 포인터에 연결합니다.
연결은 끊은 노드는 연결 리스트에만 없고 자유 저장소에는 아직 메모리가 할당된 상태로 남아 있기 때문에 free를 해주는 소멸 함수로 제거합니다.
7. 노드 개수
연결 리스트 안에 노드의 총 개수를 구하는 함수입니다.
알고리즘 문제를 풀었던 것처럼 Count 변수를 하나 만들고 while문을 통해서 개수를 세주면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// SLL 노드 개수
int SLL_GetNodeCount(Node* Head)
{
int Count = 0;
Node* Current = Head;
while (Current != NULL)
{
Current = Current->NextNode;
Count++;
}
return Count;
}
|
▲ 현재 노드인 Head부터 마지막 노드까지 순차적으로 탐색합니다.
댓글