Honors assignment W3

/*
  Honors Assignment W3
  
  This program creates a doubly linked list with 200 random values between [0,49].
  Then it tests two methods to remove duplicates:
  1) It first sorts the list on value, and then iterates over the list removing 
     elements that have the same value as the previous one in the list.
  2) It takes the first element and searches the remainder of the list for elements 
     with the same value and removes them. Then it repreats this process with the 
     second, third, ... elements until only one element is left.
  The main function prints the lists and the results to the standard output.
  
  Code by: GB
  Last update: 2022-05-26  
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define MAXVAL 49
#define LISTLEN 200

// an element of a list has a value and pointers to the previous and next element
typedef struct list {
    int value;
    struct list* next;
    struct list* prev;
} list;


list* randlist(int maxvalue, int len) {
    /*
      Creates a list of elements with random values, and returns
      a pointer to its head.
      The maxvalue and len arguments can be used to set the max of 
      the random numbers and the length of the list.
    */
    int val,i; 
    list* head = NULL;
    list* last = NULL;
    list* newitem;
    
    for (i=0; i<len; i++) {
    	newitem = malloc(sizeof(list));
    	if (i==0) head = newitem;
    	newitem->value = 1 + rand() % maxvalue;
    	newitem->prev = last;
    	newitem->next = NULL;
    	if (last != NULL) {
    	    last->next = newitem;
    	}
    	last = newitem;
    }
    return head;
}

void bubblesort_list(list* l) {
    /* 
      Sorts a doubly linked list using the bubble sort algorithm.
      
      List items remain in place in memory, just the content of their 
      value address changes. 
    */
    int swapped = 1;
    int tempval;
    list* c;
    
    while (swapped == 1) { // go over list until in last pass there was no swap 
        swapped = 0;
        c = l; // set current item to start of list
        while (c->next != NULL) { // not at the end of list
            if (c->value > (c->next)->value) { // current smaller than next
                tempval = c->value;
                c->value = (c->next)->value;
                (c->next)->value = tempval;
                swapped = 1;
            }
        c = c->next; // move on to next item
        }
    }
}


void remove_duplicates_sorted_list(list* l) {
    /*
      Remove duplicates from a doubly linked list that is sorted on value.
    */

    list* temp;
    while (l->next != NULL) {
        if (l->value == (l->next)->value) {
            // remove next item and do not move on
            temp = l->next;
            l->next = (l->next)->next; 
            if (l->next != NULL) {
            	(l->next)->prev = l;
            }
            free(temp); // free memory of removed item
        } else {
            // move on to next item
            l = l->next; 
        }
    }
}


void remove_duplicates_nonsorted_list(list* l) {
    /*
      Remove duplicates from a doubly linked list that is not sorted on value
      without sorting it.
    */

    list* temp;
    list* c = l;
    int targetval = c->value;
    while (c->next != NULL) {
        if ((c->next)->value == targetval) {
            // remove next item and do not move on
            temp = c->next;
            c->next = (c->next)->next; 
            if (c->next != NULL) {
            	(c->next)->prev = c;
            }
            free(temp); // free memory of removed item
        } else {
            // move on to next item
            c = c->next; 
        }
    }
    if (l->next != NULL) {
        remove_duplicates_nonsorted_list(l->next); 
    }
}



void print_list(list* l) {
    /*
      prints list
    */
    while (l->next != NULL) {
        printf("%02d, ", l->value);
        l = l->next;
    }
    printf("%02d, ", l->value);
    printf("\n");
}


int main(void) {

    /*
    Performs the actions needed to fullfill the honors assignment W3 and 
    prints results to screen for verification.
    */   

    list* head = NULL;
    srand(time(0));
    
    printf("random 200 elements between [0,49]:\n");
    head = randlist(MAXVAL, LISTLEN);
    print_list(head);
    printf("\nsorted with bubble sort:\n");
    bubblesort_list(head);
    print_list(head);
    printf("\nduplicates removed from sorted list (method 1):\n");
    remove_duplicates_sorted_list(head);
    print_list(head);
    printf("\nnew random 200 elements between [0,49]:\n");
    head = randlist(MAXVAL, LISTLEN);
    print_list(head);
    printf("\nduplicates removed using method 2:\n");
    remove_duplicates_nonsorted_list(head);
    print_list(head);
    printf("\nsorted non-duplicate list (to help verififying results 2):\n");
    bubblesort_list(head);
    print_list(head);
    
    return 0;
}