๐ŸŒˆ ์ž๋ฃŒ๊ตฌ์กฐ:: ์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ

Aprilยท2021๋…„ 10์›” 14์ผ
1
post-thumbnail

๐Ÿš€ What I Will Learn

  • ์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ๋™์ž‘ ์›๋ฆฌ์™€ ๊ตฌํ˜„ ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ์ตํžˆ๊ธฐ...

์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ

1๏ธโƒฃ ์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ž€?

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) ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์‚ฝ์ž…

  • [ 1 ]: ์‚ฝ์ž…ํ•  ๋…ธ๋“œ์˜ ์•ž ๋…ธ๋“œ๊ฐ€, ์‚ฝ์ž… ํ•  ๋…ธ๋“œ๋ฅผ ๋ฐ”๋ผ๋ณด๊ฒŒ ํ•œ๋‹ค
  • [ 2 ]: ์‚ฝ์ž…ํ•  ๋…ธ๋“œ๊ฐ€ ์•ž ๋…ธ๋“œ๋ฅผ ๋ฐ”๋ผ๋ณด๊ฒŒ ํ•œ๋‹ค
    • ์ด๋•Œ ์‚ฝ์ž…ํ•  ๋…ธ๋“œ์™€ ์‚ฝ์ž…ํ•  ๋…ธ๋“œ์˜ ์•ž ๋…ธ๋“œ๊ฐ€ ์„œ๋กœ ๋ฐ”๋ผ๋ณด๋Š” ํ˜•ํƒœ
  • [ 3 ]: ์‚ฝ์ž…ํ•  ๋…ธ๋“œ์˜ ๋’ค ๋…ธ๋“œ๊ฐ€, ์‚ฝ์ž… ํ•  ๋…ธ๋“œ๋ฅผ ๋ฐ”๋ผ๋ณด๊ฒŒ ํ•œ๋‹ค
  • [ 4 ]: ์‚ฝ์ž…ํ•  ๋…ธ๋“œ๊ฐ€ ๋’ค ๋…ธ๋“œ๋ฅผ ๋ฐ”๋ผ๋ณด๊ฒŒ ํ•œ๋‹ค
    • ์ด๋•Œ ์‚ฝ์ž…ํ•  ๋…ธ๋“œ์™€ ์‚ฝ์ž…ํ•  ๋…ธ๋“œ์˜ ๋’ค ๋…ธ๋“œ๊ฐ€ ์„œ๋กœ ๋ฐ”๋ผ๋ณด๋Š” ํ˜•ํƒœ

// ์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์‚ฝ์ž… ํ•จ์ˆ˜
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) ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์‚ญ์ œ

  • [ 1 ]: ์‚ญ์ œํ•  ๋…ธ๋“œ์˜ ์•ž ๋…ธ๋“œ๊ฐ€ ์‚ญ์ œํ•  ๋…ธ๋“œ์˜ ๋’ค๋ฅผ ๋ฐ”๋ผ๋ณด๊ฒŒ ํ•œ๋‹ค
  • [ 2 ]: ์‚ญ์ œํ•  ๋…ธ๋“œ์˜ ๋’ค ๋…ธ๋“œ๊ฐ€ ์‚ญ์ œํ•  ๋…ธ๋“œ์˜ ์•ž์„ ๋ฐ”๋ผ๋ณด๊ฒŒ ํ•œ๋‹ค
  • [ 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;
}




โœจ tl;dr

  • ์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์—์„œ๋Š” ๊ฐ ๋…ธ๋“œ๊ฐ€ ์•ž ๋…ธ๋“œ์™€ ๋’ค ๋…ธ๋“œ์˜ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๊ณ  ์žˆ๋‹ค
  • ์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉํ•˜๋ฉด ๋ฆฌ์ŠคํŠธ์˜ ์•ž์—์„œ๋ถ€ํ„ฐ ํ˜น์€ ๋’ค์—์„œ๋ถ€ํ„ฐ ๋ชจ๋‘ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋‹ค
profile
๐Ÿš€ ๋‚ด๊ฐ€ ๋ณด๋ ค๊ณ  ์“ฐ๋Š” ๊ธฐ์ˆ ๋ธ”๋กœ๊ทธ

0๊ฐœ์˜ ๋Œ“๊ธ€