-
Notifications
You must be signed in to change notification settings - Fork 1
/
list.h
112 lines (80 loc) · 1.79 KB
/
list.h
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#ifndef _LIST
#define _LIST
typedef struct NODE{
Generic data;
struct NODE *next;
struct NODE *previous;
}NODE;
typedef struct LIST{
Generic (*cmp_func)();
struct NODE *head;
struct NODE *tail;
}LIST;
Generic LIST_Create(Generic (*cmp_func)()){
LIST *new_list = (LIST *) malloc(sizeof(LIST));
new_list->head = NULL;
new_list->tail = NULL;
new_list->cmp_func = cmp_func;
return new_list;
}
Generic LIST_Is_Empty(LIST *list){
return (list->head == NULL);
}
Generic LIST_Enqueue(LIST *list, Generic data, Integer *comparisons){
NODE *new_node = (NODE *) malloc(sizeof(NODE));
new_node->data = data;
if(list->head == NULL){
new_node->next = NULL;
new_node->previous = NULL;
list->head = new_node;
list->tail = new_node;
(*comparisons)++;
}
else{
if(list->cmp_func(data, list->head->data)){
list->head->previous = new_node;
new_node->next = list->head;
new_node->previous = NULL;
list->head = new_node;
(*comparisons)++;
}
else{
NODE *curr = list->head->next;
while(curr != NULL){
if(list->cmp_func(data, curr->data)){
new_node->next = curr;
new_node->previous = curr->previous;
curr->previous->next = new_node;
curr->previous = new_node;
return;
}
curr = curr->next;
(*comparisons)++;
}
list->tail->next = new_node;
new_node->previous = list->tail;
new_node->next = NULL;
list->tail = new_node;
}
}
}
Generic LIST_Peek(LIST *list){
return list->head->data;
}
Generic LIST_Pop(LIST *list, Integer *comparisons){
if(LIST_Is_Empty(list)){
return 0;
}
NODE *dequeued = list->head;
if(list->head->next == NULL){
list->head = NULL;
list->tail = NULL;
}
else{
list->head = list->head->next;
list->head->previous = NULL;
}
(*comparisons)++;
return dequeued->data;
}
#endif