Lab46 Wiki

While the basic components of data structures are the stacks, linkages and sorted piles of these built-in storage spaces, it is the algorithms that are used to implement and traverse these structures that make the topic so special to computer scientists around the world. Data storage combined with clever algorithms are the keys in the resulting data structure that make it more easily integrated into a vast array of implementations.

While the concept of a data type is usually applied to programming languages, the idea comes from the way humans commonly interact with data. We are able to apply certain lessons (I.E. common sense) to the information we receive, and therefore make decisions on how we manipulate it. However, one of the primary pitfalls of modern computing is that that computers do not have common sense. Therefore, there must be some type of language that can communicate instruction and data to the machine. Further, this language must consider the characteristics of the data which it communicates in order to communicate the correct instructions.

Given a number (use 4), a letter (use R) and a 3rd grade education, it should be immediately apparent that these two pieces of data are not necessarily interchangable. That is, a 4 cannot be added to an R, an R cannot be sorted based on its relationship with a 4. The human mind can arrive at the conclusion that more information is required to achieve these tasks. Humans are able to make a distinction between a number and a letter based upon common understanding. That is, humans can assign one “type” to symbols from the alphabet, and another “type” to symbols coming from the set of numbers. Humans can then create codes or “mappings” such that an R can indicate the number 17; or, the number 4 can indicate the letter D.

By assigning a type to the data, common interactions are made more predictable. Data types provide a jumping-off point where we can begin to make data more interchangable or, quickly prove that certain types are NOT interchangable.

Just like a storage facility owner, a computer assigns memory in the order that requests are received, based upon the expected size of the data. However, the key difference between the storage facility and the computer lies in the way they each deal with overflow. In the real world example of the storage facility, overflowing your storage space might not be a big deal, as your neighbor might be willing to share some space with you, or at the very least, let you sublet. However, there is no sharing in computing. The space is either yours, or it is not. Further, since the computer makes no consideration for political implications, it simply assumes that the next available storage spot must be empty, and therefore ripe for the picking. It fills up the storage area, and in the process removes its previous contents. As you can imagine, when the tenant comes back to find their storage space full of someone else’s stuff (and their own stuff missing), the fur flies. Now imagine you’re neighbor is Iran. Data types prevent these potential electronic “fist-a-cuffs” by giving the processor a place to start, and a place to end.

The most common of the simple types are:

• Integer data type (int); typically used to store values between -2,147,483,648 to 2,147,483,647,
• Character data type (char); used to store single characters of data
• Boolean data type (bool); used to store a single bit, true or false

Each simple data type has a domain of possible values (certainly finite), and is assigned a finite amount of space (in memory) that it may occupy. Further, each data type is given a name, and that name is used to instantiate variables (objects) of that data type. The computer uses the name to assign the correct amount of storage space and that storage space has an address. Further, based upon the name, the computer is able to determine the possible interactions that are allowed upon the data.

The pointer data type is slightly different than typical simple data types, in that the domain of the pointer data type is the the list of all the memory addresses in the computer. Therefore, the contents of a pointer must be a memory address. However, since the pointer data type doesn’t have a name like other simple data types, there must be one more layer to complete the relationship between the pointer and the data that it points to. That is, the pointer must be allocated, the data which the pointer points to (the pointee) must be allocated (otherwise, how is the computer to know what operations are allowed on the data?) and then the pointer must be directed to point to the memory location where the pointee is located. Luckily, this can be accomplished in one step:

// Create a pointer to a memory location large enough
// to store an integer value

int i;
int *intPtr;

// pointer is created, but is not pointing to a memory location yet

intPtr = i;

// intPtr is now pointing to the memory location where i resides

char *charPtr;
charPtr = (char *) malloc(sizeof(char)*100);

// charPtr points to a memory block that is the size of 100 characters

This relationship between the pointer and its pointee is the key characteristic that makes pointers a valuable programming tool across multiple implementations. Pointers are the foundation of complex data structures.

A major problem with pointers arises when a value is extracted from a pointer variable, that is, the pointer variable contains a memory address, not the value stored at the memory address … (I’d say, if we can’t ever get the value, this whole exercise is useless). Therefore, there must be a way of extracting the actual value from the pointer variable. The C programming language provides the “address of” or reference operator & (amprisand), and the * (asterisk) is used as the dereference or “value of” operator.

