Some suggestions follow.
1/ Comment your code. It won't affect at all how the code does its job (unless you do something silly like comment out a vital line of code), but it will affect the ability to maintain that code. The programmers that follow you may well praise or curse your name depending on this.
2/ Since you have a few operations that work on the end of the list, you can speed things up by caching that somewhere. I suggest that the best way to do this is to have a list data structure, separate from the node one, something like:
struct node {
int data; // or whatever the actual payload is.
struct node *next;
}
struct list {
struct node *first;
struct node *last;
size_t count;
}
This will allow you to quickly get at the last element for push_back/pop_back
(but see next item). Caching the length in the list structure will also turn the count()
call into an O(1)
operation instead of O(n)
.
It's also more logical since it makes little sense to call pop_back()
passing a node that isn't the last node - these are list operations, not node ones. A classic example of wrongness with the current method is if you call count()
passing in a node that's not the head. It will only count items from there until the end.
Now that may be what you intended but the lack of comments (see point 1) do not make it clear.
3/ Consider using a doubly linked list even if you think you only need a singly linked one. It makes insertions and deletions a lot easier, not needing a list traversal to find a node's predecessor for example.
Granted it's a little wasteful to have two pointers for every integer in the list but that's also true of a singly linked list. In general, list payloads tend to be more substantial.
4/ Things fail, allow for that. For example, you should be detecting malloc
failure and handling it. In addition, you should be indicating to the caller if they do something silly, like:
- popping on an empty list;
- passing in a NULL pointer;
- trying to retrieve an index beyond the end of the list.
The functions that currently return void
are easy to fix, you simply have them return an error code instead. The trickier ones are those that already return something useful (and, of course, limited to those that can actually fail), these need to be able to indicate failure and return that useful thing.
5/ Consider separating your monolithic code into a form more usable by a client. That means providing stuff in a header file for the client to include, and removing test/exercise code into a separate source file so it's not included in clients that don't need it.
6/ Better typing. C has had a proper boolean type for a while now, and size_t
is a more natural fit for counting things (you'll never have -42
items in a list, for example).
7/ Sit down with a pen and paper and actually "run" your code in certain scenarios. This will catch any errors in your logic related to missing a step, such as forgetting to set or change a pointer in the mode.
Alternatively, add a debug
function that prints out the internal structures in such a way that a core dump will not prevent you from seeing it. That often involves flushing the data at multiple levels (the fflush/fsync
sequence).
With all that taken into account, this code is one example of how to do it. First, the header file, separate for reasons explained above, and with documentation for clients.
Note the comment at the top about preferring an opaque pointer to enforce encapsulation. I haven't done that in this answer but you can look here to get an idea on how to do it.
#include <stdbool.h>
#include <stddef.h>
// Do NOT use these structures from outside (they really
// should be opaque). All access should be via the API
// functions only.
struct s_node {
int data; // Payload.
struct s_node *next; // NULL for tail.
struct s_node *prev; // NULL for head.
};
struct s_list {
size_t count; // Other fields valid only if count > 0.
struct s_node *first;
struct s_node *last;
};
// This is the start of the public API stuff that clients can use.
// Needless to say, all functions below receiving a list must get a
// properly created one (from init_list). You can also call
// free_list(NULL) to mirror free(NULL)..
enum e_error {
OKAY = 0, // Operation succeeded.
NO_MEMORY, // Allocation failure.
EMPTY_LIST, // Cannot do to empty list.
BAD_INDEX, // Index beyond list length.
};
// Returns new empty list object. Return NULL if no memory.
struct s_list *init_list();
// Frees everything to do with a list. No errors possible.
void free_list(struct s_list *list);
// Places an item before the current first item, or adds to the list
// if empty. Can return NO_MEM or OK.
enum e_error push_front(struct s_list *list, int data);
// Places an item after the current last item, or adds to the list
// if empty. Can return NO_MEM or OK.
enum e_error push_back(struct s_list *list, int data);
// Pops the item from the front of list into int pointer, NULL
// means throw away. Can return EMPTY_LIST or OK.
enum e_error pop_front(struct s_list *list, int *p_data);
// Pops the item from the back of list into int pointer, NULL
// means throw away. Can return EMPTY_LIST or OK.
enum e_error pop_back(struct s_list *list, int *p_data);
// Returns true if value found in list, false ortherwise.
bool contains(struct s_list *list, int data);
// Returns number of nodes is in list.
size_t count(struct s_list *list);
// Returns number of times a specific value is in list.
size_t count_with(struct s_list *list, int data);
// Gives the value at an index. Can return BEYOND or OK.
enum e_error get_elem_at(struct s_list *list, size_t offset, int *p_data);
Next, the code itself. Modifications are mostly listed in the numbered points at the start of this answer but I've also changed count()
into count_with()
and provided a count()
that counts all elements regardless of value. That's so you can see the value of the caching the count in the list structure.
#include <stdlib.h>
#include "prog.h"
struct s_list *init_list(void) {
// Allocate new list, failing if no memory.
struct s_list *list = malloc(sizeof(struct s_list));
if (list == NULL) {
return NULL;
}
// Mark list as empty.
list->count = 0;
return list;
}
void free_list(struct s_list *list) {
// Allow NULL input as no-operation.
if (list == NULL) {
return;
}
// First, free all nodes (count is in control, not first).
if (list->count > 0) {
struct s_node *node = list->first;
while (node != NULL) {
struct s_node *corpse_node = node;
node = node->next;
free(corpse_node);
}
}
// Then free the list itself.
free(list);
}
enum e_error push_front(struct s_list *list, int data) {
// Allocate new node, failing if no memory.
struct s_node *node = malloc(sizeof(struct s_node));
if (node == NULL) {
return NO_MEMORY;
}
// These are identical for empty/non-empty lists.
node->data = data;
node->prev = NULL;
// Simple case if list currently empty.
if (list->count == 0) {
node->next = NULL;
list->count = 1;
list->first = list->last = node;
return OKAY;
}
// List has a first element so insert before it.
node->next = list->first;
list->first->prev = node;
list->first = node;
list->count++;
return OKAY;
}
enum e_error push_back(struct s_list *list, int data) {
// Allocate new node, failing if no memory.
struct s_node *node = malloc(sizeof(struct s_node));
if (node == NULL) {
return NO_MEMORY;
}
// These are identical for empty/non-empty lists.
node->data = data;
node->next = NULL;
// Simple case if list currently empty.
if (list->count == 0) {
node->prev = NULL;
list->count = 1;
list->first = list->last = node;
return OKAY;
}
// List has a last element so insert after it.
node->prev = list->last;
list->last->next = node;
list->last = node;
list->count++;
return OKAY;
}
enum e_error pop_front(struct s_list *list, int *p_data) {
// Not allowed on empty list.
if (list->count == 0) {
return EMPTY_LIST;
}
// Save stuff needed to free.
struct s_node *node = list->first;
if (p_data != NULL) {
*p_data = node->data;
}
// Adjust list.
list->first = node->next;
list->first->prev = NULL;
list->count--;
// Free and return.
free(node);
return OKAY;
}
enum e_error pop_back(struct s_list *list, int *p_data) {
// Not allowed on empty list.
if (list->count == 0) {
return EMPTY_LIST;
}
// Save stuff needed to free.
struct s_node *node = list->last;
if (p_data != NULL) {
*p_data = node->data;
}
// Adjust list.
list->last = node->prev;
list->last->next = NULL;
list->count--;
// Free and return.
free(node);
return OKAY;
}
bool contains(struct s_list *list, int data) {
// Count is in control.
if (list->count == 0) {
return false;
}
// Check each mode, return immediately if found.
struct s_node *node = list->first;
while (node->next != NULL) {
if (node->data == data) {
return true;
}
node = node->next;
}
return false;
}
size_t count(struct s_list *list) {
// Cached info, no need to traverse list.
return list->count;
}
size_t count_with(struct s_list *list, int data) {
// Count is in control.
if (list->count == 0) {
return 0;
}
// Check each mode, counting matches.
struct s_node *node = list->first;
size_t count = 0;
while (node->next != NULL) {
if (node->data == data) {
++count;
}
}
return count;
}
enum e_error get_elem_at(struct s_list *list, size_t offset, int *p_data) {
// Count limits what you can get to.
if (offset >= list->count) {
return BAD_INDEX;
}
// Find node at given index and return its data.
struct s_node *node = list->first;
while (offset > 0) {
node = node->next;
offset--;
}
*p_data = node->data;
return OKAY;
}
Then the modified test program, with the mentioned debugging function to check for things like invalid pointers and such (ensuring a core dump doesn't happen before all output is fully flushed).
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "prog.h"
void debug(char *desc, struct s_list *list) {
printf("===== List @ %p (%s)\n", (void*)list, desc);
fflush(stdout); fsync(fileno(stdout));
printf(" count = %zu\n", list->count);
fflush(stdout); fsync(fileno(stdout));
printf(" first = %p\n", (void*)(list->first));
fflush(stdout); fsync(fileno(stdout));
printf(" last = %p\n", (void*)(list->last));
fflush(stdout); fsync(fileno(stdout));
struct s_node * node = list->first;
while (node != NULL) {
printf(" Node @ %p\n", (void*)node);
fflush(stdout); fsync(fileno(stdout));
printf(" data = %d\n", node->data);
fflush(stdout); fsync(fileno(stdout));
printf(" prev = %p\n", (void*)(node->prev));
fflush(stdout); fsync(fileno(stdout));
printf(" next = %p\n", (void*)(node->next));
fflush(stdout); fsync(fileno(stdout));
node = node->next;
}
printf("-----\n");
fflush(stdout); fsync(fileno(stdout));
}
void print_list(struct s_list *list) {
int data;
size_t i = 0;
while (get_elem_at(list, i, &data) == OKAY) {
printf("offset %zu: %d\n", i++, data);
}
}
void check_err(enum e_error err_code, char *desc) {
if (err_code == OKAY) {
return;
}
printf("Error %d while %s\n", err_code, desc);
}
int main(int argc, char *argv[]) {
int data;
struct s_list *list = init_list();
debug("after init", list);
if (list != NULL) {
check_err(push_back(list, 10), "pushing back 10");
debug("after push 10", list);
check_err(push_back(list, 20), "pushing back 20");
debug("after push 20", list);
check_err(push_back(list, 30), "pushing back 30");
debug("after push 30", list);
check_err(push_back(list, 40), "pushing back 40");
debug("after push 40", list);
print_list(list);
check_err(pop_back(list, &data), "popping back");
debug("after pop 40", list);
print_list(list);
free_list(list);
}
return 0;
}
And, finally, the output of that modified test program so you can see the detailed structures after each modification:
===== List @ 0x555a3e7502a0 (after init)
count = 0
first = (nil)
last = (nil)
-----
===== List @ 0x555a3e7502a0 (after push 10)
count = 1
first = 0x555a3e7506d0
last = 0x555a3e7506d0
Node @ 0x555a3e7506d0
data = 10
prev = (nil)
next = (nil)
-----
===== List @ 0x555a3e7502a0 (after push 20)
count = 2
first = 0x555a3e7506d0
last = 0x555a3e7506f0
Node @ 0x555a3e7506d0
data = 10
prev = (nil)
next = 0x555a3e7506f0
Node @ 0x555a3e7506f0
data = 20
prev = 0x555a3e7506d0
next = (nil)
-----
===== List @ 0x555a3e7502a0 (after push 30)
count = 3
first = 0x555a3e7506d0
last = 0x555a3e750710
Node @ 0x555a3e7506d0
data = 10
prev = (nil)
next = 0x555a3e7506f0
Node @ 0x555a3e7506f0
data = 20
prev = 0x555a3e7506d0
next = 0x555a3e750710
Node @ 0x555a3e750710
data = 30
prev = 0x555a3e7506f0
next = (nil)
-----
===== List @ 0x555a3e7502a0 (after push 40)
count = 4
first = 0x555a3e7506d0
last = 0x555a3e750730
Node @ 0x555a3e7506d0
data = 10
prev = (nil)
next = 0x555a3e7506f0
Node @ 0x555a3e7506f0
data = 20
prev = 0x555a3e7506d0
next = 0x555a3e750710
Node @ 0x555a3e750710
data = 30
prev = 0x555a3e7506f0
next = 0x555a3e750730
Node @ 0x555a3e750730
data = 40
prev = 0x555a3e750710
next = (nil)
-----
offset 0: 10
offset 1: 20
offset 2: 30
offset 3: 40
===== List @ 0x555a3e7502a0 (after pop 40)
count = 3
first = 0x555a3e7506d0
last = 0x555a3e750710
Node @ 0x555a3e7506d0
data = 10
prev = (nil)
next = 0x555a3e7506f0
Node @ 0x555a3e7506f0
data = 20
prev = 0x555a3e7506d0
next = 0x555a3e750710
Node @ 0x555a3e750710
data = 30
prev = 0x555a3e7506f0
next = (nil)
-----
offset 0: 10
offset 1: 20
offset 2: 30