1) ์๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ๋จธ๋ฆฌ(Head)์ ๊ผฌ๋ฆฌ(Tail)๋ฅผ ๋ชจ๋ ๊ฐ์ง๋ค๋ ํน์ง์ด ์๋ค
2) ์๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๊ฐ ๋
ธ๋๋ ์ ๋
ธ๋์ ๋ค ๋
ธํธ์ ์ ๋ณด๋ฅผ ๋ชจ๋ ์ ์ฅํ๊ณ ์๋ค
1) ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ ์ธํ๊ธฐ
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int data;
struct Node *prev; // ์ ๋
ธ๋์
struct Node *next; // ๋ค ๋
ธ๋ ์ ์ธ
} Node;
Node *head, *tail;
2) ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ฝ์
// ์๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ฝ์
ํจ์
void insert(int data) {
Node* node = (Node*) malloc(sizeof(Node)); // ์๋ก์ด ๋
ธ๋ ํ ๋น
node->data = data; // ๋ฐ์ดํฐ ์ด๊ธฐํ
Node* cur;
cur = head->next;
while (cur->data < data && cur != tail) {
cur = cur->next; // cur๋ณ์๊ฐ ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ๋ณ๊ฒฝ
}
Node* prev = cur->prev; // ์ฝ์
ํ ๋
ธ๋์ ์ ๋
ธ๋๋ฅผ prev๋ก ์ค์
prev->next = node; // ์ ๋
ธ๋์ next๊ฐ ํ์ฌ ์ฝ์
ํ ๋
ธ๋๋ฅผ ๋ฐ๋ผ๋ณด๊ฒ ํ๊ณ
node->prev = prev; // ๋
ธ๋์ prev๊ฐ ์ ๋
ธ๋๊ฐ ๋๊ณ
cur->prev = node; // ๋ค ๋
ธ๋์ prev๊ฐ ๋
ธ๋๊ฐ ๋๊ณ
node->next = cur; // ๋
ธ๋์ next๊ฐ ์ฝ์
ํ ๋
ธ๋์ ๋ฐ๋ก ๋ค์ ๋ค์ด๊ฐ ๋
ธ๋๊ฐ ๋ ์ ์๋๋ก
}
3) ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ญ์
// ์๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ญ์ ํจ์
void removeFront() {
Node* node = head->next;
head->next = node->next;
Node* next = node->next;
next->prev = head; free(node);
}
4) ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ถ๋ ฅ
// ์๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ ์ฒด ์ถ๋ ฅ ํจ์
void show() {
Node* cur = head->next;
while (cur != tail) {
printf("%d ", cur->data);
cur = cur->next;
}
}
5) ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ฌ์ฉํ๊ธฐ
int main(void) {
head = (Node*) malloc(sizeof(Node));
tail = (Node*) malloc(sizeof(Node));
head->next = tail;
head->prev = head;
tail->next = tail;
tail->prev = head;
insert(2);
insert(1);
insert(3);
insert(9);
insert(7);
removeFront();
show();
system("pause");
return 0;
}