http://clrs.skanev.com/10/02/05.html
Implement the dictionary operations INSERT, DELETE, and SEARCH using singly linked, circular lists. What are the running times of your procedures?
I assume this should use a sentinel. Otherwise, there is no good way to terminate the search. We can track a pointer and abort when we reach it again, but not all languages allow us to compare pointers that way.
INSERT: O(1), simply insert at the head of the list.
DELETE: O(n), you'll have to first search for the element in the list. For searching in the worst case
you've to compare with every node in the linked list.
SEARCH: O(n), reason is same as of above.
https://github.com/gzc/CLRS/blob/master/C10-Elementary-Data-Structures/exercise_code/dict.cpp
http://clrs.skanev.com/10/02/05.html
Implement the dictionary operations INSERT, DELETE, and SEARCH using singly linked, circular lists. What are the running times of your procedures?
I assume this should use a sentinel. Otherwise, there is no good way to terminate the search. We can track a pointer and abort when we reach it again, but not all languages allow us to compare pointers that way.
INSERT: O(1), simply insert at the head of the list.
DELETE: O(n), you'll have to first search for the element in the list. For searching in the worst case
you've to compare with every node in the linked list.
SEARCH: O(n), reason is same as of above.
https://github.com/gzc/CLRS/blob/master/C10-Elementary-Data-Structures/exercise_code/dict.cpp
http://clrs.skanev.com/10/02/05.html
typedef struct node_t { int key; struct node_t *next; } node_t; typedef struct { struct node_t nil; } list_t; void init_list(list_t *list) { list->nil.key = 0; list->nil.next = &(list->nil); } void destroy_list(list_t *list) { node_t *node = list->nil.next; node_t *next; while (node != &(list->nil)) { next = node->next; free(node); node = next; } } void insert(list_t *list, int key) { node_t *new = (node_t *) malloc(sizeof(node_t)); new->key = key; new->next = list->nil.next; list->nil.next = new; } node_t *search(list_t *list, int key) { node_t *node = list->nil.next; // The trick from exercise 10.2.4 list->nil.key = key; while (node->key != key) { node = node->next; } if (node == &(list->nil)) { return NULL; } else { return node; } } void delete(list_t *list, int key) { node_t *node = &(list->nil); while (node->next != &(list->nil)) { if (node->next->key == key) { node_t *to_be_deleted = node->next; node->next = node->next->next; free(to_be_deleted); } else { node = node->next; } } }