Created
December 2, 2012 19:40
-
-
Save icheishvili/4190607 to your computer and use it in GitHub Desktop.
Linked List in C with Iterator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct list_node { | |
void* data; | |
struct list_node* next; | |
}; | |
struct list { | |
struct list_node* head; | |
}; | |
struct list* list_create() { | |
struct list* l = malloc(sizeof(struct list)); | |
l->head = NULL; | |
return l; | |
} | |
size_t list_size(struct list* l) { | |
size_t size = 0; | |
struct list_node* curr = l->head; | |
while (curr) { | |
size++; | |
curr = curr->next; | |
} | |
return size; | |
} | |
void list_free(struct list* l, bool free_data) { | |
struct list_node* curr = l->head; | |
struct list_node* next; | |
while (curr) { | |
next = curr->next; | |
if (free_data) { | |
free(curr->data); | |
} | |
free(curr); | |
curr = next; | |
} | |
free(l); | |
} | |
void list_lpush(struct list* l, void* data) { | |
struct list_node* node = malloc(sizeof(struct list_node)); | |
node->next = l->head; | |
node->data = data; | |
l->head = node; | |
} | |
void* list_lpop(struct list* l) { | |
void* rdata = NULL; | |
struct list_node* rnode = NULL; | |
if (l->head) { | |
rnode = l->head; | |
l->head = rnode->next; | |
rdata = rnode->data; | |
free(rnode); | |
} | |
return rdata; | |
} | |
void list_rpush(struct list* l, void* data) { | |
struct list_node* curr = l->head; | |
struct list_node** entryp = &l->head; | |
while (curr) { | |
entryp = &curr->next; | |
curr = curr->next; | |
} | |
struct list_node* node = malloc(sizeof(struct list_node)); | |
node->next = NULL; | |
node->data = data; | |
*entryp = node; | |
} | |
void* list_rpop(struct list* l) { | |
struct list_node* curr = l->head; | |
if (!curr) { | |
return NULL; | |
} | |
while (curr && curr->next && curr->next->next) { | |
curr = curr->next; | |
} | |
struct list_node* rnode; | |
void* rdata; | |
if (curr->next) { | |
rnode = curr->next; | |
rdata = rnode->data; | |
curr->next = rnode->next; | |
} else { | |
rnode = curr; | |
rdata = rnode->data; | |
l->head = NULL; | |
} | |
free(rnode); | |
return rdata; | |
} | |
struct list_iterator { | |
struct list* list; | |
struct list_node* curr; | |
struct list_node** entryp; | |
}; | |
void* list_remove(struct list_iterator* it) { | |
struct list_node* rnode = NULL; | |
void* rdata = NULL; | |
if (it->curr) { | |
rnode = it->curr; | |
rdata = rnode->data; | |
it->curr = rnode->next; | |
*it->entryp = rnode->next; | |
free(rnode); | |
} | |
return rdata; | |
} | |
struct list_iterator* list_iterator_create(struct list* l) { | |
struct list_iterator* it = malloc(sizeof(struct list_iterator)); | |
it->list = l; | |
it->curr = l->head; | |
it->entryp = &l->head; | |
return it; | |
} | |
struct list_iterator* list_iterator_copy(struct list_iterator* it) { | |
struct list_iterator* copy = malloc(sizeof(struct list_iterator)); | |
copy->list = it->list; | |
copy->curr = it->curr; | |
copy->entryp = it->entryp; | |
return copy; | |
} | |
void* list_iterator_next(struct list_iterator* it) { | |
void* data = NULL; | |
if (it->curr) { | |
data = it->curr->data; | |
it->entryp = &it->curr->next; | |
it->curr = it->curr->next; | |
} | |
return data; | |
} | |
bool list_iterator_has_next(struct list_iterator* it) { | |
return it->curr != NULL; | |
} | |
void list_iterator_free(struct list_iterator* it) { | |
free(it); | |
} | |
void list_reverse(struct list* l) { | |
struct list_node* curr = l->head; | |
struct list_node* next = NULL; | |
struct list_node* prev = NULL; | |
while (curr) { | |
next = curr->next; | |
curr->next = prev; | |
prev = curr; | |
curr = next; | |
} | |
l->head = prev; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
How does iterator handles multi threading? Suppose In one threading I am traversing using the iterator and in some other thread I deleted one node that the iterator was about to access. How does this code handles this situation?