Going through classic data structures and have stopped on linked lists.Just implemented a circular singly-linked list, but I'm under overwhelming impression that this list could be expressed in a more elegant manner, remove_node function in particular. Keeping in mind efficiency and code readability, could anybody present a more concise and efficient solution for singly-linked circular list?
#include <stdio.h>
#include <stdlib.h>
struct node{
struct node* next;
int value;
};
struct list{
struct node* head;
};
struct node* init_node(int value){
struct node* pnode;
if (!(pnode = (struct node*)malloc(sizeof(struct node)))){
return NULL;
}
else{
pnode->value = value;
}
return pnode;
}
struct list* init_list(){
struct list* plist;
if (!(plist = (struct list*)malloc(sizeof(struct list)))){
return NULL;
}
plist->head = NULL;
return plist;
}
void remove_node(struct list*a plist, int value){
struct node* current, *temp;
current = plist->head;
if (!(current)) return;
if ( current->value == value ){
if (current==current->next){
plist->head = NULL;
free(current);
}
else {
temp = current;
do {
current = current->next;
} while (current->next != plist->head);
current->next = plist->head->next;
plist->head = current->next;
free(temp);
}
}
else {
do {
if (current->next->value == value){
temp = current->next;
current->next = current->next->next;
free(temp);
}
current = current->next;
} while (current != plist->head);
}
}
void print_node(struct node* pnode){
printf("%d %p %p\n", pnode->value, pnode, pnode->next);
}
void print_list(struct list* plist){
struct node * current = plist->head;
if (!(current)) return;
if (current == plist->head->next){
print_node(current);
}
else{
do {
print_node(current);
current = current->next;
} while (current != plist->head);
}
}
void add_node(struct node* pnode,struct list* plist){
struct node* current;
struct node* temp;
if (plist->head == NULL){
plist->head = pnode;
plist->head->next = pnode;
}
else {
current = plist->head;
if (current == plist->head->next){
plist->head->next = pnode;
pnode->next = plist->head;
}
else {
while(current->next!=plist->head)
current = current->next;
current->next = pnode;
pnode->next = plist->head;
}
}
}
Take a look at the circular linked list in the Linux kernel source: http://lxr.linux.no/linux+v2.6.36/include/linux/list.h
Its beauty derives from the fact that you don't have a special struct for your data to fit in the list, you only have to include the struct list_head *
in the struct you want to have as a list. The macros for accessing items in the list will handle the offset calculation to get from the struct list_head
pointer to your data.
A more verbose explanation of the linked list used in the kernel can be found at kernelnewbies.org/FAQ/LinkedLists (Sorry, I dont have enough karma to post two hyperlinks).
Edit: Well, the list is a double-linked list and not a single-linked one like you have, but you could adopt the concept and create your own single-linked list.