Remove duplicates from doubly-linked list

Given a list of 200 random integers ranging from 0-49, this program sorts the list in numerical order and removes all the duplicate numbers.
mail@pastecode.io avatar
unknown
plain_text
2 years ago
5.1 kB
4
Indexable
Never
//Week 3 Honors Assignment
//Modify the singly linked list to be a doubly linked list. Now write a routine that removes all duplicate data in the doubly linked list.
//The data will be integers generated at random from [0,49]. Initially have a list of 200 elements.
//Now do this in one of two ways.
//1. Sort the list by its data field. Remove adjacent elements of the sorted list with the same value.
//2. Or, take the first element—search the remainder of the list for elements with the same data and remove them. Then take the second element and do the same. Repeat until only one element is left.

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

typedef struct list{
	int data; //can replace this with a more complex data structure
	struct list *next; //pointer to next element
	struct list *prev; //pointer to previous element
}list;

//function to create the list
list* create_list(int d){
	list* head = malloc(sizeof(list)); //use malloc to allocate space for the list
	head->data = d; //set the data parameter
	head->next = head->prev = NULL; //set the previous and next elements to NULL
	return head; //return the head
}

//add an element to the list by adding an element to the front (prepending
list *add_to_front(int d, list* head){
	list* newNode = create_list(d); //create a list
	newNode->data = d; //add the data
	newNode->next = head; //Make the next node after newNode the head
	newNode->prev = NULL; //make the previous node null
	if(head!=NULL){
		head->prev = newNode; //set the previous node from the head to the new node we created
	}
	head = newNode; //mode the head to point to the new node
	return head;
}

//convert an array to a list
list* array_to_list(int d[], int size){
	list* head = create_list(d[0]); //create lsit using first element of the array
	for(int i=1; i<size; i++){
		head = add_to_front(d[i], head); //add array elements to the front of the lsit we made
	}
	return head;
}

int is_empty(const list *l){
	return l == NULL; //the tail is null. if this is what the lsit equals, we know its empty
}

void print_list(list *h, char *title){
	printf("%s\n", title); //give the list a title for identification purposes
	int index = 0;
	while(h!=NULL){ //while we are not at the end of the list
		printf("%d\t", h->data); //print the element
		h = h->next; //go to the next element
		index++; //increment index
		if(index%5==0){
			printf("\n");;
		}
	}
	printf("\n");
}

int getItem(list *head, int index){
	list* current = head;
	//index of the node we're looking at
	int count = 0;
	while(current!=NULL){
		if(count == index){
			return current->data;
		}
		count++;
		current = current->next;
	}
	assert(0);
}

void setItem(list *head, int index, int data){
        list* current = head;
        //index of the node we're looking at
        int count = 0;
        while(current!=NULL){
                if(count == index){
                        current->data = data;
			return;
                }
                count++;
                current = current->next;
        }
        assert(0);
}

void swap(list* data, int a, int b){
	//swap the nodes at index a and b
	int temp = getItem(data, a);
	setItem(data, a, getItem(data, b));
	setItem(data, b, temp);
}


void bubbleSort(list* data, int amt){
	for(int i=0; i<amt; i++){
		for(int j = amt-1; j>i; j--){
			if(getItem(data, j-1)>getItem(data, j)){
				swap(data, j-1, j);
			}
		}
	}
}

void removeDuplicates(list* head){
	list* current = head; //pointer to traverse the linked list
	list* nextPointer; //pointer to store the next pointer of the node to be deleted
	if(is_empty(current)){
		return; //do nothing if the lsit is empty
	}
	//traverse the list until the last node is reached
	while(current->next!=NULL){
		//if the current node and the node after the current node have the same value:
		if(current->data == current->next->data){
			nextPointer = current->next->next; //set the next pointer to be the node after the node after the current node
			free(current->next); //free the node after the current node
			current->next = nextPointer; //set the node after the current node to the node after the node after the current node. The node was successfuly deleted.
		}else{
			//if the current node and the node after the current node aren't the same value, advance to the next node without deletion
			current = current->next;
		}
	}
}

#define SIZE 200 //we will generate 200 random integers from 0 to 49 inclusive

int main(){
	//Use srand to set the seed. we will use the current time, as that produces a unique number every time the program is run
	srand(time(0));
	int numbers[SIZE];
	//fill the array of numbers with random numbers
	for(int i=0; i<SIZE; i++){
		numbers[i] = rand()%50; //add random number to the array. using %50 makes the numbers from 0 to 49
	}
	//convert array to a list
	list* myList = array_to_list(numbers, SIZE);
	//sort the list using bubble sort
	bubbleSort(myList, SIZE);
	//remove the duplicates
	removeDuplicates(myList);
	//print the list
	print_list(myList, "myList");
	return 0;
}