A project for Data Structures by Brandon Kennedy during the Fall 2011 Semester.

This project was begun on September 19th and is anticipated to take 1 week, but in actuality took 5 weeks.

By doing this project I hope to walk away with a better understanding of linked listing, nodes, library creation, use, and utilization.

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

The reason for doing this project is to pursue a better understanding of libraries, linked lists, nodes and codes optimization.

This basis for this project is to create a linked list that can be filled with data. I then want to be able to manipulate the data 6 different ways:

1. Insert data
2. remove data
3. append data
4. delete the list of data
5. find data in the list
6. copy the list of data

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:

• 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 (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).

• 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
• structs: this code will implement two structs.

/*
 * main.c - a program to execute 6 linked list modifiers
 * 
 * written by Brandon Kennedy for Data Structures on 6 weeks time...
 *
 * compile with:
 *   gcc -o main main.c -L. -ldll
 *
 * execute with:
 *   ./main
 */
 
 
#include"linkedlist.h"
 
int main()
{
        int i=0;
        int choice=0;
        int node=0;
        char input;
        char junk;
 
        List *mylist1;
        mylist1 = (List *) malloc (sizeof(List));
 
        mylist1 -> start = mylist1 -> end = mylist1 -> tmp =NULL;
 
        printf("Enter a character (@ to exit): ");
        scanf("%c", &input);
        scanf("%c", &junk);
        while(input != '@')
        {
                if(mylist1 -> start == NULL)
                {
                        mylist1 -> start = (Node *) malloc (sizeof(Node));
                        mylist1 -> end = mylist1 -> start; // only one node, start and end are same
                        mylist1 -> end -> next = NULL; // nothing after
                        mylist1 -> start -> prev = NULL; // nothing before
                        mylist1 -> tmp = mylist1 -> start; // tmp points to beginning of list
                        mylist1 -> start -> value = input; // enter value into node
                }
                else
                {
                        mylist1 = append(mylist1, mylist1 -> end, input);
                }
                printf("Enter a character (@ to exit): ");
                scanf("%c", &input);
                scanf("%c", &junk);
        }
 
        printf("You choices now are:\n");
        printf("\n");
        printf("   To insert before a node enter 1\n");
        printf("   To append after a node enter 2\n");
        printf("   To remove a node enter 3\n");
        printf("   To delete the list enter 4\n");
        printf("   To find a node via value, enter 5\n");
        printf("   To copy the existing list, enter 6\n");
        printf(" :");
        scanf("%d", &choice);
 
        i = 0;
        mylist1 -> tmp = mylist1 -> start;
        while (mylist1 -> tmp != NULL)
        {
                printf("[%d] value: %c\n", i, mylist1 -> tmp -> value);
                i++;
                mylist1 -> tmp = mylist1 -> tmp -> next;
        }
 
 
 
 
            if(choice == 1)//insert a node
        {
 
                printf("Please enter the node you wish to insert before: ");
                scanf("%d", &node);
                scanf("%c", &junk);
 
                printf("Please enter a character for that node: ");
                scanf("%c", &input);
                scanf("%c", &junk);
 
                mylist1 -> tmp = mylist1 -> start;
                for(i=0; i<node; i++) //position tmp at node to insert before
                {
                        mylist1 -> tmp = mylist1 -> tmp -> next;
                }
                insert(mylist1, mylist1 -> tmp, input);
 
                i = 0;
                mylist1 -> tmp = mylist1 -> start;
                while (mylist1 -> tmp != NULL)
                {
                        printf("[%d] value: %c\n", i, mylist1 -> tmp -> value);
                        i++;
                        mylist1 -> tmp = mylist1 -> tmp -> next;
                }
        }
        else if(choice == 2) //insert after node
        {
                printf("Please enter the node you wish to insert after: ");
                scanf("%d", &node);
                scanf("%c", &junk);
                printf("Please enter a character for that node: ");
                scanf("%c", &input);
                scanf("%c", &junk);
 
                mylist1 -> tmp = mylist1 -> start;
                for(i=0; i<node; i++) //position tmp at node to after before
                {
                        mylist1 -> tmp = mylist1 -> tmp -> next;
                }
                mylist1 = append(mylist1,mylist1 -> tmp, input);
 
                i = 0;
                mylist1 -> tmp = mylist1 -> start;
                while (mylist1 -> tmp != NULL)
                {
                        printf("[%d] value: %c\n", i, mylist1 -> tmp -> value);
                        i++;
                        mylist1 -> tmp = mylist1 -> tmp -> next;
                }
         }
        else if(choice == 3)//remove a node
        {
                printf("Please enter the node you wish to remove: ");
                scanf("%d", &node);
                scanf("%c", &junk);
 
                mylist1 -> tmp = mylist1 -> start;
                for(i=0; i<node; i++) //position tmp at node to delete
                {
                        mylist1 -> tmp = mylist1 -> tmp -> next;
                }
 
                printf("You removed the node in memory location [0x%x]\n", remov(mylist1, mylist1 -> tmp));
                printf("The node contained the value [%c]\n", mylist1 -> tmp -> value);
 
                i = 0;
                mylist1 -> tmp = mylist1 -> start;
                while (mylist1 -> tmp != NULL)
                {
                        printf("[%d] value: %c\n", i, mylist1 -> tmp -> value);
                        i++;
                        mylist1 -> tmp = mylist1 -> tmp -> next;
                }
 
        }
        else if(choice == 4)
        {
                deletelist(mylist1);
 
                i = 0;
                mylist1 -> tmp = mylist1 -> start;
                while (mylist1 -> tmp != NULL)
                {
                        printf("[%d] value: %c\n", i, mylist1 -> tmp -> value);
                        i++;
                        mylist1 -> tmp = mylist1 -> tmp -> next;
                }
 
        }
        else if(choice == 5)//find a value
        {
                scanf("%c", &junk);
                printf("Please enter the value of the node you wish to find: ");
                scanf("%c", &input);
                printf("The first instance of value [%c] is in memory address [0x%x]\n", input, find(mylist1, input));
        }
        else if(choice == 6)//copy a list
        {
                List *mylist2;
                mylist2 = (List *) malloc (sizeof(List));
 
                mylist2 = copy(mylist1);
 
                i = 0;
                mylist2 -> tmp = mylist2 -> start;
                printf("\n");
                printf("List 2\n");
                while (mylist2 -> tmp != NULL)
                {
                        printf("[%d] value: %c\n", i, mylist2 -> tmp -> value);
                        i++;
                        mylist2 -> tmp = mylist2 -> tmp -> next;
                }
        }
        else
        {
                printf("error, [%d] was not a choice\n", input);
                exit(1);
        }
}

