C 알고리즘 연결 리스트 - sonkoni/Koni-Wiki GitHub Wiki
단일 연결리스트 특징
- 리스트 중간 지점에 노드를 손쉽게 추가하거나 삭제할 수 있다.
- 특정 노드를 찾으려면 노드를 모두 검색해야 한다(최악의 경우)
- 크기가 고정되어 있지 않다.
┌ head ┐ ┌─▶┌ node1 ┐ ┌─▶┌ node1 ┐
│next ─┼─┘ │next ──┼─┘ │next ──┼──▶ NULL
╞══════╡ ╞═══════╡ ╞═══════╡
│data: │ │data:10│ │data:20│
└──────┘ └───────┘ └───────┘
head: 머리노드. 단일 연결 리스트의 기준점. 데이터를 저장하지 않는다.
node: 데이터가 저장되는 실제 노드.
NULL: 꼬리를 나타낸다.
#include <stdio.h>
#include <stdlib.h>
struct Node {
struct Node *next;
int data;
};
int main(int argc, char *argv[]) {
/************ 구성하기 ************/
// 머리 노드 생성
struct Node *head = malloc(sizeof(struct Node));
// 첫 번째
struct Node *node1 = malloc(sizeof(struct Node));
head->next = node1;
node1->data = 10;
// 두 번째
struct Node *node2 = malloc(sizeof(struct Node));
node1->next = node2;
node2->data = 20;
// 꼬리 NULL 처리
node2->next = NULL;
/************ 사용 ************/
// 현재 노드를 만들고 첫 번째 노드를 저장한다.
// 루프로 NULL 이 아닐 때까지 순회한다.
struct Node *curr = head->next;
while (curr != NULL) {
printf("%d\n", curr->data);
curr = curr->next;
}
// 해제는 역순
free(node2);
free(node1);
free(head);
return 0;
}
// 10
// 20#include <stdio.h>
#include <stdlib.h>
struct Node {
struct Node *next;
int data;
};
// 타겟 노드 뒤에 새 노드 추가
void addNext(struct Node *target, int data) {
struct Node *newNode = malloc(sizeof(struct Node));
newNode->next = target->next;
newNode->data = data;
target->next = newNode;
}
int main(int argc, char *argv[]) {
// 머리 노드 생성
struct Node *head = malloc(sizeof(struct Node));
head->next = NULL;
addNext(head, 30);
addNext(head, 20);
addNext(head, 10);
struct Node *curr = head->next;
while (curr != NULL) {
printf("%d\n", curr->data);
curr = curr->next;
}
// 해제
// 다시 현재노드를 헤드로 맞추고, 모든 노드를 순회하면서 현재 노드를 해제
curr = head->next;
while (curr != NULL) {
struct Node *next = curr->next;
free(curr);
curr = next; // 현재노드 변수에 next를 심어서 루프를 다시 돈다.
}
head->next = curr;
free(head);
return 0;
}
// 10
// 20
// 30#include <stdio.h>
#include <stdlib.h>
struct Node {
struct Node *next;
int data;
};
void addNext(struct Node *target, int data) {
struct Node *newNode = malloc(sizeof(struct Node));
newNode->next = target->next;
newNode->data = data;
target->next = newNode;
}
// 타겟노드 바로 다음 노드를 삭제
void delNext(struct Node *target) {
struct Node *rmNode = target->next;
target->next = rmNode->next;
free(rmNode);
}
int main(int argc, char *argv[]) {
struct Node *head = malloc(sizeof(struct Node));
head->next = NULL;
addNext(head, 30);
addNext(head, 20);
addNext(head, 10);
// 방금 추가한 항목 하나 제거해보기
delNext(head);
struct Node *curr = head->next;
while (curr != NULL) {
printf("%d\n", curr->data);
curr = curr->next;
}
curr = head->next;
while (curr != NULL) {
struct Node *next = curr->next;
free(curr);
curr = next;
}
head->next = curr;
free(head);
return 0;
}
// 20
// 30함수 내부 NULL 검사를 하지 않으면 코드가 위험해진다.
#include <stdio.h>
#include <stdlib.h>
struct Node {
struct Node *next;
int data;
};
void addNext(struct Node *target, int data) {
// 타겟노드가 NULL 이면 함수 끝냄
if (target == NULL) {
return;
}
struct Node *newNode = malloc(sizeof(struct Node));
// 메모리 할당에 실패하면 함수 끝냄
if (newNode == NULL) {
return;
}
newNode->next = target->next;
newNode->data = data;
target->next = newNode;
}
void delNext(struct Node *target) {
// 타겟노드가 NULL 이면 함수 끝냄
if (target == NULL) {
return;
}
struct Node *rmNode = target->next;
// 삭제하려는 노드가 NULL 이면 함수 끝냄
if (rmNode == NULL) {
return;
}
target->next = rmNode->next;
free(rmNode);
}
int main(int argc, char *argv[]) {
struct Node *head = malloc(sizeof(struct Node));
head->next = NULL;
addNext(head, 30);
addNext(head, 20);
addNext(head, 10);
delNext(head);
struct Node *curr = head->next;
while (curr != NULL) {
printf("%d\n", curr->data);
curr = curr->next;
}
curr = head->next;
while (curr != NULL) {
struct Node *next = curr->next;
free(curr);
curr = next;
}
head->next = curr;
free(head);
return 0;
}