Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======Project: Doubly Linked List Library Implementation======

A project for Matt Haas' Fall 2011 Data Structures class.

This project was done over the month of October, but was worked on for about a week in terms of days in which programming this implementation.

=====Objectives=====
The purpose of this lab is to create linked list manipulating functions, make a library from these functions, then write a program that implements this library.
=====Prerequisites=====
In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

  * understand functions
  * understand pointers
  * understand structs
  * understand malloc()
  * ability to create a linked data structure

=====Background=====
As previously stated, I am trying to make a linked list library implementation. In doing so, I will have gained an understanding of a linked list, which is our basis for learning about data structures. This lets one create a list of data that can be accessed by moving back and forth.

=====Scope=====
To better utilize the functionality of the doubly linked list we've been studying in class, a personal implementation for use as a library will be undertaken for use in other projects and activities this semester.

Working from the class example, a library implementation will be created which has the following functions:

  * **create**: generate a new node
  * **append**: add a new node to the list after a given node
  * **remove**: remove a node from the list
  * **search**: find if a node exists (likely search by value)
  * **insert**: add a new node to the list before a given node
  * **copy**: duplicate an existing node
  * **copy list**: duplicate the current list of nodes
  * **display**: display current list

Creating a header file will be in order, which will contain the function prototypes of all of the above. The code will be implemented across several files .

There will also be a sample implementation (ie a file with a **main()**) that will include the header file and demonstrate this library being created (it will link against it to compile).

=====Attributes=====

  * pointers: pointers are at the heart of dynamic structures.
  * malloc/new: dynamic memory allocation.
  * linked lists: this code is going to implement linked lists.
  * doubly linked lists: not only is the code implementing a linked list, it is implementing doubly linked lists.
  * libraries: this code will be part of a library that can be reused in other projects
  * file I/O: The manager in the main function uses the library to take input and give output.
 
=====Code=====
===main.c===
<code c>
/*
 * Doubly Linked List Library - a doubly linked list implementation
 *
 * Fall2011 Data Structures
 */

// Include files
#include <stdio.h>
#include <stdlib.h>
#include "dlllib.h"

unsigned int makeChoice();

// main function
int main()
{
	// initialize variables
	start = end = tmp = tmp2 = NULL;
	unsigned int choice, created=0;
	system("clear");
	printf("Welcome to Linked List Manager!\n\n");
	while(created == 0)
	{
		create();
		if(start != NULL)
		{
			created=1;
		}
		else
		{
			printf("Please create a list.\n");
		}
	}
	system("clear");
	choice=makeChoice();
	system("clear");
	while(choice != 0)
	{
		system("clear");
		if(choice==1)
		{
			displayList();
		}
		
		else if(choice==2)
		{
			append();
		}
		else if(choice==3)
		{
			insert();
		}

		else if(choice==4)
		{
			removeNode();
		}

		else if(choice==5)
		{
			copy();
		}
		else if(choice==6)
		{
			copyList();
		}
		if (start == NULL)
		{
			choice=0;
		}
		else
		{
			printf("\n\n");
			choice=makeChoice();
		}
		system("clear");
	}
	return(0);
}	

unsigned int makeChoice()
{
	unsigned int choice=-1;
	while ((choice < 0)  || (choice > 6))
	{
		printf(" =============================================================");
		printf("\n|| Choose a function to execute (0 to quit):                 ||\n");
		printf(" =============================================================\n");
		printf("|| (1: Display list) || (2: Append node) || (3: Insert node) ||\n");
		printf("|| (4: Remove node)  || (5: Copy node)   || (6: Copy list)   ||\n"); 
		printf(" =============================================================\n\nInput: ");
		scanf("%d", &choice);
		if ((choice < 0) || (choice > 6))
		{
			printf("\n!!ERROR!! Please enter a valid value.\n");
		}
	}
	return(choice);
}
</code>

===dlllib.h===

<code c>
/*
 * Doubly Linked List Library - a doubly linked list implementation
 *
 * Fall2011 Data Structures
 */

#ifndef _DLLLIB_H
#define _DLLLIB_H

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

// Create our node structure
struct node {
	int value;
	struct node *next;
	struct node *prev;
};
typedef struct node Node;