The concept of a pointer is to place a known marker at the beginning of a given storage space, and from there, calculate the end location based upon the type of the data placed there. Therefore, the purpose and duty of a single pointer can be greatly expanded by simply casting the pointer to any desired data type and then manually allocating the necessary amount of storage space. For example, the following C code creates a new pointer to the beginning of a character, and then allocates the amount of memory required by the input from the command line:

	char *str;
	str= (char*) malloc(sizeof(char)*strlen(argv[i]));

C and C++ are high level languages that assume that the programmer is in control of data, both in the form of variables, and user generated input. This means that there are very few safe-guards that protect from accidental (or on purpose) memory allocation. For example, consider the following code: (called char_array.c)

#include <stdlib.h>

int main(int argc, char *argv[]) {

        char str1[8];
        int buffer=0;

        if(argc < 2){
                printf("Usage: %s <string to allocate>\n", argv[0]);
                exit(1);
        }

        strcpy(str1, argv[1]);

        printf("str1 contains %s and buffer contains %d \n", str1, buffer);

}         

The above code creates a char array of size 8, which is allocated one byte for each element in the array, or 8 bytes. The program then takes input from the command line and outputs the value of str1 and buffer, which is an integer initialized to 0. The program clearly intends buffer to be 0 at the end of execution:

:~$ g++ -o char_array char_array.c
:~$ ./char_array 12345678
str1 contains 12345678 and buffer contains 0

Everything seems to be in order. The previous command first sets the value of the char array[] to 12345678, which when treated as individual chars, occupies only 8 bytes of memory. After that, the values of the variables str1 and buffer are output. As the programs logic is laid out, the value of buffer is 0… and remains so in this example. However, notice what happens if we give the program a value larger than 8 bytes:

:~$ ./char_array 123456789
str1 contains 12345678 and buffer contains 57

:~$ ./char_array 1234567890
str1 contains 12345678 and buffer contains 12345

This is an example of a buffer overflow. The input to str1 exceeded the memory that was allocated to it. Since C and C++ assume that the programmer knows what they are doing with their resources, no effort is made to prevent the program from writing beyond the highest array index (this is one reason that languages like Java have so many fans). So, where does it go? The next address in line….in this case buffer.

If primitive data types can be likened to building out, then records and structs may be likened to building up. Simple data types take care of some very broad problems in computing, and most computational problems can be solved by simply instantiating and initializing one piece of data at a time. However, this method is not practical in every situation, specifically when vast quantities are required. Given all the primitive data types, there would eventually come an need to store related data of different types in a complex and sophisticated manner.

A record (implemented as a struct in C programming) allows an entirely new data type to be created based upon other, “smaller”, data types. Further, this new complex data type is capable of holding other complex data types, which provides the unique capability of expanding to take on any size that’s assigned to it. This method of grouping data types allows for easier implementation and instantiation of objects. A struct consists of a list of fields (or members) and each of these fields may be of any data type. In this way, instantiating one struct can inform the processor to reserve enough memory (storage space) for the entire body of the struct.

A struct representing a major city might look like this:

struct city {

	int population;
	char *name;
	char *county;
	char *state;

}

Now a single call reserves a memory location big enough to store an integer and three character pointers. In this example, each city would be represented by a new instantiation of this data structure. For example, creating a structure for 3 cities:

// instantiate a copy of the data type for each city

struct city Cleveland;
struct city Boston;
struct city Ithaca;

A struct containing two different types of data, (this example contains both pointer and integer data) demonstrates the differences between the simple data types and the more complex types like pointers and structs. Notice that, since the field labeled population is an integer, the processor already knows how much space is required to store its value. Therefore, setting the value of the integer may be done post haste:

Cleveland.population = 444,313;
Boston.population = 590,763;
Ithaca.population = 28,829;

However, since each character pointer is simply a memory location, a known amount of storage space must be reserved before assigning values:

// Allocate enough memory to store 50 characters each

Cleveland.name  = (char) malloc(sizeof(char)*50);
Boston.name = (char) malloc(sizeof(char)*50);
Ithaca.name = (char) malloc(sizeof(char)*50);

Cleveland.county = (char) malloc(sizeof(char)*50);
Boston.county = (char) malloc(sizeof(char)*50);
Ithaca.county = (char) malloc(sizeof(char)*50);

