Skip to content

Instantly share code, notes, and snippets.

@meylingtaing
Last active September 24, 2024 15:49
Show Gist options
  • Save meylingtaing/11018042 to your computer and use it in GitHub Desktop.
Save meylingtaing/11018042 to your computer and use it in GitHub Desktop.
A generic linked list library for C
/* llist.c
* Generic Linked List implementation
*/
#include <stdlib.h>
#include <stdio.h>
#include "llist.h"
llist *llist_create(void *new_data)
{
struct node *new_node;
llist *new_list = (llist *)malloc(sizeof (llist));
*new_list = (struct node *)malloc(sizeof (struct node));
new_node = *new_list;
new_node->data = new_data;
new_node->next = NULL;
return new_list;
}
void llist_free(llist *list)
{
struct node *curr = *list;
struct node *next;
while (curr != NULL) {
next = curr->next;
free(curr);
curr = next;
}
free(list);
}
// Returns 0 on failure
int llist_add_inorder(void *data, llist *list,
int (*comp)(void *, void *))
{
struct node *new_node;
struct node *curr;
struct node *prev = NULL;
if (list == NULL || *list == NULL) {
fprintf(stderr, "llist_add_inorder: list is null\n");
return 0;
}
curr = *list;
if (curr->data == NULL) {
curr->data = data;
return 1;
}
new_node = (struct node *)malloc(sizeof (struct node));
new_node->data = data;
// Find spot in linked list to insert new node
while (curr != NULL && curr->data != NULL && comp(curr->data, data) < 0) {
prev = curr;
curr = curr->next;
}
new_node->next = curr;
if (prev == NULL)
*list = new_node;
else
prev->next = new_node;
return 1;
}
void llist_push(llist *list, void *data)
{
struct node *head;
struct node *new_node;
if (list == NULL || *list == NULL) {
fprintf(stderr, "llist_add_inorder: list is null\n");
}
head = *list;
// Head is empty node
if (head->data == NULL)
head->data = data;
// Head is not empty, add new node to front
else {
new_node = malloc(sizeof (struct node));
new_node->data = data;
new_node->next = head;
*list = new_node;
}
}
void *llist_pop(llist *list)
{
void *popped_data;
struct node *head = *list;
if (list == NULL || head->data == NULL)
return NULL;
popped_data = head->data;
*list = head->next;
free(head);
return popped_data;
}
void llist_print(llist *list, void (*print)(void *))
{
struct node *curr = *list;
while (curr != NULL) {
print(curr->data);
printf(" ");
curr = curr->next;
}
putchar('\n');
}
/* llist.h
* Generic Linked List
*/
struct node {
void *data;
struct node *next;
};
typedef struct node * llist;
/* llist_create: Create a linked list */
llist *llist_create(void *data);
/* llist_free: Free a linked list */
void llist_free(llist *list);
/* llist_add_inorder: Add to sorted linked list */
int llist_add_inorder(void *data, llist *list,
int (*comp)(void *, void *));
/* llist_push: Add to head of list */
void llist_push(llist *list, void *data);
/* llist_pop: remove and return head of linked list */
void *llist_pop(llist *list);
/* llist_print: print linked list */
void llist_print(llist *list, void (*print)(void *data));
#include <stdio.h>
#include "llist.h"
#define COUNT sizeof numbers / sizeof (int)
#define COUNT2 sizeof more_numbers / sizeof (int)
int numcmp(void *, void *);
void numprint(void *);
int main()
{
int numbers[] = {3, 8, 23, 1, 8, 45, 3, 11, 15, 12, 42, 9, 0, 53, 15};
int more_numbers[] = {7, 10, 4, 11};
llist *my_list = llist_create(NULL);
unsigned int i;
// Print out the empty list
llist_print(my_list, numprint);
// Add all of the numbers
for (i = 0; i < COUNT; i++)
llist_add_inorder((void *)(numbers + i), my_list, numcmp);
// Print out list of sorted numbers
llist_print(my_list, numprint);
// Remove first five numbers
for (i = 0; i < COUNT2; i++)
llist_pop(my_list);
// Print list again
llist_print(my_list, numprint);
// Add numbers to front
for (i = 0; i < COUNT2; i++)
llist_push(my_list, &more_numbers[i]);
// Print list once again
llist_print(my_list, numprint);
// Free the list
llist_free(my_list);
return 0;
}
int numcmp(void *a, void *b)
{
if (*(int *)a < *(int *)b)
return -1;
if (*(int *)a > *(int *)b)
return 1;
return 0;
}
void numprint(void *num)
{
int *pnum = (int *)num;
if (num == NULL)
return;
printf("%d", *pnum);
}
llist_driver: llist.o main.c
gcc -Wall -Wextra llist.o main.c -o llist_driver
llist.o: llist.h llist.c
gcc -Wall -Wextra -fPIC llist.h -c llist.c
clean:
rm -rf *.o *.gch llist_driver
@bwack
Copy link

bwack commented Sep 22, 2019

llist *new_list = (llist *)malloc(sizeof (llist));
*new_list = (struct node *)malloc(sizeof (struct node));

Is this leaky ?

@MartinChekurov
Copy link

Yes, it is.

@MichalBan
Copy link

MichalBan commented May 13, 2021

llist_pop() causes seg fault if passed llist is NULL.
This can be easly fixed by changing line 113

    if (list == NULL || head->data == NULL)

to

    if (list == NULL || !head || head->data == NULL)

Then it will just return NULL instead.

@DevelopmentHF
Copy link

DevelopmentHF commented Apr 9, 2024

llist *new_list = (llist *)malloc(sizeof (llist));
*new_list = (struct node *)malloc(sizeof (struct node));

Is this leaky ?

@MartinChekurov @bwack
How might you go about tweaking this

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