Lab46 Wiki

User Tools

Site Tools

You are here: start » user » kkrauss1 » portfolio » libdll
user:kkrauss1:portfolio:libdll

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
user:kkrauss1:portfolio:libdll [2011/12/12 19:05] – [Objectives] kkrauss1user:kkrauss1:portfolio:libdll [2011/12/12 19:58] (current) – [Objectives] kkrauss1
Line 1: Line 1:
 +======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.  
  

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki