Skip to content

Instantly share code, notes, and snippets.

@coderodde
Created October 2, 2017 05:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save coderodde/61f1650018335a772aeee54d39d256b1 to your computer and use it in GitHub Desktop.
Save coderodde/61f1650018335a772aeee54d39d256b1 to your computer and use it in GitHub Desktop.
Demo driver for linked list C code question
#include "singly_linked_list.h"
#include <stdio.h>
#include <string.h>
int main() {
int i;
singly_linked_list_t* list = singly_linked_list_alloc();
singly_linked_list_iterator_t* iterator;
for (i = 1; i < 6; ++i)
{
singly_linked_list_push_back(list, i);
}
for (i = 0; i >= -4; --i)
{
singly_linked_list_push_front(list, i);
}
iterator = singly_linked_list_get_iterator(list);
while (singly_linked_list_iterator_has_next(iterator))
{
printf("%d ", singly_linked_list_iterator_next(iterator));
}
puts("");
singly_linked_list_pop_front(list);
singly_linked_list_pop_front(list);
singly_linked_list_pop_back(list);
singly_linked_list_pop_back(list);
iterator = singly_linked_list_get_iterator(list);
while (singly_linked_list_iterator_has_next(iterator))
{
printf("%d ", singly_linked_list_iterator_next(iterator));
}
puts("");
while (singly_linked_list_size(list))
{
singly_linked_list_pop_back(list);
}
singly_linked_list_free(list);
}
#include "singly_linked_list.h"
#include <stdlib.h>
singly_linked_list_t* singly_linked_list_alloc()
{
return calloc(1, sizeof(singly_linked_list_t));
}
int singly_linked_list_init(singly_linked_list_t* list)
{
if (!list)
{
return 0;
}
list->head = NULL;
list->tail = NULL;
list->size = 0;
return 1;
}
void singly_linked_list_free(singly_linked_list_t* list)
{
if (list)
{
singly_linked_list_clear(list);
free(list);
}
}
void singly_linked_list_clear(singly_linked_list_t* list)
{
singly_linked_list_node_t* current_node;
singly_linked_list_node_t* next_node;
if (!list)
{
return;
}
current_node = list->head;
while (current_node)
{
next_node = current_node->next;
free(current_node);
current_node = next_node;
}
list->head = NULL;
list->tail = NULL;
list->size = 0;
}
int singly_linked_list_push_front(singly_linked_list_t* list, int datum)
{
singly_linked_list_node_t* new_node;
if (!list)
{
return 0;
}
new_node = malloc(sizeof *new_node);
if (!new_node)
{
return 0;
}
new_node->datum = datum;
if (list->size == 0)
{
list->head = new_node;
list->tail = new_node;
}
else
{
new_node->next = list->head;
list->head = new_node;
}
list->size++;
return 1;
}
int singly_linked_list_push_back(singly_linked_list_t* list, int datum)
{
singly_linked_list_node_t* new_node;
if (!list)
{
return 0;
}
new_node = malloc(sizeof *new_node);
if (!new_node)
{
return 0;
}
new_node->datum = datum;
if (list->size == 0)
{
list->head = new_node;
list->tail = new_node;
}
else
{
list->tail->next = new_node;
list->tail = new_node;
}
list->size++;
return 1;
}
int singly_linked_list_pop_front(singly_linked_list_t* list)
{
int result;
singly_linked_list_node_t* node;
if (!list)
{
abort();
}
if (list->size == 0)
{
abort();
}
result = list->head->datum;
node = list->head;
list->head = list->head->next;
list->size--;
if (!list->head)
{
list->tail = NULL;
}
free(node);
return result;
}
int singly_linked_list_pop_back(singly_linked_list_t* list)
{
int result;
singly_linked_list_node_t* current_node;
singly_linked_list_node_t* previous_node;
if (!list)
{
abort();
}
if (list->size == 0)
{
abort();
}
current_node = list->head;
previous_node = NULL;
while (current_node->next)
{
previous_node = current_node;
current_node = current_node->next;
}
result = current_node->datum;
if (!previous_node)
{
list->head = NULL;
list->tail = NULL;
}
else
{
previous_node->next = NULL;
list->tail = previous_node;
}
list->size--;
free(current_node);
return result;
}
size_t singly_linked_list_size(singly_linked_list_t* list)
{
if (!list)
{
abort();
}
return list->size;
}
singly_linked_list_iterator_t*
singly_linked_list_get_iterator(singly_linked_list_t* list)
{
singly_linked_list_iterator_t* iterator;
if (!list)
{
return NULL;
}
iterator = malloc(sizeof *iterator);
if (!iterator)
{
return NULL;
}
iterator->next_node = list->head;
return iterator;
}
int
singly_linked_list_iterator_has_next(singly_linked_list_iterator_t* iterator)
{
if (!iterator)
{
abort();
}
return iterator->next_node != NULL;
}
int singly_linked_list_iterator_next(singly_linked_list_iterator_t* iterator)
{
int result;
if (!iterator)
{
abort();
}
if (!singly_linked_list_iterator_has_next(iterator))
{
abort();
}
result = iterator->next_node->datum;
iterator->next_node = iterator->next_node->next;
return result;
}
#ifndef SINGLY_LINKED_LIST_H
#define SINGLY_LINKED_LIST_H
#include <stdlib.h>
typedef struct singly_linked_list_node_t {
int datum;
struct singly_linked_list_node_t* next;
} singly_linked_list_node_t;
typedef struct singly_linked_list_t {
singly_linked_list_node_t* head;
singly_linked_list_node_t* tail;
size_t size;
} singly_linked_list_t;
typedef struct singly_linked_list_iterator_t {
singly_linked_list_node_t* next_node;
} singly_linked_list_iterator_t;
/******************************************
* Allocates and returns a new empty list. *
******************************************/
singly_linked_list_t* singly_linked_list_alloc();
/**********************
* Initializes a list. *
**********************/
int singly_linked_list_init(singly_linked_list_t* list);
/*************************
* Frees the entire list. *
*************************/
void singly_linked_list_free(singly_linked_list_t* list);
/***************************
* Clears the list content. *
***************************/
void singly_linked_list_clear(singly_linked_list_t* list);
/**********************************************
* Pushes a new datum to the head of the list. *
**********************************************/
int singly_linked_list_push_front(singly_linked_list_t* list, int datum);
/**********************************************
* Pushes a new datum to the tail of the list. *
**********************************************/
int singly_linked_list_push_back(singly_linked_list_t* list, int datum);
/*****************************
* Pops the head of the list. *
*****************************/
int singly_linked_list_pop_front(singly_linked_list_t* list);
/*****************************
* Pops the tail of the list. *
*****************************/
int singly_linked_list_pop_back(singly_linked_list_t* list);
/**********************************************
* Returns the number of elements in the list. *
**********************************************/
size_t singly_linked_list_size(singly_linked_list_t* list);
/**************************************
* Returns the iterator over the list. *
**************************************/
singly_linked_list_iterator_t*
singly_linked_list_get_iterator(singly_linked_list_t* list);
/******************************************************************
* Returns non-zero value if the iterator has something to remove. *
******************************************************************/
int
singly_linked_list_iterator_has_next(singly_linked_list_iterator_t* iterator);
/**************************
* Returns the next datum. *
**************************/
int singly_linked_list_iterator_next(singly_linked_list_iterator_t* iterator);
#endif /* SINGLY_LINKED_LIST_H */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment