단방향 연결리스트의 연결리스트와 노드 구조체 선언
typedef struct node{
int item;
struct node *next; // typedef 선언했음에도 struct 선언 필요
}node;
typedef struct list{
int cnt;
node *head;
node *tail;
}list;
cnt는 연결리스트의 노드 개수. 연결리스트의 head는 첫 노드, 실제 값이 들어가지는 않으며 head에 연결될 다음노드부터 값이 들어간다. tail노드는 연결리스트의 마지막 노드, 노드 추가시 tail 다음에 연결된다.
연결리스트 초기화
void init(list *l) {
node *head = (node *)malloc(sizeof(node));
head->next = NULL;
l->head = head;
l->tail = NULL;
l->cnt = 0;
return;
}
연결리스트의 head노드를 만들어주고 tail노드는 없으므로 NULL. 만약 연결리스트에 실제 값이 들어가는 노드가 하나라면 그 노드는 tail
노드 추가
void insert(list *l, int item) {
node *tmp = (node *)malloc(sizeof(node));
tmp->item = item;
tmp->next = NULL;
l->cnt++;
if (l->tail == NULL) {
l->head->next = tmp;
}
else {
l->tail->next = tmp;
}
l->tail = tmp;
return;
}
추가될 tmp노드를 만든 후 값을 입력해주고, tmp는 마지막 노드이므로 tmp의 다음 노드는 NULL을 입력한다. 그리고 연결리스트에 head를 제외하고 노드가 없다면(l->tail == NULL) 연결될 첫 노드이므로 head 다음으로 연결해주고 첫 노드가 아니라면 tail 다음으로 연결해준다. 마지막으로 tail의 주소를 tmp로 바꿔준다.
노드 삭제
void delete(list *l, int item) {
node *cur = l->head;
while (cur->next != NULL) {
if (cur->next->item == item) {
node *tmp = cur->next; // 지워질 노드
if (cur->next == l->tail) {
cur->next = NULL;
l->tail = cur;
}
else {
cur->next = cur->next->next;
}
free(tmp);
break;
}
cur = cur->next;
}
l->cnt--;
return;
}
값을 입력받아서 이 값과 같은 노드가 있으면 그 노드를 삭제한다.
반복문으로 head부터 다음 노드가 지울 값을 가지는지 확인한다. (반복문으로 노드를 탐색하는방법은 아래 노드 전체 출력함수가 같은 원리로 간단하게 구현되어 있다.) 이때 현재 노드가 아닌 다음노드가 지워질 노드인지 확인해야한다. 다음 노드가 지워질 노드라면 현재노드를 다음 다음 노드와 연결해주기 위함이다. 만약 현재 노드가 지워질 노드라면 이전 노드의 주소를 기억하고 있지 않아서 이전 노드와 다음노드를 연결할 수 없다. 지워질 노드가 tail(다음 노드가 tail)이면 현재노드의 다음노드를 null, 현재노드를 tail로 바꿔준다.
지워질 노드가 tail이 아니면 현재노드의 다음노드는 그 다음노드로 연결해준다. 그리고 free로 현재노드의 다음노드는 힙영역에서 지워준다.
노드 전체 출력
void print(list *l) {
node *cur = l->head->next;
while (cur != NULL) {
printf("%d ", cur->item);
cur = cur->next;
}
}
전체 코드
#include <stdlib.h>
#include <stdio.h>
typedef struct node{
int item;
struct node *next; // typedef 선언했음에도 struct 선언 필요
}node;
typedef struct list{
int cnt;
node *head;
node *tail;
}list;
void init(list *l) {
node *head = (node *)malloc(sizeof(node));
head->next = NULL;
l->head = head;
l->tail = NULL;
l->cnt = 0;
return;
}
void insert(list *l, int item) {
node *tmp = (node *)malloc(sizeof(node));
tmp->item = item;
tmp->next = NULL;
l->cnt++;
if (l->tail == NULL) {
l->head->next = tmp;
}
else {
l->tail->next = tmp;
}
l->tail = tmp;
return;
}
void delete(list *l, int item) {
node *cur = l->head;
while (cur->next != NULL) {
if (cur->next->item == item) {
node *tmp = cur->next;
if (cur->next == l->tail) {
cur->next = NULL;
l->tail = cur;
}
else {
cur->next = cur->next->next;
}
free(tmp);
break;
}
cur = cur->next;
}
l->cnt--;
return;
}
void print(list *l) {
node *cur = l->head->next;
while (cur != NULL) {
printf("%d ", cur->item);
cur = cur->next;
}
}
int main() {
list l;
init(&l);
insert(&l, 10);
insert(&l, 11);
delete(&l, 10);
delete(&l, 11);
insert(&l, 12);
insert(&l, 13);
print(&l);
printf("\nnum : %d", l.cnt);
}