Skip to content

Instantly share code, notes, and snippets.

@lukem512
Created April 13, 2015 09:45
Show Gist options
  • Save lukem512/1b009ff0b06877662d4d to your computer and use it in GitHub Desktop.
Save lukem512/1b009ff0b06877662d4d to your computer and use it in GitHub Desktop.
Linked List ADS
// Luke Mitchell
// Linked List
// 22-11-2011
// edited 12/12/2011 for CW1 [100%]
// edited 27/12/2011 for CW2
#ifndef LIST_H
#define LIST_H
/* Includes */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/* Types */
typedef struct node {
char *data;
int count;
struct node* next;
} node;
typedef struct list {
int size;
node* start;
node* end;
node* current;
} list;
/* Function prototypes */
node* list_search (list*, char*);
int list_get_comparisons (list*, char*);
int list_is_empty (list*);
void list_reset (list*);
int list_add_node (list*, char*, int);
int list_add_node_rear (list*, char*, int);
int list_remove_node (list*, node*);
int list_advance (list*);
int list_retreat (list*);
list* list_create (void);
void list_destroy (list*);
#endif
// Luke Mitchell lm0466
// Principles of programming CW2
// Hash table/Linked list assignment
// Definition for linked list ADS
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
// returns the element of the list, l, containing the data specified
// returns NULL if not found
node* list_search (list* l, char* data)
{
// begin at the start of the list
list_reset (l);
// empty list? return not found
if (l->current == NULL)
return NULL;
// iterate through each list item, comparing strings
do
{
if (strcmp (l->current->data, data) == 0)
return l->current; // found, return the node
} while (list_advance (l) != -1);
// return 'not found'
return NULL;
}
// returns the number of comparisons taken to find the node with data specified
// this essentially performs a search whilst keeping count of the comparisons
int list_get_comparisons (list* l, char* data)
{
int cmp = 0;
// reset list to begin count at start
list_reset (l);
// empty list? return 0 comparisons
if (l->current == NULL)
return cmp;
// iterate through each list item, comparing strings
do
{
// increment counter
cmp++;
if (strcmp (l->current->data, data) == 0)
break;
} while (list_advance (l) != -1);
// return comparisons
return cmp;
}
// returns 1 if the specified list is empty
// returns 0 if list isn't empty
int list_is_empty (list* l)
{
return (l->start == NULL) ? 1 : 0;
}
// moves the current pointer to the start of the specified list
void list_reset (list* l)
{
l->current = l->start;
}
// inserts an element at the front of the list
// the new element will contain the specified data, data (the string)
// and c (count, or the number of occurences of the string)
// returns -1 on failure
// returns 0 on success
int list_add_node (list* l, char* data, int c)
{
node* n = calloc (1, sizeof(node));
if (n == NULL)
return -1;
// copy the data
n->data = malloc (strlen(data)+1);
strncpy (n->data, data, strlen(data)+1);
n->count = c;
// empty list?
if (list_is_empty (l))
{
// set the current and end pointers
// to the new (and only) node
l->current = n;
l->end = n;
}
else
{
// no, merely set the next pointer
// as the node was inserted at the front
// of the list
n->next = l->start;
}
// set the start pointer to the new node
l->start = n;
// and increment the list size counter
l->size++;
// return success
return 0;
}
// inserts an element at the rear of the list
// the new element will contain the specified data, data (the string)
// and c (count, or the number of occurences of the string)
// see list_add_node for details of workings
// returns -1 on failure
// returns 0 on success
int list_add_node_rear (list* l, char* data, int c)
{
node* n = calloc (1, sizeof(node));
if (n == NULL)
return -1;
// copy the data
n->data = malloc (strlen(data)+1);
strncpy (n->data, data, strlen(data)+1);
n->count = c;
// empty list?
if (list_is_empty (l))
{
l->start = n;
l->current = n;
}
else
{
l->end->next = n;
}
l->end = n;
l->size++;
return 0;
}
// removes a specified node, n, from the specified list, l.
// returns -1 if n isn't found in l
// returns 0 if removal is successful
int list_remove_node (list* l, node* n)
{
node *k, *j;
k = l->start;
j = n->next;
// search list for preceeding node, k, to n
while (k->next != n && k != l->end)
k = k->next;
// check we found the right node
if (k->next != n)
return -1;
// update next pointer from k
k->next = j;
// check for special circumstances
if (l->start == n)
l->start = k;
if (l->current == n)
l->current = k;
if (l->end == n)
l->end = k;
// free memory from n
free (n->data);
free (n);
l->size--;
return 0;
}
// advances the current pointer to the next item in the list
// if the current pointer points to the end of the list returns -1
// returns 0 on successful advance
int list_advance (list* l)
{
if (l->current == l->end)
return -1;
l->current = l->current->next;
return 0;
}
// retreats the current pointer to the previous item in the list
// returns -1 if the current pointer is the start
// returns 0 on successful retreat
int list_retreat (list* l)
{
if (l->current == l->start)
return -1;
node* n = l->start;
// find the preceeding list item
while (n->next != l->current && n != l->end)
n = n->next;
// ensure we found it
if (n->next != l->current)
return -1;
l->current = n;
return 0;
}
// creates an empty list
// allocate memory and initialises struct fields
// returns a pointer to the list, or NULL if there's
// insufficient memory
list* list_create (void)
{
// allocate memory for list
list* l = malloc (sizeof(list));
// if malloc failed, return null (value of l)
if (l)
{
l->size = 0;
l->start = NULL;
l->end = NULL;
l->current = NULL;
}
return l;
}
// destroys the specified list and frees all memory it occupied
void list_destroy (list* l)
{
// free each item in the list
list_reset (l);
// remove (and free) each node individually
do {
list_remove_node (l, l->current);
} while (list_advance(l) != -1);
// free the list structure itself
free (l);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment