Skip to content

Instantly share code, notes, and snippets.

@icheishvili
Created December 2, 2012 19:40
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save icheishvili/4190607 to your computer and use it in GitHub Desktop.
Save icheishvili/4190607 to your computer and use it in GitHub Desktop.
Linked List in C with Iterator
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;
}
@sagarsuman00
Copy link

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment