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 Data Structures by Brad Hammond during the Fall of 2011.

This project was begun on DATE and is anticipated to take 1 week. (Upon completion you can correct this with the actual length).

=====Objectives=====
State the purpose of this project. What is the point of this project? What do we hope to accomplish by undertaking it?

=====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 purpose of this project is to build a custom implementation of a doubly linked list. A linked list is a series of nodes. Each nodes contain a value and two pointers, one that points to the next node and one which points to the previous node. The first node's previous pointer and the final nodes next pointer both point to NULL as there are no nexts from the end or prevs from the beginning. 
=====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=====

  * 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=====

<code c>
#include "List.h"
#include <stdlib.h>

List *create() 
{
	List *list;
	list = (List*) malloc(sizeof(List));
	list -> first = list -> last = list -> temp = list -> temp2 = NULL;
	list -> length = 0;	

	return list;
}

void appendToList(List* list, int i)
{
	if (list -> first == NULL) {
		list -> first = (Node*) malloc(sizeof(Node));
		list -> last = list -> first;
		list -> first -> prev = NULL;
		list -> first -> next = NULL;
		list -> first -> value = i;
	} else {
		list -> temp = (Node*) malloc(sizeof(Node));
		list -> last -> next = list -> temp;
		list -> temp -> prev = list -> last;
		list -> last = list -> temp;
		list -> last -> value = i;
		list -> last -> next = NULL;
	}

	list -> length++;
}

int insertInList(List *list, int pos, int i)
{
	int x, error = 0;
	
	list -> temp = list -> first;
	
	if (list -> first == NULL)
		appendToList(list, i);

	if (pos < 0 || pos > list -> length ) 
		error = -1;
	else {	
		for (x = 0; x < pos; x++)
			list -> temp = list -> temp -> next;
		if (list -> first == NULL) {
			list -> first = (Node*) malloc(sizeof(list));
			list -> last = list -> first;
			list -> temp = list -> first;
			list -> first -> prev = NULL;
			list -> first -> next = NULL;
			list -> first -> value = i;
		} else if (list -> first == list -> temp) {
			list -> temp2 = (Node*) malloc(sizeof(Node));
			list -> temp2 -> next = list -> first;
			list -> temp2 -> prev = NULL;
			list -> first -> prev = list -> temp2;
			list -> temp2 -> value = i;
			list -> first = list -> temp2;
		} else {
			list -> temp2 = (Node*) malloc(sizeof(Node));
			list -> temp2 -> prev = list -> temp -> prev;
			list -> temp2 -> next = list -> temp;
			list -> temp -> prev -> next = list -> temp2;
			list -> temp -> prev = list -> temp2;
			list -> temp2 -> value = i;
		}
		list -> length++;
		error = 0;
	}
	return error;
}

int listLength(List *list)
{
	return list -> length;
}

int deleteNode(List *list, int pos)
{
	int i;
	
	if (list -> first == NULL || pos < 0 || pos > list -> length ) 
		return -1;
		
	list -> temp = list -> first;

	for (i = 0; i < pos; i++)
		list -> temp = list -> temp -> next;
	
	if ((list -> temp != list -> first) && (list -> temp != list -> last)) {
		list -> temp -> prev -> next = list -> temp -> next;
		list -> temp -> next -> prev = list -> temp -> prev;
		list -> temp -> prev = NULL;
		list -> temp -> next = NULL;
		free(list -> temp);
	} else if (list -> first == list -> last) {
		free(list -> temp);
	} else if (list -> temp == list -> first) {
		list -> temp -> next -> prev = NULL;
		list -> first = list -> first -> next;
		list -> temp -> next = NULL;	
		free(list -> temp);
	} else {
		list -> temp -> prev -> next = NULL;
		list -> last = list -> last -> prev;
		list -> temp -> prev = NULL;
		free(list -> temp);
	}
	
	list -> length--;
	
	return 0;
}

int getValue(List *list, int pos)
{
	int i, v;

	if (list == NULL || pos > list -> length || pos < 0)
		return -1;
	list -> temp = list -> first;

	for (i = 0; i < pos; i++)
		list -> temp = list -> temp -> next;
	
	v = list -> temp -> value;

	return v;
}

int searchList(List *list, int v)
{
	int i = 0, found = 0;
	
	list -> temp = list -> first;
	
	while (!found && i < listLength(list)) {
		if (list -> temp -> value == v)
			found = 1;
		else {
			i++;
			list -> temp = list -> temp -> next;
		}
	}
	
	if (i == listLength(list))
		i = -1;
		
	return i;
}

int deleteList(List* list)
{
	if (list == NULL)
		return -1;
	else
		while (listLength(list) >0)
			deleteNode(list, listLength(list) - 1);
	
	return 0;
}

List *copyList(List* l1, List* l2)
{
	List *start;
	int i = 0;
	
	if (l1 == NULL || l2 == NULL)
		return NULL;
	else {
		start = l2;
		while (i < listLength(l1))
			appendToList(l2, getValue(l1, i++));
	}
	
	return start;
}
</code>

=====Execution=====
Again, if there is associated code with the project, and you haven't already indicated how to run it, provide a sample run of your code:

<cli>
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs/LinkedList$ ./main2
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 1
Enter a value: 2
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 1
Enter a value: 4
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 2
Enter a value: 1
Enter a position: 0
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 3
List currently has 3 nodes.
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 4
Enter a position: 0
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 3
List currently has 2 nodes.
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 6
Enter a value: 2
Position of value 2 is 0.
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 7
0
List deleted
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 3
List currently has 0 nodes.
1) Append to the list
2) Insert before a position in the list
3) Get the length of the list
4) Delete a node from the list
5) Get a value from a position in the list
6) Get a position in the list based on a value
7) Delete the entire list
8) Quit
Make a selection: 8
Quitting...

</cli>

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

Making a customized linked list implementation based on the code that we did in class really helped to clear up a lot of the lower level details of the list. The biggest step in creating the list is to realize what smaller steps are going to need to be taken. Assigning values in a list isn't as simple as assigning a value to an array.  For instance, in order to append to the list we can't just magically pop a value at the end of the list. The first thing that would need to be done is to allocate space for a new node which can be assigned to the next node. Once this is done, we reassign the current node's next and then assign the appropriate values to the new node's prev and next pointers. Finally, the value can be assigned to our new node and increment the length of the list. This is the biggest hurdle in learning about linked lists. To assign a value it isn't simply one step but several steps.
=====References=====
In performing this project, the following resources were referenced:

  * [[http://en.wikipedia.org/wiki/Linked_list|Linked List - Wikipedia]]
  * /var/public/data/doubly2.c

Generally, state where you got informative and useful information to help you accomplish this project when you originally worked on it (from Google, other wiki documents on the Lab46 wiki, etc.)
Lab46 Wiki

User Tools

Site Tools

Page Tools
