Non-Linear Data Structures :: Binary Tree

The first non-linear data structure and most important to understand is the binary search tree. This structure consists of a main node which is called the root and sub nodes which are called children. Each parent node has children nodes starting at the root and going to the bottom of the tree. Binary Search trees work by having a left child and a right child pointer. This does not mean that every parent node will have 2 children. The number of children depend on the values of each node that are inserted into the tree. The first value that is inserted into the tree is the root. From the root each value inserted must be checked against it; if the value is greater than the root then it would become the right child if it were less than the root it would become the left child. This goes on through the entire tree. NO left child will ever be greater than or equal to its parent or sibling.

The following tree was created by inserting these values in order. (10,15,13,24,4,7,9,5,2)

Linear Data Structures :: Creating Queues

The concept of a queue is what every small child learns when they go to school. Wait your turn. The queue is used to create a FIFO list also known as first in first out. A queue is similar to a stack in that the top of the stack is like the front of the queue. However, the stack is created using Push at the Top while the queue is created by inserting the new node at the back of the queue.

STACK
The following image is an example of a stack. It shows the TOP of the stack equal to 3. The image demonstrates how the stack would push new nodes. Each new node would push down on the next creating what would look like a tower of blocks. The problem with a stack is that if data at the bottom of the stack needs to be popped off the stack it has to wait for everything else to go first. This is a problem in programs that create stacks of processes. Starvation is the term used for a process that does not get a chance to execute.


QUEUE
The image of the queue can be viewed as a line of people waiting at a bank. The first person in line would get to go first. After that person completes their transaction they can leave the queue and the next person can be in front of the line. A queue is a good way to ensure that everyone gets treated equally and prevents starvation from occuring.

Linear Data Structures :: Understanding Stacks

The concept of a stack is easy to understand. An example of a stack in the real world would be a stack of books or stack of papers etc. The idea of a stack in data structures is identical. There is a top and everything else is below the top. Creating a stack using a linked list is a good implementation because it allows for a stack of any size as long as resources such as memory permit. The main ideas of a stack are Top, Push and Pop. Top references the top of the stack. This is implemented using a pointer that will always be at the top of the stack. Push is refering to adding and item onto the stack. After each Push is completed the newest item added would then become the Top. Pop is used as a deletion method just as Push is used as an insertion. After each Pop is called the Top is removed from the list and the next node in that list becomes the new Top.

This code example shows the push and pop methonds.

Linear Data Structures :: Deleting from a Linked List

Since the previous post discussed inserting a node into a linked list it is necessary to also discuss the deletion of a node from the list. There are multiple cases that need to be taken into consideration. Removing a node from the beginning, end, and inbetween. The steps of deleting form the list consist of first finding the node, next removing the node and finally repairing the link between the list by linking the node previous to the deleted node and the node immediatly following the deleted node.

The following is an example of a linked list. Each square is a node with a structure of a data field and a next. In order to delete the second node we would traverse through the list until the specific data is found. The links must be changed in order to maintain the proper structure as was mentioned before. The first and third square would then be linked.

BEFORE DELETION

AFTER DELETION

Deleting from the beginning or end is similar to what was previously shown. Deleting from the beginning is nothing more than setting the initial pointer to another location. Removal from the end of the list is similar in that we change only one pointer. The previous node must be set to be the end of the list by setting next to NULL.

Deleting and Inserting are not the only functions of linked lists. Searching and Sorting can also be used, often within deletion and insertion algorithims.

Linear Data Structures :: Linked List

Usually the first data structure that is taught is the linked list. This is because it is simple and easy to implement. In order to create a linked list it is necessary to understand pointers. (The Pointers lesson is located in the archive) A linked list can be as large or small as the programmer wants it to be; of course memory size has to be taken into consideration. A linked list is individual nodes chained together by pointers. Each node can contain any number of fields of information depending on the structure. The following is an example of defining the structure of a linked list.



Adding a node to a list is easiest to do at the end of the list. Creating the new node can be done by using the following example.


This creates a new node and sets the values of each field in the node equal to a value that would be input from the terminal or from file. Traversing the list and deleting a node from the linked list is more difficult and will be discussed in later posts.

Introduction to Programming :: Pointers

Reference Operator

Pointers are exactly what the name suggests. They point at something else. The first topic of pointers that is necessary to understand is the reference operator. A reference operator points at a location in memory rather than the actual value stored within that location. Imagine a piece of memory (A) at location 1000 for example is holding a value of 50.

Input
A = 50;
B = A;
C = &A;

Output
B=50
C=1000

B is the value of A and C is the location of A.

Dereference Operator

The following dereference example consists of (A) once again at location 1000 with a stored value of 50.

Input
A= 1000(memory location) [50 is stored here]
B= *A

Output
B= Value of the location A is equivalent to. (50)

Introduction to Programming :: Input from File

The following code is an example of opening an input file and printing to the screen. Using input and output files can improve functionality of a user’s code by allowing for appending and truncating of files. Input files are often useful in programs that are not run by a user but rather predetermined information that needs to be accessed quickly. First use the #include statements and followed by using namespace std; .
Inside the main function declare a string and ifstream. In this if-else statement the file is checked, IF it is open a while loop executes. while(! InputFile.eof()) translates to while not end of input file get information from file and print to screen.