자료구조
[자료구조_Day2]Double Circular Linked List
Whatman
2018. 10. 28. 23:45
■Double Circular Linked List■
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | void initDCLL(Node **H) { *H = (Node*)malloc(sizeof(Node)); (*H)->next = *H; (*H)->prev = *H; } Node * createNode( T_DATA data ){ Node *t = (Node*)malloc(sizeof(Node)); t->data = data; t->next = NULL; t->prev = NULL; return t; } void _insertNode(Node *newnode, Node *P, Node *N) { newnode->prev = P; newnode->next = N; P->next = newnode; N->prev = newnode; } typedef struct { char *Name; char *PhoneNo; } Phonebook; typedef struct _Node { T_DATA data; struct _Node *prev; struct _Node *next; } Node; #define insertAfterNode(newnode, T) _insertNode(newnode, T, T->next) void AddPhoneBook(void) { Phonebook newpb; Node *temp = NULL; if(Head==NULL) { temp=createNode(newpb); Head->next=temp; Head->prev=temp; } else { temp=createNode(newpb); insertAfterNode(temp, Head->next); } } | cs |
이중 환형 리스트는 이중 연결 리스트와 비슷하지만 차이점은 tail이 없다는 것입니다.
사용 예 : <재시도 페이지 교체>
-사용 가능한 페이지를 재할당하는 등의 페이지 할당/교체 방식
-Swap disk
-Page replacement algorithm
-메모리 공간의 제약으로 인해 동시에 모든 자료를 메모리에 올려 놓을 수가 없다.
(-> 빈번한 교체가 이루어져야 한다.)
-LRU페이지 교체 방식