/*
 * insert.c, used by linking.
 *
 * compile with gcc -c insert.c
 * List *insert(List *, Node *, char)
 * Accepts: a list struct containing start, end, and a tmp variable.
 * Returns:a list struct
 */
 
#include"linkedlist.h"
List *insert(List *mylist, Node *thing, char p)
{ // thing is node to insert before      p is character to insert in node
        Node* tmp2; // new node
        tmp2 = (Node *) malloc (sizeof(Node)); // new nodes size
        tmp2 -> value = p; // tmp's value is now what p was
        mylist -> tmp = thing;
        if(mylist -> tmp == mylist -> start) //if thing is first node in list
        {
                mylist -> start -> prev = tmp2;
                tmp2 -> next = mylist -> start;
                mylist -> start = mylist -> start -> prev;
        }
        else
        {
                mylist -> tmp -> prev -> next = tmp2;
                tmp2 -> prev = mylist -> tmp -> prev;
                tmp2 -> next = mylist -> tmp;
                mylist -> tmp -> prev = tmp2;
        }
        return mylist;
}

• remove.c, a function to remove a node
• Node *remov(List *, Node *)
• accepts a list struct and a node address
• returns a node address

#include"linkedlist.h"
Node *remov(List *mylist, Node *thing)//thing is the node you want to remove
{
        Node *tmp4;
        mylist -> tmp = thing;
        if((mylist -> tmp != mylist -> start) && (mylist -> tmp != mylist -> end))
        {// if thing is not the only node in the list
                tmp4 = thing;
                mylist -> tmp -> prev -> next = mylist -> tmp -> next;
                mylist -> tmp -> next -> prev = mylist -> tmp -> prev;
                mylist -> tmp -> next = NULL;
                mylist -> tmp -> prev = NULL;
        }
        else if(mylist -> tmp  == mylist -> start)
        {// if thing is first node
                mylist -> start = mylist -> start -> next;
                mylist -> start -> prev -> next = NULL;
                tmp4 = mylist -> start -> prev;
                mylist -> start -> prev = NULL;
        }
        else// if(mylist -> tmp == mylist -> end)
        {//if thing is last node
                mylist -> end = mylist -> end -> prev;
                mylist -> end -> next -> prev = NULL;
                tmp4 = mylist -> end -> next;
                mylist -> end -> next = NULL;
        }
        return tmp4;
}

  *append.c, a function to append a node
  *List *append(List *, Node *, char)
  *accepts a List struct, a Node, and a char
  *returns a list struct
 
 
#include "linkedlist.h"
 
