오늘도 돌아온 자료구조 시간!! 오늘은 C++로 연결 리스트를 구현해보겠습니다.
기본적인 개념은 생략하고 코드 구현을 중심으로 글을 써보도록 하겠습니다.
typedef int Data;
typedef struct _Node {
Data item; // 리스트 요소의 내용
struct _Node *next; // 자기참조구조체, 다음 노드를 가리키기 위함
} Node;
typedef struct {
Node *head; // 연결 리스트의 head
int len; // 연결 리스트의 길이
} LinkedList;
먼저 위 코드로 구조체를 정의합니다.
void InitList(LinkedList *plist) {
plist->head = (Node *) malloc(sizeof(Node));
plist->head->next = NULL; // dummy node
plist->len = 0;
}
우리는 리스트의 삽입와 삭제를 보다 편한 방법으로 하기 위해 더미 노드를 필요로 합니다. 이건 나중에 아래에 설명하겠습니다.
bool IsEmpty(LinkedList *plist) {
return plist->len == 0;
}
리스트의 길이가 0일 경우 true를 반환하는 아주 간단한 함수입니다.
리스트를 삽입 또는 삭제하는 데에 가능한 케이스는 다양합니다.
이런 경우를 다 고려해서 각각 코드를 짜기에는 너무 불편합니다.
그래서 우리는 하나의 통합된 솔루션을 알아볼겁니다.
더미 노드는 말 그대로 아무 기능도 없는 가짜 노드를 말합니다.
위 사진은 삽입을 예시로 든 것인데 아무것도 없는 더미 노드를 리스트의 head로 지정하면 삽입과 삭제의 여러가지 경우에 대해 똑같은 솔루션을 사용할 수 있습니다.
void InsertMiddle(LinkedList *plist, int pos, Data item) {
Node *cur, *newNode; // 각각 현재 위치, 새로운 노드
if (pos < 0 || pos > plist->len)
exit(1);
newNode = (Node *) malloc(sizeof(Node));
newNode->item = item;
newNode->next = NULL; // 새로운 노드를 만들어냅니다.
cur = plist->head;
for (int i = 0; i < pos; i++) // 삽입하고자 하는 위치로 이동
cur = cur->next;
newNode->next = cur->next; // 새 노드를 삽입하고자 하는 위치의 다음 노드와 연결
cur->next = newNode; // 현재 위치의 다음 노드는 새 노드가 될 것!
plist->len++; // 리스트 길이 증가
}
일련의 과정을 개조식으로 정리하자면 이렇습니다.
1. 새 노드 만들기
2. 노드를 넣을 위치의 전 위치로 cur 포인터 옮기기
3. 새 노드를 cur 포인터의 다음 노드에 연결
4. cur 포인터의 다음 노드는 새 노드가 될 것 이기 때문에 둘을 연결
5. 리스트 길이 증가
void RemoveMiddle(LinkedList *plist, int pos) {
Node *cur, *temp;
if (IsEmpty(plist) || pos < 0 || pos >= plist->len)
exit(1);
cur = plist->head;
for (int i = 0; i < pos; i++)
cur = cur->next;
temp = cur->next;
cur->next = cur->next->next; // cur->next->next == temp->next
plist->len--;
free(temp); // 요소 삭제
}
삽입과 원리는 비슷합니다.
K번째 노드를 삭제한다 치면..
1. cur 포인터를 (K-1) 번째 위치로 이동합니다.
2. temp 포인터를 K번째 노드에 지정합니다.
3. (K-1) 번째 노드와 (K+1) 번째 노드를 연결시킵니다.
4. K 번째 노드(temp)를 제거합니다.
Data ReadItem(LinkedList *plist, int pos) {
Node *cur;
if (IsEmpty(plist) || pos < 0 || pos >= plist->len)
exit(1);
cur = plist->head->next;
for (int i = 0; i < pos; i++)
cur = cur->next;
return cur->item;
}
인자로 위치를 받아 원하는 위치의 요소를 반환합니다.
void PrintList(LinkedList* plist) {
for (Node* cur = plist->head->next; cur != NULL; cur = cur->next)
cout << cur->item;
cout << "\n";
}
cur 포인터를 계속 이동시키며 요소를 출력시킵니다.
void ClearList(LinkedList* plist) {
// 계속 첫 노드만을 삭제하며 모든 노드를 삭제하는 것
while (plist->head->next != NULL)
RemoveMiddle(plist, 0);
free(plist->head);
}
메모리 누수를 방지하기 위해 리스트를 삭제합니다.
int main() {
LinkedList list;
InitList(&list);
InsertMiddle(&list, 0, 1);
InsertMiddle(&list, 1, 2);
InsertMiddle(&list, 2, 3);
PrintList(&list);
RemoveMiddle(&list, 1);
PrintList(&list);
ClearList(&list);
return 0;
}
삽입/삭제의 간단한 예제를 작성해보았습니다.
123
13
코드에 따라 올바르게 실행되는 것을 확인할 수 있습니다.