======Project: Doubly Linked List Library Implementation====== A project for Data Structures by Dave Schoeffler during the Fall 2011 semester. This project was begun on September 19th and was completed on October 14th. =====Objectives===== The purpose of this project is to explore the nature of doubly linked lists through their use in various functions. This project will also require an understanding of malloc(), structs, pointers and passing them to functions. The understanding of the preceding will allow me to successfully create a linked data structure. =====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===== The point of this project is to implement a linked list that will store characters. A linked list is a data structure that is made up of a group of "nodes" that store data. The data that is stored in each node is made up pointers to other nodes as well as the information(the content). The content can be a simple data type like an int variable and can be more complex like an array. Linked lists can come in several different variations. There are singly linked lists and doubly linked lists. Singly linked lists are simpler, that is because each node contains only one pointer(the pointer to the next node), where as in doubly linked lists, each node contains 2 pointers(one pointer that points to the previous node and one that points to the next node). This project will implement a doubly linked list the stores character data. It will give the user functionality to manipulate the nodes of the linked list. =====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 * **removeNode**: 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 * **display**: display the contents of a linked list =====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 =====Code===== ===Implementation program=== /*Author: Dave Schoeffler * Purpose: This Program implements my linked list library * of functions. This library gives you the functionality * to create a linked list, append a node to the list, delete * a node from the list search for a value in the list, insert * a node in the list and display the list. This program is menu * driven. * Compile with: gcc -o mainLinked mainLinked.c -L. -ldll * * Execute with: ./mainLinked * */ // Include files #include #include #include "linkedlist.h" // main function int main() { // declare variables int i = 0, index, flag = 0, count = 5; char junk, input, input2, choice; Node *start, *end, *tmp, *tmp2, *tmp3; // initialize variables start = end = tmp = tmp2 =tmp3 = NULL; create(&start, &end, &tmp); //main while loop that allows the user to perform multiple operations while (flag == 0) { printf("Select which operation to perform on the linked list.\n"); printf("Enter - 1 - to append node to list.\n"); printf("Enter - 2 - to delete node from list.\n"); printf("Enter - 3 - to search for a value in a node.\n"); printf("Enter - 4 - to insert a node in a list.\n"); printf("Enter - 5 - to display list.\n"); printf("Enter - q - to quit.\n"); scanf("%c", &choice); scanf("%c", &junk); switch(choice) { case '1': printf("Enter character to append to list: "); scanf("%c", &input); scanf("%c", &junk); append(&end, input); display(&start); break; case '2': printf("Enter node number to delete: "); scanf("%d", &index); scanf("%c", &junk); printf("count list = %d\n", countList(start, count)); while( index < 0 || index > countList(start, count)) { printf("Invalid index... Re-enter valid index: "); printf("Enter node number to delete: "); scanf("%d", &index); scanf("%c", &junk); } removeNode(&start, &end, index); display(&start); break; case '3': printf("Enter character you wish to find: "); scanf("%c", &input); scanf("%c", &junk); tmp3 = search(&start, input); if(input == tmp3 -> value) { printf("The value %c was found in the list\n", tmp3 -> value); } else { printf("Sorry. That value was not found in the list\n"); } break; case '4': printf("Enter node position to insert before: "); scanf("%d", &index); scanf("%c", &junk); printf("Enter a value for new node: "); scanf("%c", &input2); scanf("%c", &junk); insert(&start, &end, index, input2); display(&start); break; case '5': display(&start); break; case 'q': case 'Q': flag = 1; break; default: printf("Invalid entry!\n"); break; } } return 0; } === header file === #ifndef_LINKED_LIST_H #define _LINKED_LIST_H // Create our node structure struct node { char value; struct node *next; struct node *prev; }; typedef struct node Node; void append(Node** end, char input); void removeNode(Node** start, Node** end, int index); Node* search(Node** start, char ch); void display(Node** start); Node* create(Node** start, Node** end, Node** tmp); void deleteList(Node** start,Node** end); #endif === functions === //Author: Dave Schoeffler // Function append() adds a new node onto the end of a linked list #include "linkedlist.h" #include void append(Node** end, char input) { Node* tmp; tmp = (*end); 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 } //Function removeNode() removes a node from a given list and frees the memory for that node #include "linkedlist.h" #include void removeNode(Node** start, Node** end, int index) { // Remove a node from the list int i; Node* tmp; tmp = *start; // Move tmp to exact node we wish to delete for( i=0; i 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(tmp); } 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 } } //Function search() searches a given list for a given value. If that value is found the //function returns the pointer to that node. If the is not found it returns a node with //a value of '#' #include "linkedlist.h" #include Node* search(Node** start, char ch) { Node* tmp; Node* tmp3; tmp = *start; int flag = 0; tmp3 = malloc(sizeof(Node)); while((tmp->value != ch)&&(flag == 0)) { if(tmp -> next != NULL) { tmp = tmp -> next; } else { flag = 1; } } if (flag == 1) { tmp3 -> value = '#'; tmp = tmp3; } return tmp; } //Function display() displays the contents of a linked list #include #include "linkedlist.h" void display(Node** start) { int i = 0; Node* tmp; tmp = *start; while (tmp != NULL) { printf("[%d] value: %c\n", i, tmp -> value); i++; tmp = tmp -> next; } } //Function create() allows the user to enter values to be stored in a linked list #include #include #include "linkedlist.h" void create(Node** start, Node** end, Node** tmp) { char input,junk; printf("Enter a character (# to quit): "); scanf("%c", &input); scanf("%c", &junk); // build our list while (input != '#') { 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 character (# to quit): "); scanf("%c", &input); scanf("%c", &junk); } } =====Execution===== The following shows the execution and demonstration of the functions that I wrote. lab46:~/src/data$ ./mainLinked Enter a character (# to quit): t Enter a character (# to quit): e Enter a character (# to quit): s Enter a character (# to quit): t Enter a character (# to quit): # Select which operation to perform on the linked list. Enter - 1 - to append node to list. Enter - 2 - to delete node from list. Enter - 3 - to search for a value in a node. Enter - 4 - to insert a node in a list. Enter - 5 - to display list. Enter - q - to quit. 1 Enter character to append to list: x [0] value: t [1] value: e [2] value: s [3] value: t [4] value: x Select which operation to perform on the linked list. Enter - 1 - to append node to list. Enter - 2 - to delete node from list. Enter - 3 - to search for a value in a node. Enter - 4 - to insert a node in a list. Enter - 5 - to display list. Enter - q - to quit. 2 Enter node number to delete: 0 count list = 4 [0] value: e [1] value: s [2] value: t [3] value: x Select which operation to perform on the linked list. Enter - 1 - to append node to list. Enter - 2 - to delete node from list. Enter - 3 - to search for a value in a node. Enter - 4 - to insert a node in a list. Enter - 5 - to display list. Enter - q - to quit. 3 Enter character you wish to find: t The value t was found in the list Select which operation to perform on the linked list. Enter - 1 - to append node to list. Enter - 2 - to delete node from list. Enter - 3 - to search for a value in a node. Enter - 4 - to insert a node in a list. Enter - 5 - to display list. Enter - q - to quit. 4 Enter node position to insert before: 0 Enter a value for new node: t [0] value: t [1] value: e [2] value: s [3] value: t [4] value: x Select which operation to perform on the linked list. Enter - 1 - to append node to list. Enter - 2 - to delete node from list. Enter - 3 - to search for a value in a node. Enter - 4 - to insert a node in a list. Enter - 5 - to display list. Enter - q - to quit. 5 [0] value: t [1] value: e [2] value: s [3] value: t [4] value: x Select which operation to perform on the linked list. Enter - 1 - to append node to list. Enter - 2 - to delete node from list. Enter - 3 - to search for a value in a node. Enter - 4 - to insert a node in a list. Enter - 5 - to display list. Enter - q - to quit. q lab46:~/src/data$ =====Reflection===== Wow! I learned so many things during this project. Going into this project I thought I had a good knowledge of what a linked list was. After running into a few problems(mostly having to do with passing structs to functions). I realized I needed to study up a little bit more. I was able to work through these problems and get the functions to work. I had some problems when I tried to copy my list into another list. This happened because I used double indirection to pass my node pointers to other function. Matt and me discovered that when passing the node using single indirection it was only passing the contents of the node but not the address of the original node. So to get around this we used double indirection. This caused problems when trying to copy a node. Matt said to forget about copy() for the meantime and just get everything else working which I did(thanks Matt). I still plan on coming back to this later. Overall I learned a whole lot about linked lists and the knowledge I gained from this is already helping me understand more about stacks(and queue's from what I hear). =====References===== In performing this project, the following resources were referenced: * http://en.wikipedia.org/wiki/Linked_list * C++ Programming __D.S. Malik__ * Matthew Haas * a few other internet sources I do not remember :)