// Allocate enough memory to store 2 characters each

Cleveland.state = (char) malloc(sizeof(char)*2);
Boston.state = (char) malloc(sizeof(char)*2);
Ithaca.state = (char) malloc(sizeof(char)*2);

Now that a storage space has been carved out, values may be assigned to each member:

// Assign values to each member field

Cleveland.county = “Cuyahoga”;
Cleveland.state = “OH”;

Boston.county = “Cuyahoga”;
Boston.state = “MA”;

Ithaca.county = “Tompkins”;
Ithaca.state = “NY”;

Members are accessed via extended dot notation, in the same manner that values are assigned:

// print out some info

printf(“ %s has %d people.”, Cleveland.name , Cleveland.population);
printf(“ %s has %d people.”, Boston.name , Boston.population);
printf(“ %s has %d people.”, Ithaca.name , Ithaca.population);

As previously mentioned, pointers do not contain a data value, instead they contain memory addresses. In order to get the data value, the pointer variable must be preceded with an asterisk (*). Similarly, a pointer to a struct points to the memory location where the struct is stored, and must first be dereferenced prior to accessing its data value. Once the struct has been dereferenced, its member values may be accessed via extended dot notation:

struct city* Buffalo;

// dereference the pointer to the struct
// access members via extended dot notation

(*Buffalo).population = 276059


// Allocate enough memory to store characters
(Buffalo).name  = (char) malloc(sizeof(char)*50);

// shorthand access using ->
Buffalo -> county = (char) malloc(sizeof(char)*50);
Buffalo -> state = (char) malloc(sizeof(char)*2);

Pointing to the memory location of a struct is clever, and greatly enhances a programmer’s ability create new data types. However, structs built in this manner are still limited to the contents of their members.

In contrast, consider a dynamic list with the capability of inserting values into, and removing values from the list at a given point. Each element in the list would have a data value (payload), and then each member could be stored in some type of an array, and removal and insertion could be handled using he array’s built in indexing mechanism. So, why not use arrays? Because arrays come with inherent limitations. For example, conventional C and C++ arrays cannot be lengthened. Overcoming this problem with pointers is easy.

Consider the definition of a “node” struct that includes a pointer to another instance of the struct:

struct node{

	int val;
	struct node *next;

};

typedef struct node Node;

// define a new “name” for the node for easier implementation
// instantiate new nodes with Node *start = (*Node) malloc(sizeof(*Node)

Defining a struct in this manner, provides each list element with a member which consists of a pointer to the location of the next element in the list. Further, since it is possible to dynamically allocate memory on the fly, this implementation may be extended to hold any number of elements. Notice that this “linked list” style implementation allows for a single variable name to encompass several structs. This presents idea of a head, that is, the identifier points to the beginning of the list. Also notice that the next pointer for the final element is set to NULL. This creates a checkpoint, noting the end of the list.

Node *start;

start = (*Node) malloc(sizeof(*Node)); // new node
start -> val = 10;

start -> next = (*Node) malloc(sizeof(*Node)); // allocate memory for the next element
start -> next -> val = 11; //second element in the list

start -> next -> next = (*Node) malloc(sizeof(*Node)); 
start -> next -> next -> val = 12; // third element in the list

// make the fourth element empty
start -> next -> next -> next = null;

The previous lines instantiate a new linked list with three elements. The variable start points to the beginning of the list, start → next points to the second element and start → next → next points to the third element. However, consider how values would be extracted from a list with 50 elements. Typing a line like start → next → next → next → … (47 more times) → val wouldn’t be a very efficient method, and further, it wouldn’t be a very good way to keep your new programming job.

An iteration structure is needed to traverse the list to get to the nth element. Further, since the variable name (the identifier) references the memory location at the beginning of the list, then re-pointing the identifier to the second element in the list effectively removes the first element from the list’s linkage. Therefore, iterating through the list requires two pointers, one for the head of the list, and one to iterate deeper into the list.

start = start -> next; // error

// oops! pointed start to the next element in the list
// first element is lost forever... not good, not good at all

Therefore, another temporary pointer is needed to iterate through the list, pointing at each consecutive element at the list is traversed:

int i;
*Node tmp;

tmp = start; // point tmp to the beginning of the list

