Repository navigation
Expand file tree
/
Copy pathcircularlinkedlist.h
More file actions
189 lines (173 loc) · 5.2 KB
/
Copy pathcircularlinkedlist.h
File metadata and controls
189 lines (173 loc) · 5.2 KB
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#ifndef CIRCULARLINKEDLIST_JL
#define CIRCULARLINKEDLIST_JL
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
// Define how our circular node is structured.
typedef struct CNode{
int data; // The value of the node that we need to store.
struct CNode* next; // The pointer to the next node. The last node points to the first one.
} CNode;
// Define how our (linear and dynamic) circular linked list is structured.
// We only keep the tail: the head is always tail->next, so both ends are reached in O(1).
typedef struct{
CNode* tail; // The pointer to the last node in our list (null if it's empty).
int size; // The number of elements (nodes) in our list.
} CircularLinkedList;
/********************/
/* FUNCTIONS */
/********************/
// Set Up the Circular Linked List. We start setting the tail pointer to null and size to 0.
void initCircularLinkedList(CircularLinkedList *list){
list->tail = NULL;
list->size = 0;
}
// Create a New Circular Node. Returns the new node or null if there's no memory.
CNode* createCNode(int value){
CNode* newNode = (CNode*)malloc(sizeof(CNode));
if(!newNode){
return NULL;
}
newNode->data = value;
newNode->next = newNode;
return newNode;
}
// Check if the List is Empty. Returns 1 if it's empty or 0 if it has elements.
int isEmptyCircular(CircularLinkedList *list){
if(list->tail == NULL){
return 1;
}
else{
return 0;
}
}
// Insert at the Beginning of the List. Returns 1 if successful or 0 if the new node is not created.
int insertAtHeadCircular(CircularLinkedList *list, int value){
CNode* newNode = createCNode(value);
if(!newNode){
return 0;
}
else{
if(list->tail == NULL){
list->tail = newNode;
}
else{
newNode->next = list->tail->next;
list->tail->next = newNode;
}
list->size++;
return 1;
}
}
// Insert at the End of the List. Returns 1 if successful or 0 if the new node is not created.
int insertAtTailCircular(CircularLinkedList *list, int value){
if(!insertAtHeadCircular(list, value)){
return 0;
}
else{
// The new node is the head, so moving the tail one step forward makes it the last one.
list->tail = list->tail->next;
return 1;
}
}
// Delete the First Node. Returns 1 if successful or 0 if the list is empty.
int deleteAtHeadCircular(CircularLinkedList *list, int *value){
if(isEmptyCircular(list)){
return 0;
}
else{
CNode* head = list->tail->next;
*value = head->data;
if(head == list->tail){
list->tail = NULL;
}
else{
list->tail->next = head->next;
}
free(head);
list->size--;
return 1;
}
}
// Delete a Node by Value (First One is Deleted). Returns 1 if successful or 0 if the value is not found.
int deleteByValueCircular(CircularLinkedList *list, int value){
if(isEmptyCircular(list)){
return 0;
}
else{
CNode* prev = list->tail;
CNode* temp = list->tail->next;
for(int i = 0; i < list->size; i++){
if(temp->data == value){
if(temp == prev){
list->tail = NULL;
}
else{
prev->next = temp->next;
if(temp == list->tail){
list->tail = prev;
}
}
free(temp);
list->size--;
return 1;
}
prev = temp;
temp = temp->next;
}
return 0;
}
}
// Search for a Value in the List. Returns 1 if found or 0 if it's not.
int searchCircular(CircularLinkedList *list, int value){
if(isEmptyCircular(list)){
return 0;
}
CNode* temp = list->tail->next;
for(int i = 0; i < list->size; i++){
if(temp->data == value){
return 1;
}
temp = temp->next;
}
return 0;
}
// Rotate the List one Position: the first element becomes the last one. Returns 1 if successful or 0 if the list is empty.
int rotateCircular(CircularLinkedList *list){
if(isEmptyCircular(list)){
return 0;
}
else{
list->tail = list->tail->next;
return 1;
}
}
// Print all Elements of the List. Displays elements from first to last one (one full turn).
void printCircularLinkedList(CircularLinkedList *list){
printf("[");
if(!isEmptyCircular(list)){
CNode* temp = list->tail->next;
for(int i = 0; i < list->size; i++){
printf("%d", temp->data);
if(i < list->size-1){
printf(", ");
}
temp = temp->next;
}
}
printf("]\n");
}
// Free all the Nodes and Reset the List.
void freeCircularLinkedList(CircularLinkedList *list){
if(!isEmptyCircular(list)){
CNode* temp = list->tail->next;
for(int i = 0; i < list->size; i++){
CNode* nextNode = temp->next;
free(temp);
temp = nextNode;
}
}
initCircularLinkedList(list);
}
#endif //CIRCULARLINKEDLIST_JL