int create();
int append();
int removeNode();
int search();
int insert();
int deleteList();
int copyList();
int copy();
int displayList();

int input, input2;
Node *start, *end, *tmp, *tmp2;

#endif
</code>

===create.c===
<code c>
#include<stdio.h>
#include<stdlib.h>
#include "dlllib.h"

int create()
{	
	// initialize variables
	start = end = tmp = tmp2 = NULL;

	printf("Enter a value (-1 to quit): ");
	scanf("%d", &input);

	// build our list
	while (input != -1)
	{
		if (start == NULL) // we have an empty list
		{
			start = (Node *) malloc (sizeof(Node));
			end = start; // only one node, start and end are same
			start -> next = NULL; // nothing after
			start -> prev = NULL; // nothing before
			tmp = start; // tmp points to beginning of list
			start -> value = input; // enter value into node
		}
		else // there is something in our list
		{
			tmp = (Node *) malloc (sizeof(Node));
			end -> next = tmp; // tack new node onto end of list
			tmp -> prev = end; // new node points to current end
			end = end -> next; // advance end to new end
			end -> value = input; // put input in node
			end -> next = NULL; // nothing beyond end
		}

		printf("Enter a value (-1 to quit): ");
		scanf("%d", &input);
	}
	return(0);
}
</code>

===append.c===
<code c>
#include<stdio.h>
#include<stdlib.h>
#include "dlllib.h"
	
int append()
{
	//Append 

	tmp=start;
	int i=0;
	while(tmp != NULL)
	{
		i++;
		tmp=tmp->next;
	}
	printf("Enter a value for the appended node: ");
	scanf("%d", &input);
	tmp = (Node *) malloc (sizeof(Node));
	end -> next = tmp; // tack new node onto end of list
	tmp -> prev = end; // new node points to current end
	end = end -> next; // advance end to new end
	end -> value = input; // put input in node
	end -> next = NULL; // nothing beyond end
	return(0);
}
</code>

===insert.c===
<code c>
#include <stdio.h>
#include <stdlib.h>
#include "dlllib.h"

int insert()
{
	// Insert a new node
	int i=0;
	printf("Enter node position to insert before: ");
	scanf("%d", &input);

	tmp = start;
	for(i=0; i<input; i++) //position tmp at node to insert before
	{
		tmp = tmp -> next;
	}

	printf("Enter a value for new node: ");
	scanf("%d", &input2);

	if (start == NULL) // if our list is empty
	{
		start = (Node *) malloc (sizeof(Node));
		end = tmp = start;
		start -> prev = NULL;
		end -> prev = NULL;
		start -> value = input2;
	}
	else if (start == tmp) // we're inserting before start of list
	{
		tmp2 = (Node *) malloc (sizeof(Node));
		tmp2 -> next = start; // point new node's next at start
		start -> prev = tmp2; // point start's prev at tmp2
		start = start -> prev; // move start to new node
		start -> value = input2; // put value in node
	}
	else // we're inserting before a node in the list
	{
		tmp2 = (Node *) malloc (sizeof(Node));
		tmp2 -> next = tmp; // point new node's next at tmp
		tmp2 -> prev = tmp -> prev; // point new node's prev at tmp's prev
		tmp -> prev -> next = tmp2; // tmp's previous next is new node
		tmp -> prev = tmp2; // tmp's prev is new node
		tmp2 -> value = input2; // put value in node
	}
	return(0);
}
</code>

===copy.c===
<code c>
#include <stdio.h>
#include <stdlib.h>
#include "dlllib.h"

int copy()
{
	//Copy
	int i;	
	printf("Enter node # to copy: ");
	scanf("%d", &input);

	// Move tmp to exact node we wish to copy
	tmp=start;
	for(i=0; i<input; i++)
	{
		tmp = tmp -> next;
	}	
	tmp2 = (Node *) malloc (sizeof(Node));
	end -> next = tmp2; // tack new node onto end of list
	tmp2 -> prev = end; // new node points to current end
	end = end -> next; // advance end to new end
	end -> value = tmp-> value; // put value of copied node in node
	end -> next = NULL; // nothing beyond end
	return(0);
}
</code>
===search.c===
<code c>
#include <stdio.h>
#include <stdlib.h>
#include "dlllib.h"