for(i = 0; i < 2; i++){

	// loop to get the third element
	tmp = tmp -> next;

}

// prints 12

printf(“The 3rd element is %d”, tmp -> val);

Iterating through the list in this manner keeps the initial pointer (start) at the beginning of the list, while iterating the temporary pointer (tmp) to the third element.

While this example is limited to getting a predefined value from a predefined struct, this concept may be extended to dynamically create lists based upon user input, allowing a user to choose a selected value to return.

A new linked list may be created by adding elements to the end of the list as they are provided by a user or possibly from file input. The following example takes input from the user:

    Node *start, *tmp;

	int input = 0;

	start = tmp = NULL;

	do {
		printf("Enter a value (-1 to quit): ");
		scanf("%d", &input);

		if ((start == NULL) && (input != -1))
		{
			start = (Node *) malloc (sizeof(Node));
			tmp = start;
			tmp -> value = input;
			tmp -> next = NULL;
		}
		else if (input != -1)
		{
			tmp -> next = (Node *) malloc (sizeof(Node));
			tmp = tmp -> next;
			tmp -> value = input;
			tmp -> next = NULL;
		}
	} while (input != -1);

In the previous C code snippit, start still points to the memory location where the struct begins, however, new nodes have been appended to the end of the list. Since each struct contains a pointer to the next, a simple iteration from the beginning of the list will continually provide a pointer to the memory location of each subsequent element.

Once the list is built, the method for inserting values into a list differs slightly depending on the way the you turn your paradigm. Specifically, is the value to be inserted before or after a specified element.

Inserting a value into a linked list before a selected index involves iterating through the list to find the target node one spot before the selected index. Next, the target node’s (that is, the node prior to the selected index) next pointer is directed to the new node to be inserted, and the new node’s next pointer is directed to the node at the selected index. However, consider what happens if the user selects the first or zero-ith element in the list. Since the target node is one less than input, then choosing zero would, in theory, iterate to the position negative one. Choosing one will iterate to the zero-ith element. Neither of these outcomes is desired. Therefore, if the user selects zero then a new node is created, its next pointer directed to the element at the beginning of the list. The rest of the list stays the same. If the user chooses to insert before the second element in the list (that is, starting at zero, the element at “index” one) .

	Node *start, *tmp, *tmp2;

// ... create a list from start using previous method

	int i = 0, input = 0;

	tmp = start;
	
	printf("Select Node # to insert before: ");
	scanf("%d", &input);

	for (i = 0; i < (input - 1); i++){

		//position tmp before the selected index
		tmp = tmp -> next;

	}


	if (input == 1){

		i++;

	}


	printf("Enter value for new node: ");
	scanf("%d", &input);

	// Create new node
	tmp2 = (Node *) malloc (sizeof(Node));
	tmp2 -> value = input;


	if (i != 0){	// anything but the first

		tmp2 -> next = tmp -> next;
		tmp -> next = tmp2;

	}else{	// the first node
	
		tmp2 -> next = result;
		start = tmp2;
	}

Inserting a value after a selected index requires one more iteration to find the target node at the selected index, and therefore doesn’t require a check for input of one or zero.

Remove an item from a linked list by iterating a temporary pointer to the memory location prior to the target node, setting it’s ‘‘next’’ pointer to the pointer after it’s current next pointer (in other words, ‘’tmp → next → next’’). Next, free the memory allocated for the node:

Node *start, *tmp, *tmp2;

	int i = 0, input = 0;

	start = malloc(sizeof(Node));

    // .. add elements to the list

	tmp = start;

	printf("Select Node # to delete: ");
	scanf("%d", &input);

	for (i = 0; i < (input - 1); i++){
		tmp = tmp -> next;
	}

	if(input ==1){

		i++;

	}

	if (i != 0){	// anything but the first
	
		tmp2 = tmp -> next;
		tmp -> next = tmp2 -> next;

	}else{	// the first node
	
		tmp2 = start;
		start = start -> next;
	}

	tmp2 -> next = NULL;
	free(tmp2l);

Once the linked list concept has been fully explored, a new limitation may be discovered. Specifically, as a temporary pointer is iterated through a linked list, it is not possible to quickly locate the previous node. Because the linked list node only contains a member pointer to the next member, a program must create and iterate a new temporary pointer from the beginning of the list to find a member that is prior to an already existing temporary pointer. Therefore, computations could be made much faster by simply adding a pointer to each node’s predecessor. Luckily, there is only one small modification needed to our node to make all this possible.

