Name: Anonymous 2011-08-19 20:33
I have implemented linked lists in C as a learning exercise. I'm a noob ass so tell me how my implementation sucks and I will fix it. I didn't have a particular use-case in mind when I wrote it.
Header:
C file:
Testcase:
Header:
// llist.h
#ifndef LLIST_H_
#define LLIST_H_
struct LList;
typedef struct LList LList;
struct LLNode;
typedef struct LLNode LLNode;
struct LList {
LLNode *front, *back;
};
struct LLNode {
void *data;
LLNode *next;
};
LList* llist_new(LList **self);
void llist_add(LList *self, void *v);
void llist_remove(LList *self, LLNode *node);
void llist_insert(LLNode *node, void *v);
void llist_destroy(LList *self);
#endifC file:
// llist.c
#include <assert.h>
#include <stdlib.h>
#include "llist.h"
// Initialize a new, empty LList, in dynamically allocated memory.
LList *llist_new(LList **self) {
*self = malloc(sizeof (LList));
if (self == NULL) { return NULL; }
(*self)->front = NULL;
(*self)->back = NULL;
return *self;
}
// Append a value to the LList. Creates a new node.
void llist_add(LList *self, void *v) {
LLNode *node = malloc(sizeof (LLNode));
assert(node != NULL);
node->data = v;
node->next = NULL;
// Put this node at the back of the list.
if (self->front != NULL) {
self->back->next = node;
self->back = node;
} else {
self->back = node;
self->front = node;
}
}
// Iterate over the LList to locate a node, and then remove it from the list.
void llist_remove(LList *self, LLNode *node) {
LLNode *iter_node = self->front;
LLNode *prev_node = NULL;
while (iter_node != NULL) {
if (iter_node == node) {
if (prev_node != NULL) { prev_node->next = iter_node->next; }
else { self->front = NULL; }
free(iter_node);
return;
}
prev_node = iter_node;
iter_node = iter_node->next;
}
}
// Insert a value after a particular node.
void llist_insert(LLNode *node, void *v) {
LLNode *next = node->next;
LLNode *new_node = malloc(sizeof (LLNode));
new_node->data = v;
new_node->next = next;
node->next = new_node;
}
void llist_destroy(LList *self) {
LLNode *iter_node = self->front;
while (iter_node != NULL) {
LLNode *next = iter_node->next;
free(iter_node);
iter_node = next;
}
free(self);
}Testcase:
// llist_test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "llist.h"
#ifdef _WIN32
char *strdup(char *s);
#endif
int main(void) {
LList *phone_nums;
LLNode *iter;
if (llist_new(&phone_nums) == NULL) { printf("Out of memory."); exit(1); }
llist_add(phone_nums, strdup("123-4567")); // Yes, I should free() these later...
llist_add(phone_nums, strdup("890-1234"));
llist_add(phone_nums, strdup("567-8901"));
llist_add(phone_nums, strdup("234-5678"));
LLNode *temp = NULL;
iter = phone_nums->front;
while (iter) {
printf("%s\n", (char*)iter->data);
if (!strcmp("890-1234", (char*)iter->data)) { temp = iter; }
iter = iter->next;
}
puts("");
llist_insert(temp, strdup("BEEP BOOP"));
iter = phone_nums->front;
while (iter) {
printf("%s\n", (char*)iter->data);
if (!strcmp("567-8901", (char*)iter->data)) { temp = iter; }
iter = iter->next;
}
puts("");
llist_remove(phone_nums, temp);
iter = phone_nums->front;
while (iter) {
printf("%s\n", (char*)iter->data);
if (!strcmp("567-8901", (char*)iter->data)) { temp = iter; }
iter = iter->next;
}
llist_destroy(phone_nums);
return 0;
}
#ifdef _WIN32
char *strdup(char *s) {
char *p = malloc(strlen(s) + 1);
strcpy(p, s);
return p;
}
#endif