int search()
{
	//Find if node exists (search by value)
	printf("Enter a value to search for: ");
	scanf("%d", &input);
	tmp=start;
	int i = 0;
	int found=0; //if found = 0, then no node matches the search.

	while (tmp != NULL)
	{
		if(tmp->value == input)
		{
			printf("Node at position [%d] matches the search value.\n", i);
			printf("Node [%d]: %d\nSearch value: %d\n\n", i, tmp->value, input);
			found=1;
		}
		i++;
		tmp = tmp -> next;
	}
	if (found == 0)
	{
		printf("No node matches the search value.\n");
	}
	return(0);
}
</code>
===copyList.c===
<code c>
#include <stdio.h>
#include <stdlib.h>
#include "dlllib.h"

int copyList()
{
	//Copy entire list.
	tmp=start;
	int i=0;
	int copyFor;
	while (tmp != NULL)
	{
		i++;
		tmp = tmp->next;
	}
	tmp=start;
	for(copyFor=0;copyFor<i;copyFor++)
	{
	tmp2 = (Node *) malloc (sizeof(Node));
	end -> next = tmp2; // tack new node onto end of list
	tmp2 -> prev = end; // new node points to current end
	end = end -> next; // advance end to new end
	end -> value = tmp-> value; // put value of copied node in node
	end->next=NULL;
	tmp=tmp->next;
	}
	return(0);
}	
</code>

===displayList.c===
<code c>
#include <stdio.h>
#include <stdlib.h>
#include "dlllib.h"

int displayList()
{
	// Display our linked list
	int i = 0;
	tmp = start;

	while (tmp != NULL)
	{
		printf("[%d] value: %d\n", i, tmp -> value);
		i++;
		tmp = tmp -> next;
	}
	return(0);
}
</code>
===removeNode.c===
<code c>
#include <stdio.h>
#include <stdlib.h>
#include "dlllib.h"

int removeNode()
{
	// Remove a node from the list
	tmp = start;
	int i=0;
	printf("Enter node # to delete: ");
	scanf("%d", &input);

	// Move tmp to exact node we wish to delete
	for(i=0; i<input; i++)
	{
		tmp = tmp -> next;
	}

	if ((tmp != start) && (tmp != end))
	{
		tmp -> next -> prev = tmp -> prev;
		// The node after points to the node before tmp
		tmp -> prev -> next = tmp -> next;
		// Now, the now before points to the node after tmp
		tmp -> prev = NULL;
		tmp -> next = NULL;
		// tmp is now disconnected from the list
		free (tmp); // deallocate the node tmp is pointing to
	}
	else if (start == end) // list is only a single node
	{
		free(start);
		start=end=tmp=NULL;
	}
	else if (tmp == start)
	{
		tmp -> next -> prev = NULL;
		// The node following tmp is no longer pointing to us
		start = start -> next;
		// Adjust start to point to the new start of the list
		tmp -> next = NULL; // Disconnect tmp from the list
		free(tmp); // deallocate the node tmp is pointing to
	}
	else // tmp is equal to end
	{
		tmp -> prev -> next = NULL;
		// The node preceding tmp is no longer pointing to us
		end = end -> prev;
		// Adjust end to point to the new end of the list
		tmp -> prev = NULL; // Disconnect tmp from the list
		free(tmp); // deallocate the node tmp is pointing to
	}
	return(0);
}
</code>

=====Execution=====
This is how to compile and execute:
<cli>
lab46:~/src/data/dlllib$ ar rcs libdll.a *.o
lab46:~/src/data/dlllib$ gcc -o testimple main.c -L. -ldll
lab46:~/src/data/dlllib$ ./testimple
</cli>

=====Reflection=====
I had some problems with my node removing function. Rather than having a function that removes a list, I settled for a single node deleting function that can be run until the list is gone. Overall, this is a very important project, because it lays the foundation for the rest of the class, really. It is a big hurdle to get over, but once you do, there is a lot to be learned from going back and using this project.
=====References=====
In performing this project, the following resources were referenced:

  * Matt Haas
  * Fellow classmates (simple discussion about the aspects of our personal implementations)
  * C Programming Language O'Reilly Pocket Reference
Lab46 Wiki

User Tools

Site Tools

Page Tools