struct node {
	int value;
	struct node *prev;
	struct node *next;
};
typedef struct node Node;

The addition of a pointer to the previous element allows the program to now start at the beginning of a list and iterate toward the end, or start at the end and iterate toward the beginning (more interestingly, start in the middle and go forward or backward).

Further, only small modifications are needed to make the previous insert algorithm work with doubly linked lists :

Node *start, *tmp;

	int input = 0;

	start = tmp = NULL;

	do {
		printf("Enter a value (-1 to quit): ");
		scanf("%d", &input);

		if ((start == NULL) && (input != -1)) {

			start = (Node *) malloc (sizeof(Node));
			tmp = start;
			tmp -> value = input;
			tmp -> next = NULL;
			tmp -> prev = START;

		} else if (input != -1) {

			tmp -> next = (Node *) malloc (sizeof(Node));
			tmp -> value = input;
			tmp -> next -> next = NULL;
			tmp -> next -> prev = tmp;

		}
	} while (input != -1);

The previous C code snippet creates subsequent nodes, linking each to their next and previous neighbors in the list. Additionally, the ‘’prev’’ pointer of the first element and the ‘‘next’’ pointer of the last element are set to NULL. This provides a checkpoint regardless of the direction the control loop is iterated. This means that given any point in the list, a temporary pointer may be iterated from the end to the beginning, checking for ‘’tmp → prev == NULL’’ or from the beginning to the end, checking for ‘‘tmp → next == NULL’’. Further, it becomes apparent that, in theory this iteration may be done with a single variable. No temporary pointer is really needed (depending on the care which is taken with the root pointer) as each node in the list contains a pointer to both its previous and next neighbors. This may give the programmer a sense of playing with fire.

Removing an element from a doubly linked list is only slightly different than dealing with singly linked lists. Once the target element is found, its previous neighbor’s ‘‘next’’ pointer is directed to its own ‘‘next’’ pointer (I.E. from the target: ‘‘prev → next = target → next’’), and its ‘‘next’’ neighbor’s ‘‘prev’’ pointer is directed to the target’s ‘‘prev’’ (I.E. ‘‘target → next → prev = target → prev’’).

target -> prev -> next = target -> next;
target -> next -> prev = target -> prev;

free(target);

The concept of stacks and queues are implemented in the same manner as a linked list. Each element in the list (I.E. each struct) contains a pointer to the next element in the list (each may also contain a ‘‘prev’’ pointer). However, the key difference between linked lists and stacks is the manner in which elements are added and removed. Linked lists provide an implementation that allows values to be added in the order specified by a user or arbitrary algorithm. In contrast, stacks and queues rely on list elements being added in specific positions.

Consider the concept of the inbox on a receptionist’s desk. The bin may start the day empty, and as new jobs are added to the receptionist’s list, a decision must be made as to the priority given to each task. In many cases, this is a decision that may be made via algorithm.

The receptionist may choose to accomplish tasks in the bin in the order that they are received. In that case, the first jobs in the bin would be the first jobs out of the bin. In practical terms this means that new jobs are placed on top the the pile, and the receptionist would choose the job at the bottom of the pile as the next in line, or next in the queue.

Inserting nodes into a queue requires iteration to the end of the list. Setting the end node’s next value to the newly created node.

	Node *start, *tmp;

// .. malloc start ... create first node

	tmp = start;
	
	while( tmp -> next != NULL){

		tmp = tmp -> next;

	}
	
	// tmp is now pointing to the end of the list

	tmp -> next = malloc(sizeof(Node));
		
	

In this regard, adding elements to the end of a stack can be made cheaper by adding a second node, and pointing it at the last element in the list.

Removing nodes from the list requires removing the ‘‘start’’ pointer, and pointing the start pointer to the next element in the list all at the same time:

	Node *start, *tmp;
//.. create the queue and fill it with values
	tmp = start;
	start = start -> next;
	tmp -> next = NULL;
	free(tmp)

In contrast to first in, first out, the receptionist may choose a new job directly from the top of the pile, or, let’s call it a stack. In this way, jobs that are added to the stack last are retrieved from the stack first. In other words, last in, first out.

