자료구조

[자료구조_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) {
    *= (Node*)malloc(sizeof(Node));
    (*H)->next = *H;
    (*H)->prev = *H;
}
 
Node * createNode( T_DATA data ){
    Node *= (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페이지 교체 방식