List *append(List *mylist, Node *thing, char d)
{ // thing is the node to insert after
        Node* tmp3;
        tmp3 = (Node *) malloc (sizeof(Node));
        tmp3 -> value = d;
        mylist -> tmp = thing;
 
//      printf("%c", tmp3 -> value);
        if(mylist -> tmp  == mylist -> end)//one nnode in list
        {
                mylist -> end -> next = tmp3;
                tmp3 -> prev = mylist -> end;
                mylist -> end = mylist -> end -> next;
                mylist -> end -> next = NULL;
        }
        else
        {
                mylist -> tmp -> next -> prev = tmp3;
                tmp3 -> next = mylist -> tmp -> next;
                tmp3 -> prev = mylist -> tmp;
                mylist -> tmp -> next = tmp3;
        }
        return mylist;
}

  *copy.c, a function to copy a linked list
  *List *copy(List *)
  *accepts a list struct
  *returns a list struct
 
 
#include"linkedlist.h"
 
List *copy(List *mylist1)
{
        List *joe;
        joe = (List *) malloc (sizeof(List));
 
        joe -> start = joe -> end = joe -> tmp = NULL;
        joe -> start = (Node *) malloc (sizeof(Node));
        joe -> end = joe -> start;
        joe -> start -> value = mylist1 -> start -> value;
 
        mylist1 -> tmp = mylist1 -> start -> next;
 
        while(mylist1 -> tmp != NULL)
        {
                joe = append(joe, joe -> end, mylist1 -> tmp -> value);
                mylist1 -> tmp = mylist1 -> tmp -> next;
        }
        return joe;
}

  *find.c, function to find a ndoe by value
  *Node *find(List *,char)
  *accept a List struct
  *returns a Node address
 
 
#include"linkedlist.h"
Node *find(List *mylist, char f)
{
        Node *test2;
        test2 = mylist -> start;
        while((test2 != NULL)  && (test2 -> value != f))
        {
                if(test2 != NULL)
                {
                        test2 = test2 -> next;
                }
        }
        return test2;
}

  *delete.c, a function to delete an existing list
  *void deletelist(List *)
  *accepts a list struct
  *returns nothing
 
#include"linkedlist.h"
void deletelist(List *mylist) //function must be passed the first and last node in the list
{
        if(mylist -> start == mylist -> end)
        {//if only 1 node in list
                free(mylist -> end);
        }
        else
        {
                while(mylist -> start != mylist -> end)
                {
                        Node *tmp5;
                        tmp5 = mylist -> start;
                        mylist -> start = mylist -> start -> next;
                        tmp5 -> next -> prev = NULL;
                        tmp5 -> next = NULL;
                        free(tmp5);
                }
                free(mylist -> end);
        }
        mylist -> end = NULL;
        mylist -> start = NULL;
}

#ifndef _LINKED_LIST_H
#define _LINKED_LIST_H
#include<stdlib.h>
#include<stdio.h>
 
struct node {
        char value;
        struct node *next;
        struct node *prev;
};
typedef struct node Node;
 
struct list{
        struct node *start;
        struct node *end;
        struct node *tmp;
};
typedef struct list List;
 
List *copy(List *);
List *append(List *, Node *, char);
List *insert(List *, Node *, char);
Node *remov(List *, Node *);
void deletelist(List *);
Node *find(List *, char);
 
#endif

The execution of the above code is as follows:

lab46:~/src/DataS/Project1$ ./main
Enter a character (@ to exit): d
Enter a character (@ to exit): e
Enter a character (@ to exit): t
Enter a character (@ to exit): 5
Enter a character (@ to exit): 8
Enter a character (@ to exit): ^
Enter a character (@ to exit): @
You choices now are:

   To insert before a node enter 1
   To append after a node enter 2
   To remove a node enter 3
   To delete the list enter 4
   To find a node via value, enter 5
   To copy the existing list, enter 6
 :3
[0] value: d
[1] value: e
[2] value: t
[3] value: 5
[4] value: 8
[5] value: ^
Please enter the node you wish to remove: 3
You removed the node in memory location [0x1f1c090]
The node contained the value [5]
[0] value: d
[1] value: e
[2] value: t
[3] value: 8
[4] value: ^
lab46:~/src/DataS/Project1$ 

Comments/thoughts generated through performing the project, observations made, analysis rendered, conclusions wrought. What did you learn from doing this project?

This project was unbelievable! I have learned so much about linked lists, node manipulation and movement, and structs. I spent the last few weeks writing and deleting so much code. I wrote and re-wrote every function in an attempt to do it 4 different ways, until i finaly found a way to efficiently execute this code. To be honest, i almost gave up on this class/project a few times, and I am glad i didn't because i was only missing a few small things!

I learned to slow down! when writing code. Many times during this project i wrote a large portion of code fast, compiled it, ran it, got an error, and immediately gave up. Instead, i need to look over the code as i go along, and review what i am putting.

Also, ANY code can be optimized… kinda…

1. Cprogramming.com
2. The C Programming Language: book
3. MATT HAAS!!!!!!!!!