In the most practical sense, stacks and queues differ from linked lists only in their precise control over adding new nodes to the list and removing nodes from the list. However, consider that the implementation must choose which end is up is up. For example, a stack can have items added to, and removed from it’s beginning. Likewise, a queue could be stocked from the front and dispensed from the back. The difficulty of implementation is changed depending on this interaction.

Stacks and queues are perfect for many implementations, but consider what happens if the data is allowed to dictate the manner in which it is stored? Traditional stacks and queues would fail because these two data structures are meant to store and retrieve elements based purely upon the order in which they were presented. Instead, a tree allows values to be stored in a list based upon their relationship to the rest of the elements within the list.

An example tree node might look like this:

struct tnode {
	int value;
	struct tnode *right;
	struct tnode *left;
};
typedef struct node TNode;
	

This type of relationship could be implemented in a way that is similar to using the next and prev doubly linked list. However, this would require inserting new nodes between existing nodes as values are added to the list. That could get a little hairy. The tree data structure instead contains member pointers labeled left and right. In this way, values added to the list may be placed in a way that is dependent upon their relationship to the root node.

In the number example, if a value is less than the root node’s value it is placed to the left. If the new value is greater, it is placed to the right. Further, iterations may be used to test the new value against each subsequent member in the list, moving right if greater, left if less. In the end, this type of traversal will land a new temporary pointer directly at its necessary insert position. Once the position is found, simply malloc the necessary storage space.

	
	TNode *root, *tmp;

// a root node with a value of 75000

	root = malloc(sizeof(TNode));
	root -> right = NULL;
	root -> left = NULL;
	root -> value = 75000;

while(tmp -> right != NULL && tmp -> left != NULL){

	if(v > tmp -> value){

                        if( tmp -> right != NULL){

                                //go right
                                tmp = tmp -> right;

                        }else{

                                //we're here
                                tmp = tmp -> right;

                        }

                }else{

                        if( tmp -> left != NULL){

                                //go left
                                tmp = tmp -> left;

                        }else{

                                //we're here
                                tmp = tmp -> left;

                        }

                }

        }

// tmp is pointing to the correct position
// set the new value

	if(v > tmp -> value){

		tmp -> right = malloc(sizeof(TNode));

	}else{

		tmp -> left = malloc(sizeof(TNode));
	}

Removing values is a little more complex:

	TNode *root, *tmp;

// ..insert values into the list

	tmp = root;

while(tmp -> right != NULL && tmp -> left != NULL){

	if(v > tmp -> value){

                        if( tmp -> right != NULL){

                                //go right
                                tmp = tmp -> right;

                        }else{

                                //we're here
                                tmp = tmp -> right;

                        }

                }else{

                        if( tmp -> left != NULL){

                                //go left
                                tmp = tmp -> left;

                        }else{

                                //we're here
                                tmp = tmp -> left;

                        }

                }

        }


//tmp is pointing to the target to be removed

        if(tmp -> left == NULL && tmp -> right == NULL){

	/*
		This is the case of the end of a tree branch
		check here to find if the parent’s value is greater
		or less than the value of the temporary pointer

		if true, iterate to the parent and set it’s left to NULL
		if false, iterate to the parent and set it’s right to NULL
	*/

        }else{


	/*

		this is the case of a value with one or more
		nodes left or right of it in the list

		if the parent node of tmp is greater than tmp -> value
		then iterate to the parent’s extreme left and set that
		left side node to tmp -> right and then tmp -> right to tmp -> left

		else iterate to the parents extreme right and set that left side 
		to tmp -> right and tmp -> right -> left to tmp -> left
	*/

        }

As you can see, iterating through the list is pretty much the same every time. Therefore, a simple search algorithm is born:

	tmp = root;

while(tmp -> right != NULL && tmp -> left != NULL){

	if(v > tmp -> value){

                        if( tmp -> right != NULL){

                                //go right
                                tmp = tmp -> right;

                        }else{

                                //we're here
                                tmp = tmp -> right;

                        }

                }else{

                        if( tmp -> left != NULL){

                                //go left
                                tmp = tmp -> left;

                        }else{

                                //we're here
                                tmp = tmp -> left;

                        }

                }

        }


//tmp is pointing to the target