1. 단일 연결 리스트의 C 구현
ㅇ 구조체, 포인터, 함수, 동적 메모리 할당을 사용하여 구현
ㅇ 노드의 구조체 정의
- struct Node { struct Node *next; int data; }
. struct Node *next : Node 구조체로 만든 다른 노드의 주소를 가리킴
ㅇ 구조체 포인터에 동적 메모리 할당
- struct 구조체이름 *구조체포인터이름 = malloc(sizeof(struct 구조체이름))
ㅇ (추가편집중)
2. 노드 2개인 단일 연결 리스트 구현 例)
ㅇ 구현 소스
#include <stdio.h> // printf()
#include <string.h> // strcpy()
#include <stdlib.h> // malloc(), free()
typedef struct ListNode { // 연결 리스트의 노드 구조체
struct ListNode *next; // 다음 노드 주소를 저장할 포인터
char label[10]; // 라벨이름
int data; // 데이터
} Node;
void displayAll(Node *head) { // 반복적으로 리스트 노드들을 방문하고, 각 노드 메모리 해제
Node *curr = head->next; // 순회용 포인터에 첫째 노드의 주소 저장
printf("(head) -> "); // 머리 노드 출력
while(curr != NULL) { // 순회용 포인터가 NULL이 아니면 계속 노드를 방문
if(curr->next != NULL) printf("(%s) %d -> ", curr->label, curr->data); // 현재 노드의 데이터 출력
else printf("(%s) %d -> ", curr->label, curr->data); // 꼬리 노드의 출력
curr = curr->next; // 순회용 포인터에 다음 노드의 주소 저장
}
printf("NULL \n");
}
Node *addAfter(Node *target, char *label, int data) { // 타깃 노드 뒤에 새 노드 생성 삽입
Node *newNode = malloc(sizeof(Node)); // 새 노드 생성
if(newNode != NULL) printf("새 노드 %s의 메모리 할당 OK \n", label);
newNode->next = target->next; // 새 노드의 다음 노드에 타깃 노드의 다음 노드를 지정
strcpy(newNode->label,label); // 새 노드에 라벨이름 저장
newNode->data = data; // 새 노드에 데이터 저장
target->next = newNode; // 타킷 노드의 다음 노드에 새 생성 노드를 지정
return newNode;
}
void removeAfter(Node *target) { // 타깃 노드의 다음 노드를 삭제
Node *removeNode = target->next; // 타깃 노드의 다음 노드 주소를 저장
target->next = removeNode->next; // 타깃 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정
printf("%s 메모리 해제 \n", removeNode->label);
free(removeNode);
}
void freeAll(Node *head) {
Node *curr = head->next; // 순회용 포인터에 첫째 노드의 주소 저장
printf("%s 메모리 해제 ",head->label);
free(head); // 현재 노드 메모리 해제
Node *temp; // 다음 노드 주소를 임시 저장하려는 노드
while(curr != NULL) { // 순회용 포인터가 NULL이 아니면 계속 노드를 방문
temp = curr->next; // 현재 노드의 다음 노드 주소를 임시로 저장
printf("%s 메모리 해제 ", curr->label);
free(curr); // 현재 노드 메모리 해제
curr = temp; // 순회용 포인터에 다음 노드 주소 저장
}
printf("\n");
}
int main() {
Node *head = malloc(sizeof(Node)); // 구조체 포인터에 메모리 할당하며, 머리 노드 즉, 연결 리스트 생성
strcpy(head->label,"head"); // 라벨이름 저장
head->next = NULL; // 다음 노드 주소
displayAll(head); // 연결 리스트 차례로 방문 출력
addAfter(head,"node1",10); // node1을 헤드 노드 뒤에 삽입
displayAll(head); // 연결 리스트 차례로 방문 출력
addAfter(head,"node2",20); // node2을 헤드 노드의 뒤에 삽입
displayAll(head); // 연결 리스트 차례로 방문 출력
Node *node3 = addAfter(head,"node3",30); // node3을 헤드 노드의 뒤에 삽입
displayAll(head); // 연결 리스트 차례로 방문 출력
removeAfter(node3); // node3의 다음 노드 node2를 삭제
displayAll(head); // 연결 리스트 차례로 방문 출력
freeAll(head); // 연결 리스트 전체를 차례대로 메모리 해제
return 0;
}
ㅇ 수행 결과
(head) -> NULL
새 노드 node1의 메모리 할당 OK
(head) -> (node1) 10 -> NULL
새 노드 node2의 메모리 할당 OK
(head) -> (node2) 20 -> (node1) 10 -> NULL
새 노드 node3의 메모리 할당 OK
(head) -> (node3) 30 -> (node2) 20 -> (node1) 10 -> NULL
node2 메모리 해제
(head) -> (node3) 30 -> (node1) 10 -> NULL
head 메모리 해제 node3 메모리 해제 node1 메모리 해제