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 C/C++, Data Structures, and System Programming  by Karl Krauss during the SEMESTER YEAR.

This project is one I spent over a week on, and probably the one I learned the most from.  

=====Objectives=====
The purpose of this project was to create a library for doubly linked lists.

=====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=====
  *This project was probably the most important project we worked on this semester.  It is a library that allows linked list functionality, its tested and works.  This made the stack and Q ones quite simple.
=====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
  * **delete**: destroy/de-allocate an existing list
  * **copy**: duplicate an existing 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 (create.c, add.c, delete.c, process.c, or however you wish to structure it-- have at least 4 .c or .cc source 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=====


====Cprog attributes====

  * variables
  * pointers 
  * selection 
  * i/o 
  * repetition 
  * functions 
  * structures 
  * libraries


====Data Structures====
  * Pointers
  * Malloc/new
  * linked list
  * Doubly linked list
  * Libraries

====Systems programming====
  * Terminal I/O


  











* 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

=====Code=====
This is the header file: 
<code c>
#ifndef		DOUBLY_H
#define      	DOUBLY_H


struct node { //predefined structure with one variable (next and prev are how they are doubly linked)
	int value;
	struct node *next;
	struct node *prev;
};
typedef struct node Node;

struct list {// predefined structure for use of returns in functions allow for easy access to list
	Node *start;
	Node *end;
};
typedef struct list List;

List *newNode(List *myList, Node *tmp, int input);
List *insertNode(List *myList, Node *tmp, Node *tmp2, int input);
List *deleteNode(List *myList, Node *tmp, int input);
Node *removeNode(List *myList, Node *tmp, int input);
void printList(List *myList, Node *tmp);
int searchNode(List *myList, int input);

//minimum variables needed in main: int input, Node *tmp, Node *tmp2, List *myList.

#endif

</code>

This is the library code:
<code c>
// This is an attempt at writing linked doubly list libraries for a single variable that will include newNode(), insertNode(), deleteNode(), 
// removeNode, printList()

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

List *newNode(List *myList, Node *tmp, int input)//This is for creating the first node of a list and appending
{

	if(myList->start == NULL) // this is to test if the list is empty
	{
		myList->start = (Node *)malloc(sizeof(Node));
		myList->end = myList->start; // with only one node end and start are the same
		myList->start->next = NULL; //no nodes after start(no next)
		myList->start->prev = NULL; //no nodes before start(no before)
		myList->start->value = input; //value is now stored in first node


	}
	else // list is not empty so now will will create a new node and append
	{
		tmp = (Node *)malloc(sizeof(Node));
		myList->end->next = tmp; // end's next now points to tmp instead of null, so adding a new node to end of list
		tmp->prev = myList->end; //new nodes prev now points to current end
		myList->end = myList->end->next; // moves end to the true end of the list.
		myList->end->value = input; // store input into new node(end)
		myList->end->next = NULL;// nothing beyond the end of the list
	}
	
	return myList;
}

List *insertNode(List *myList, Node *tmp, Node *tmp2, int input)  //the main function will need certain code for this to work
{
	if(myList->start == tmp) // This is for inserting before the list(AKA prepending)
	{
		tmp2 = (Node *)malloc(sizeof(Node));
		tmp2->next = myList->start; //point the prepended node's next to start
		myList->start->prev = tmp2; // point current starts prev to prepended tmp2
		myList->start = myList->start->prev; // move start to prepended node
		myList->start->value = input; // new starts value is stored in node
	}
	else //inserting before a node in the list but not prepending or appending
	{
		tmp2 = (Node *)malloc(sizeof(Node));
		tmp2->next = tmp; //point new node's next at temp
		tmp2->prev = tmp->prev; // point new nodes prev at temp's prev
		tmp->prev->next = tmp2; // tmp's previous's next is now the new node
		tmp->prev = tmp2; //tmp's prev is now new node
		tmp2->value = input; //store input into inserted node
	}
	
	return myList;
}

List *deleteNode(List *myList, Node *tmp, int input)
{
	if((tmp != myList->start) && (tmp != myList->end)) //is the node to be deleted any node other than the first or last node
	{
		tmp->next->prev = tmp->prev; //the node after the one to be deleted points to the node before the one to be deleted
		tmp->prev->next = tmp->next; // the node before the one to be deleted now points to the one after the deleted node
		tmp->prev = NULL; 
		tmp->next = NULL; //tmp is now disconnected from the list
		free(tmp); //deallocating the memory used for the node tmp points to
	}
	else if(myList->start == myList->end) //meaning there is only one node
	{
		free(tmp); // no need for any crazyness here, simply free the memory and the node is gone
	}
	else if(tmp == myList->start)// is the node to be deleted the first node in a list of more than one nodes
	{
		tmp->next->prev = NULL;//the node following temp points to NULL instead of start
		myList->start = myList->start->next; //start now becomes starts next(AKA the next NOde)
		tmp->next=NULL;//the old start is now completely disconnected, it does not point to another node and no nodes point to it
		free(tmp);// lets get our memory back
	}
	else //only thing left to check is if the node to be deleted is the last node aka tmp == end
	{
		tmp->prev->next = NULL; //the node before the deleted node no longer points to it
		myList->end = myList->end->prev;// now end points to the old ends previous
		tmp->prev = NULL; //Now tmp which was the END is now disconnected
		free(tmp);// gimme back my memory!
	}
	
	return myList;
}

Node *removeNode(List *myList, Node *tmp, int input)
{
	if((tmp != myList->start) && (tmp != myList->end)) //is the node to be deleted any node other than the first or last node
	{
		tmp->next->prev = tmp->prev; //the node after the one to be deleted points to the node before the one to be deleted
		tmp->prev->next = tmp->next; // the node before the one to be deleted now points to the one after the deleted node
		tmp->prev = NULL; 
		tmp->next = NULL; //tmp is now disconnected from the list
		
	}
	
	else if(tmp == myList->start)// is the node to be deleted the first node in a list of more than one nodes
	{
		tmp->next->prev = NULL;//the node following temp points to NULL instead of start
		myList->start = myList->start->next; //start now becomes starts next(AKA the next NOde)
		tmp->next=NULL;//the old start is now completely disconnected, it does not point to another node and no nodes point to it
		
	}
	else //only thing left to check is if the node to be deleted is the last node aka tmp == end
	{
		tmp->prev->next = NULL; //the node before the deleted node no longer points to it
		myList->end = myList->end->prev;// now end points to the old ends previous
		tmp->prev = NULL; //Now tmp which was the END is now disconnected
	}
	
	return tmp;
}

int searchNode(List *myList, int input)// returns the first node containing value, 0 means no such node with value exists
{ 
	Node *tmp = myList->start;
	int nodeNum = 0;
	if (tmp != NULL)
	{
		nodeNum = 1;
		while (tmp->next !=NULL)
		{
			if (tmp->value != input)
			{
				tmp = tmp->next;
				nodeNum++;
			}
			else 
			{
				break;
			}
		}
	}
	if (tmp->next == NULL)
	{
		if (tmp->value == input)
		{
			nodeNum++;
		}
	}
	else
	{
		nodeNum = 0;
	}
	return nodeNum;
}	
void printList(List *myList, Node *tmp)
{
	int i = 1;
	tmp = myList->start;

	while (tmp != NULL)
	{
		printf("Node [%d]'s value = %d\n", i, tmp->value);
		i++;
		tmp = tmp->next;
	}
}

</code>


=====Reflection=====
  *As I stated earlier I felt this could possibly be the most important project we did this semester.  I really learned a lot.  This library was written quite some time ago and the best part is when I came back to it, I had learned enough to realize I could vastly improve upon it. Something I will possibly do in the future.
Lab46 Wiki

User Tools

Site Tools

Page Tools
