======Project: Doubly Linked List Library Implementation====== A project by John T. Rine (jr018429) for CSCS2320-Data Structures during the Fall 2011 semester. My linked list library is available for download from:\\ http://lab46.corning-cc.edu/~jr018429/linkedListLibrary.zip \\ Originally, I expected this project to take two weeks but it is now week 6 and I am just finishing it up. It didn't take me 6 weeks to do the linked list, I started working on a stack library project, but after the instructor told me he would prefer a linked list implementation of a stack library rather than an array-based one, I changed gears and began working on the linked list instead and I am glad I did! The linked list, while a data structure in and of itself, can be or is the basis for other data structures such as stacks and trees. Besides learning about linked lists and doubly linked lists in particular. I learned about and gained experience working with pointers to pointers, structures, pointers to structures, dereferencing pointers to structures, dereferencing pointers to pointers to structures, and creating and using a static library. =====Objectives===== The purpose of this project was to create a static doubly linked list library and use it with a test program to verify the library.\\ Since linked lists are used to implement other data structures, I suspect this library will be used in other data structure projects.\\ =====Prerequisites===== In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved: * understand and use the C/C++ programming language * understand and use functions * understand and use pointers in general * understand and use pointers to pointers * understand and use structs * understand and use pointers (referencing and dereferencing) to structures * understand and use pointer to pointers (refeencing and dereferencing) to structures * understand and use malloc() to dynamically allocate memory * understand and use free() to deallocate memory * understand the linked data structure (singly and doubly linked lists) in general * know how to create and use a static library * know how to build a doubly linked list library using the items listed above =====Background===== Originally, I was working on a stack data structure library, however, I was going to implement an array-based stack. The instructor wanted me to implement the stack library using a linked list rather than using an array so I backed up and created a linked list library first. I will then use the linked list library to implement a stack library. =====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===== The course requirement for Data Structures projects are listed at:\\ http://lab46.corning-cc.edu/haas/fall2011/data/projects This project has the following project attributes described on that page: ^Attribute^Qty Needed^Description^ |Pointers|8|Indirection/dereferencing are demonstarted| |malloc/new|4|Utilization of dynamic memory allocation| |Linked lists|2|Implementation/utilization of a stack| |Doubly Linked lists|4|Implementation/utilization of a stack| |Libraries|4|Implementation/utilization of non-core libc library| \\ This project, therefore, is eligible for 22 attributes, however, only 6 of these are achieveable per project, so project far exceeds the minimum attribute requirements. =====Code===== My library is composed of the following files and functions:\\ **linkedListLib.h**\\ linkedListLib.h is the header file for the linked list library. It should be included in any .c library files whose function prototypes have been added to it. Also, it must be added to any programs utilizing the library's functions.\\ Example code:\\ //linkedListLib.h //John T. Rine //October 5, 2011 #ifndef _LINKEDLIST_JR_H #define _LINKEDLIST_JR_H #include #include struct Node { int data; struct Node * prev; struct Node * next; }; typedef struct Node node; //linkedListLib1.c void createList(node **, node **, int); void destroyListHead(node *); void destroyListTail(node *); int listSizeHead(node *); //linkedListLib2.c int listSizeTail(node *); void printIntDataHead(node *); void insert(node **, node **, int, int); //linkedListLib3.c void append(node **, node **, int, int); void deleteNode(node **, node **, int); void loadListData(node *); //linkedListLib4.c void loadNode(node *, int, int); void createNode(node*, node*); void copyList(node *, node **, node **); int findData(node *, int); #endif \\ **linkedListLib1.c**\\ //linkedListLib1.c //John T. Rine //October 6, 2011 //lab46:~$ gcc -c linkedListLib.c -o linkedListLib.o //lab46:~$ ar crs liblinkedListLib.a linkedListLib.o //lab46:~$ gcc -I. linkedListTest.c -o linkedListTest liblinkedListLib.a #include #include //#include"linkedListLib1.h" #include"linkedListLib.h" void createList(node **headd, node **taill, int elements) { int i; node *new, *head, *tail; new = head = tail = NULL; for(i = 1; i<=elements; i++) { if (head == NULL) { head = (node *) malloc(sizeof(node)); tail = head; head->prev = NULL; head->next = NULL; } else { new = (node *) malloc(sizeof(node)); new->prev = tail; new->next = NULL; tail->next = new; tail = new; } } *headd = head; *taill = tail; } void destroyListHead(node *head) { node *temp; node *temp2; temp = NULL; temp2 = NULL; temp = head; while(temp != NULL) { temp2 = temp->next; if (temp->prev != NULL) temp->prev = NULL; if (temp->next != NULL) temp->next = NULL; free(temp); temp = temp2; } } void destroyListTail(node *tail) { node *temp; node *temp2; temp = NULL; temp2 = NULL; temp = tail; while(temp != NULL) { temp2 = temp->prev; if (temp->prev != NULL) temp->prev = NULL; if (temp->next != NULL) temp->next = NULL; free(temp); temp = temp2; } } int listSizeHead(node *head) { int size = 0; while (head != NULL) { head = head->next; size++; } return size; } \\ **linkedListLib2.c**\\ //linkedListLib2.c //John T. Rine //October 6, 2011 //lab46:~$ gcc -c linkedListLib.c -o linkedListLib.o //lab46:~$ ar crs liblinkedListLib.a linkedListLib.o //lab46:~$ gcc -I. linkedListTest.c -o linkedListTest liblinkedListLib.a #include #include //#include"linkedListLib2.h" #include"linkedListLib.h" int listSizeTail(node *tail) { int size = 0; while (tail != NULL) { tail = tail->prev; size++; } return size; } void printIntDataHead(node * head) { node * temp = NULL; temp = head; while(temp != NULL) { printf("%d ",temp->data); temp = temp->next; } printf("\n"); } void insert(node ** head, node ** tail, int position, int data) { int i; node *temp, *temp2; temp = temp2 = NULL; temp = *head; for(i = 0; i < position; i++) { temp = temp -> next; } if (*head == NULL) { *head = (node *) malloc(sizeof(node)); *tail = *head; (*head)->prev = NULL; (*head)->next = NULL; (*head)->data = data; } else if (*head == temp) { temp2 = (node *) malloc (sizeof(node)); temp2->next = *head; (*head)->prev = temp2; *head = (*head)->prev; (*head)->prev = NULL; (*head)->data = data; } else { temp2 = (node *) malloc (sizeof(node)); temp2->next = temp; temp2->prev = temp->prev; temp->prev->next = temp2; temp->prev = temp2; temp2->data = data; } } \\ **linkedListLib3.c**\\ //linkedListLib3.c //John T. Rine //October 6, 2011 //lab46:~$ gcc -c linkedListLib.c -o linkedListLib.o //lab46:~$ ar crs liblinkedListLib.a linkedListLib.o //lab46:~$ gcc -I. linkedListTest.c -o linkedListTest liblinkedListLib.a #include #include //#include"linkedListLib3.h" #include"linkedListLib.h" void append(node **head, node **tail, int position, int data) { int i; node *temp, *temp2; temp = temp2 = NULL; temp = *head; for(i = 0; i < position; i++) { temp = temp -> next; } if (*head == NULL) { *head = (node *) malloc(sizeof(node)); *tail = *head; (*head)->prev = NULL; (*head)->next = NULL; (*head)->data = data; } else if (*tail == temp) { temp2 = (node *) malloc (sizeof(node)); temp2->prev = *tail; temp2->next = NULL; (*tail)->next = temp2; *tail = temp2; (*tail)->data = data; } else { temp2 = (node *) malloc (sizeof(node)); temp2->prev = temp; temp2->next = temp->next; temp->next->prev = temp2; temp->next = temp2; temp2->data = data; } } void deleteNode(node **head, node **tail, int position) { int i; node * temp = NULL; temp = *head; for(i = 0; i < position; i++) { temp = temp->next; } if(temp != *head && temp != *tail) { temp->next->prev = temp->prev; temp->prev->next = temp->next; temp->prev = NULL; temp->next = NULL; } else if (temp == *head) { temp->next->prev = NULL; *head = temp->next; temp->next = NULL; } else { temp->prev->next = NULL; *tail = temp->prev; temp->prev = NULL; } free(temp); } void loadListData(node *head) { int i = 0; node *temp = NULL; temp = head; printf("Enter a value or -1 to quit: "); scanf("%d", &i); while(i != -1) { temp->data = i; temp = temp->next; if(temp == NULL) { printf("List is full of data!\n"); break; } printf("Enter a value or -1 to quit: "); scanf("%d", &i); } } \\ **linkedListLib4.c**\\ //linkedListLib4.c //John T. Rine //October 6, 2011 //lab46:~$ gcc -c linkedListLib.c -o linkedListLib.o //lab46:~$ ar crs liblinkedListLib.a linkedListLib.o //lab46:~$ gcc -I. linkedListTest.c -o linkedListTest liblinkedListLib.a #include #include //#include"linkedListLib4.h" #include"linkedListLib.h" void loadNode(node *head, int position, int value) { int i; node *temp = NULL; temp = head; temp = head; for(i = 0; i < position; i++) { temp = temp->next; } temp->data = value; } void createNode(node* head, node* tail) { head = (node *) malloc(sizeof(node)); tail = head; head->prev = NULL; head->next = NULL; } void copyList(node *head, node **copyHead, node **copyTail) { node *new, *temp; new = *copyHead = *copyTail = temp = NULL; temp = head; while(temp != NULL) { if (*copyHead == NULL) { *copyHead = (node *) malloc(sizeof(node)); *copyTail = *copyHead; (*copyHead)->prev = NULL; (*copyHead)->next = NULL; (*copyHead)->data = temp->data; } else { new = (node *) malloc(sizeof(node)); new->prev = *copyTail; new->next = NULL; (*copyTail)->next = new; *copyTail = new; (*copyTail)->data = temp->data; } temp = temp->next; } } int findData(node *head, int data) { int counter = 0; while(head != NULL) { if(head->data == data) break; counter++; head = head->next; } return counter; } \\ **linkedListTest.c**\\ //linkedListTest.c //Author: John T. Rine //Date: October 5, 2011 #include "linkedListLib.h" int main(int argc, char **argv) { node *head, *tail, *copyHead, *copyTail, *temp; head = tail = copyHead = copyTail = NULL; int i = 1; printf("Creating a list of 4 nodes...\n"); createList(&head, &tail, 4); printf("Size of the list is: %d\n", listSizeHead(head)); printf("Load list data\n"); loadListData(head); printIntDataHead(head); printf("Inserting node 0 with data of 3200 before head node...\n"); insert(&head, &tail, 0, 3200); printf("Size of the list is: %d\n", listSizeHead(head)); printIntDataHead(head); printf("Inserting node with data of -3200 before tail node...\n"); insert(&head, &tail, listSizeHead(head) - 1, -3200); printf("Size of the list is: %d\n", listSizeHead(head)); printIntDataHead(head); printf("Appending node with data of 2300 after head node...\n"); append(&head, &tail, 0, 2300); printf("Size of the list is: %d\n", listSizeHead(head)); printIntDataHead(head); printf("Appending node with data of -2300 after tail node...\n"); append(&head, &tail, listSizeHead(head) - 1, -2300); printf("Size of the list is: %d\n", listSizeHead(head)); printIntDataHead(head); printf("Loading node 0 with data of 0...\n"); loadNode(head, 0, 0); printf("Size of the list is: %d\n", listSizeHead(head)); printIntDataHead(head); printf("Loading tail node with data of 255...\n"); loadNode(head, listSizeHead(head) - 1, 255); printf("Size of the list is: %d\n", listSizeHead(head)); printIntDataHead(head); printf("Deleting head node...\n"); deleteNode(&head, &tail, 0); printf("Size of the list is: %d\n", listSizeHead(head)); printIntDataHead(head); printf("Deleting tail node...\n"); deleteNode(&head, &tail, listSizeHead(head) - 1); printf("Size of the list is: %d\n", listSizeHead(head)); printIntDataHead(head); printf("Deleting node 2...\n"); deleteNode(&head, &tail, 2); printf("Size of the list is: %d\n", listSizeHead(head)); printIntDataHead(head); copyList(head, ©Head, ©Tail); printf("Size of the list is: %d\n", listSizeHead(copyHead)); printIntDataHead(copyHead); printf("The node location of 3 is %d\n", findData(copyHead, 3)); destroyListHead(head); getchar(); //Holds the console window open on a Windows machine } \\ **makeLinkedList.bat**\\ The Windows batch file makeLinkedList.bat automates, manufacture of all of the .o files, the creation of the static library file, compiling, linking, and execution of linkedListTest, the test file.\\ Example code:\\ del *.o del *.exe del *.a gcc -c linkedListLib1.c -o linkedListLib1.o rem pause gcc -c linkedListLib2.c -o linkedListLib2.o rem pause gcc -c linkedListLib3.c -o linkedListLib3.o rem pause gcc -c linkedListLib4.c -o linkedListLib4.o rem pause ar rcs libLinkedListdll.a *.o rem pause gcc -I. linkedListTest.c -o linkedListTest libLinkedListdll.a rem pause linkedListTest pause \\ **makeLinkedList.sh**\\ The bash shell script file makeLinkedList.sh automates the manufacture of all of the .o files, the creation of the static library file, compiling, linking and execution of linkedListTest, the test file.\\ Example code:\\ #!/bin/bash gcc -c linkedListLib1.c -o linkedListLib1.o gcc -c linkedListLib2.c -o linkedListLib2.o gcc -c linkedListLib3.c -o linkedListLib3.o gcc -c linkedListLib4.c -o linkedListLib4.o ar rcs libLinkedListdll.a *.o gcc -I. linkedListTest.c -o linkedListTest libLinkedListdll.a ./linkedListTest =====Execution===== Creation and execution of the linkedListTest program (Windows):\\ C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>del *.o Could Not Find C:\Documents and Settings\rinejt\Desktop\linkedListLibrary\*.o C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>del *.exe Could Not Find C:\Documents and Settings\rinejt\Desktop\linkedListLibrary\*.exe C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>del *.a Could Not Find C:\Documents and Settings\rinejt\Desktop\linkedListLibrary\*.a C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>gcc -c linkedListLib1 .c -o linkedListLib1.o C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>rem pause C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>gcc -c linkedListLib2 .c -o linkedListLib2.o C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>rem pause C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>gcc -c linkedListLib3 .c -o linkedListLib3.o C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>rem pause C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>gcc -c linkedListLib4 .c -o linkedListLib4.o C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>rem pause C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>ar rcs libLinkedListd ll.a *.o C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>rem pause C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>gcc -I. linkedListTes t.c -o linkedListTest libLinkedListdll.a C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>rem pause C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>linkedListTest Creating a list of 4 nodes... Size of the list is: 4 Load list data Enter a value or -1 to quit: 1 Enter a value or -1 to quit: 2 Enter a value or -1 to quit: 3 Enter a value or -1 to quit: 4 List is full of data! 1 2 3 4 Inserting node 0 with data of 3200 before head node... Size of the list is: 5 3200 1 2 3 4 Inserting node with data of -3200 before tail node... Size of the list is: 6 3200 1 2 3 -3200 4 Appending node with data of 2300 after head node... Size of the list is: 7 3200 2300 1 2 3 -3200 4 Appending node with data of -2300 after tail node... Size of the list is: 8 3200 2300 1 2 3 -3200 4 -2300 Loading node 0 with data of 0... Size of the list is: 8 0 2300 1 2 3 -3200 4 -2300 Loading tail node with data of 255... Size of the list is: 8 0 2300 1 2 3 -3200 4 255 Deleting head node... Size of the list is: 7 2300 1 2 3 -3200 4 255 Deleting tail node... Size of the list is: 6 2300 1 2 3 -3200 4 Deleting node 2... Size of the list is: 5 2300 1 3 -3200 4 Size of the list is: 5 2300 1 3 -3200 4 The node location of 3 is 2 C:\Documents and Settings\rinejt\Desktop\linkedListLibrary>pause Press any key to continue . . . \\ Creation and execution of the linkedListTest program (Linux):\\ lab46:~/src/data/linkedListLibrary$ ./makeLinkedList.sh Creating a list of 4 nodes... Size of the list is: 4 Load list data Enter a value or -1 to quit: 1 Enter a value or -1 to quit: 2 Enter a value or -1 to quit: 3 Enter a value or -1 to quit: 4 List is full of data! 1 2 3 4 Inserting node 0 with data of 3200 before head node... Size of the list is: 5 3200 1 2 3 4 Inserting node with data of -3200 before tail node... Size of the list is: 6 3200 1 2 3 -3200 4 Appending node with data of 2300 after head node... Size of the list is: 7 3200 2300 1 2 3 -3200 4 Appending node with data of -2300 after tail node... Size of the list is: 8 3200 2300 1 2 3 -3200 4 -2300 Loading node 0 with data of 0... Size of the list is: 8 0 2300 1 2 3 -3200 4 -2300 Loading tail node with data of 255... Size of the list is: 8 0 2300 1 2 3 -3200 4 255 Deleting head node... Size of the list is: 7 2300 1 2 3 -3200 4 255 Deleting tail node... Size of the list is: 6 2300 1 2 3 -3200 4 Deleting node 2... Size of the list is: 5 2300 1 3 -3200 4 Size of the list is: 5 2300 1 3 -3200 4 The node location of 3 is 2 lab46:~/src/data/linkedListLibrary$ \\ After verifying the linked list library, I then added the linkedListLibrary directory and its files to the Subversion repository.\\ lab46:~/src/data/linkedListLibrary$ svn add linkedListLib*.* svn: warning: 'linkedListLib.c' is already under version control svn: warning: 'linkedListLib.h' is already under version control A linkedListLib1.c A linkedListLib1.h A (bin) linkedListLib1.o A linkedListLib2.c A linkedListLib2.h A (bin) linkedListLib2.o A linkedListLib3.c A linkedListLib3.h A (bin) linkedListLib3.o A linkedListLib4.c A linkedListLib4.h A (bin) linkedListLib4.o lab46:~/src/data/linkedListLibrary$ svn add libjrdll.a A (bin) libjrdll.a After adding the linked list library files to the Subversion repository, I committed them as well.\\ lab46:~/src/data/linkedListLibrary$ svn commit -m "Per the instructor's instructions, I broke up the linkedListLib.c and .h into 4 separate files and used them to create libjrdll.a static library -John Rine" Adding linkedListLibrary/linkedListLib1.c Adding linkedListLibrary/linkedListLib1.h Adding (bin) linkedListLibrary/linkedListLib1.o Adding linkedListLibrary/linkedListLib2.c Adding linkedListLibrary/linkedListLib2.h Adding (bin) linkedListLibrary/linkedListLib2.o Adding linkedListLibrary/linkedListLib3.c Adding linkedListLibrary/linkedListLib3.h Adding (bin) linkedListLibrary/linkedListLib3.o Adding linkedListLibrary/linkedListLib4.c Adding linkedListLibrary/linkedListLib4.h Adding (bin) linkedListLibrary/linkedListLib4.o Sending linkedListLibrary/linkedListTest Transmitting file data ............. Committed revision 12. lab46:~/src/data/linkedListLibrary$ svn commit -m "The static library, libjrdll.a, has been added and committed to the svn repository -John Rine" Adding (bin) linkedListLibrary/libjrdll.a Transmitting file data . Committed revision 13. lab46:~/src/data/linkedListLibrary$ Cleaning up and committing Linked List Library:\\ lab46:~/src/data/linkedListLibrary$ svn add makeLinkedList.sh A makeLinkedList.sh lab46:~/src/data/linkedListLibrary$ svn add makeLinkedList.bat A makeLinkedList.bat lab46:~/src/data/linkedListLibrary$ svn commit -m "Added and committed files to clean up the linked list library -John T. Rine" Sending linkedListLibrary/linkedListLib.h Sending linkedListLibrary/linkedListLib1.c Sending linkedListLibrary/linkedListLib2.c Sending linkedListLibrary/linkedListLib3.c Sending linkedListLibrary/linkedListLib4.c Adding linkedListLibrary/makeLinkedList.bat Adding linkedListLibrary/makeLinkedList.sh Transmitting file data ....... Committed revision 23. lab46:~/src/data/linkedListLibrary$ =====Reflection===== Before starting this project, I was very apprehensive about working with linked lists, however, through the examples of code blocks and drawings of nodes with pointers that Matthew showed the class and through conversations I had with Matthew both e-mail and in person, I have becmome comfortable implementing the functions that create and manipulate them. I have learned to work with double indirection of structure pointers, and structure pointer syntax. I have also learned how to create and use a static library. =====References===== In performing this project, the following resources were referenced: * First and foremost, our instructor, Matthew Haas, thanks Matt! * Wikipedia-Linked Lists * Creating a Static Library * http://cslibrary.stanford.edu/103/LinkedListBasics.pdf * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_linklist.aspx