Data Structures and Algorithms

Table of Contents:

1. Introduction

2. Abstract Data Types (ADTs)

3. Data structures
3.1 Arrays
3.2 Stacks
3.3 Queues
3.4 Lists and linked lists
3.5 Trees
3.6 Hash tables

4. Algorithms
4.1 Algorithms analysis
4.2 Algorithms performance management
4.3 Searching algorithms
4.4 Sorting algorithms
4.5 Sorting algorithms examples in java

5. Recursion

6. Conclusion

Bibliography

1. Introduction

Data are intended to the substantive facts sets and concepts, which we see and deal with it in our daily lives. Data and facts are the things that we do not feel there is a relation or knowledge, directly or indirectly with them. It is a set of values ​​that reflect the entities or events expressed by, for example, book, car, university, institution, etc., are all independent entities and facts. Conversely, there are many facts that are difficult to cover and know all their fractions because of the multiplicity of their data and their characteristics, which leading to organize them in sets, arrays, strings, records, files and other patterns and so-called data structure. Data structure refers to a set of data elements that have a special organization, and also special style for accessing the individual elements, either through the process of storing or retrieving values. On the other hand, the data structure means the different ways and methods through which the logical perception of the data is interpreted as seen by the computer programmer who cares about the different ways to organize the data and developing algorithms to manipulate this data. . According to Lafore "A data structure is an arrangement of data in a computer’s memory (or sometimes on a disk). Data structures include arrays, linked lists, stacks, binary trees, and hash tables, among others". The word structure is used in many areas to describe the large entities that have been built from small blocks in recursive way, and data structure is the logical block caused by repetitive data elements according to specific order and relations. Data structures is considered as the intermediate stage between the files on the storage media and the application programs

The algorithm is a set of well-defined rules to find the best solution to a problem in a limited number of steps, and to be so, the set of rules must be clear and have a distinct breaking point. Algorithms are the procedures or formulas to solve a problem and evolved with time closely linked with the programming of computers devices. Algorithms can be expressed in any language of natural languages ​​such as Arabic, English, Spanish or French and using programming languages ​​such as JAVA, C, Pascal, Delphi and C++ as examples. Algorithms were invented by an Arab mathematician named Muhammad Bin Musa Al-Khwarizmi and the word "algorithm" is referred to his name. Al-Khwarizmi lived as part of the royal court in Baghdad during the year 780 to 847, and he used algorithms in solving mathematical problems. The most of the computer applications, with the exception of some artificial intelligence ones consist of algorithms. The creation of elegant, compact, smart and simple algorithms that require fewer steps possible is one of the main challenges in computer programming. Data structures are objects generated to store data and algorithms are a set of instructions to perform specific task by using the data structures. As computer programmers we think algorithms are the lifeblood of our work and it is the nerve that gives the life to any computer program. In brief, we can define the data structures and algorithms in one statement as Sally and Kenneth says " the structural organization is known as a data structure, and the ways in which the operations are carried out are known as algorithms", (2008).

The objectives of this paper is concentrated in introducing the basics of data structures such as arrays, linked lists, trees, stacks, queues, and hash tables. It also incorporates data structures into the applications associated to them and determine which algorithm or data structure to use in different scenarios. Through this paper we will discuss and implement various searching and sorting algorithms such as linear search and binary search using java programming language.

2. Abstract Data Types (ADTs)

The organization of information is one the main issues for every software developer. The decision for software development is affected by conceptual and structural fundamentals. Conceptualizing information means the way we think for implementing the best and easy solution. The process of conceptualizing information is known as Abstract Data Type (ADT). Abstraction is the way for creating the model that defines the problem. Abstract data type ADT is the mathematical pattern comprises a structure for storing data and processes that can be performed on that data. ADT means the creation of a good definition for an entity to be properly handled. According to http://en.wikipedia.org ADT "is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics" [8]. ADT is characterized by a type and sets of operations called interface, and the interface is the mechanism for accessing the data structures. Common ADT includes sets, trees, stacks, queues and heaps. In computer programming environment, ADT is referred to a set of data specified by the programmer in terms of information that can be contained and processes that can be done with it. The data type is said to be "abstract" because of the sense that it is independent of various applications. Setting ADT is the first step in application design process because it provides the definition of application interface. In computer programming data types are defined through variables which contain numerical data when dealing with numbers, symbolic data when dealing with characters and words and logical data when dealing with data that bearing right or wrong. All of these data types are classified as simple data types. For example, int, byte, float, long, short, double, Boolean and char are the simplest data types used in java programming language. The simple data types are used to describe entities in records and tables which are called structured data types.

According to the above can be drawn benefit of using compositions abstraction that the programmer who is trying to use a combination of data abstraction this in the application software large and complex is the focus of his thought in the matter, which tries to programming solved without effort is in the details of the structure of the data, which makes the program more effective and less complicated and therefore easy in terms of writing logic, understanding and modification

3. Data structures

The way for structurally organizing the data in memory to achieve the high efficiency for carrying out operation on information is called data structure. Data structure is the physical implementation of ADT. For example, the data structure for customer entity may contains the customer ID, name, address, birth date, balance etc. Data structures are divided into several types each of which correspond to a special method in computer program design and electronic processing and can be classified as the following three types: linear data structures, tree data structures and graphs data structures.

- The linear data structure is dealing with stacking data within the memory on a single line and these include: arrays, string, records, tables, lists, stack and queues
- The tree data structure is concerned with the hierarchical data structures like the tree representation of data set for a large family or an organizational structure of a company
- Graphics data structure is concerned with graphics and in other words, if any element of a lower level in the tree data structure linked with more than one element at a higher level is referred to by name data graphics structures.

3.1 Arrays

Arrays are defined as a set of similar elements, and these elements can be a numeric value, symbolic value, combinations of numeric value and string, or a set of records, and they are classified in terms of the dimensions into two classes: one dimensional array and multiple dimensional array.

For example, if the student scores in database systems, mathematics, operating systems, software engineering, Delphi language and data structure courses are 80, 75, 68, 90, 76, and 83 respectively, we can create an array of six elements to store these values as in Fig (1). The data for student scores are stored in array of six elements and their corresponding addresses started from 0 to 5. The values can be inserted or retrieved from arrays according to these addresses and in our example here if we named this array by studScores then we denote any of the array elements by the array name followed by the respective index such as studScores(1) to refer to mathematics and studScores(5) to refer to data structures course and so on. That means the studScores array is represented by studScores[n] where n is the index that referencing the array elements.

illustration not visible in this excerpt

Fig (1) One dimensional array

Using java programming language we can define an array by issuing the following statement:

int[ ] arr; // where arr is a reference to an array of integers

The array can be defined and created physically on the computer memory when we issue the following statement:

int[ ] arr = new int[20]; // initialize an array of 20 elements

and we can assign the value 200 to the third element and 100 to the last element of the array (arr) by using the following statement:

arr[2] = 200; // gives the array element no. 3 of index 2 the value 200

arr[19] = 100; // gives the array element no. 20 of index 19 the value 100

In our previous example we discussed how to represent the scores in six courses for one student in one-dimensional array, and if we decide to store the scores of database systems, mathematics, operating systems and software engineering for five students as shown in Table (1), we will need a tow-dimensional array to store their data.

illustration not visible in this excerpt

Table (1) Students scores

The array will consist of four columns and five rows, and if we named it stScores, then it will be referenced by sts[m, n], where m is the index of rows and n is the index of columns and it is represented in memory as shown in Table (2).

illustration not visible in this excerpt

Table (2) The two dimensional array structure

The three-dimensional array is considered as a repetition of the two-dimensional array in more than one level and we can reference its items by adding the index of the level to be sts[m,n,k]. We can define the two-dimensional array above in java and assigning them values like that in the above example we can issue the following statements:

int[ ] [ ] sts = new int[5] [4]; // initialize an array of 5 rows and 4 columns .

sts[5] [4] = 82; // gives element at row 5 column 4 score 82

sts[1] [1] = 90; // gives element at row 1 column 1 score 90

The main Characteristics of arrays can be summarized in the following points:

- It is found in all programming languages
- It has the ability to deal with them directly and easily at any array position
- It has contiguous positions making it easier to access them.

The disadvantages of arrays can be summarized as follows:

- Consist of a fixed size and is determined at the beginning when they are defined
- Contain only one type of data elements.

3.2 Stacks

Stacks are more abstract data structure than arrays and any other data storage and their implementation mechanisms are not visible to users. Stack is a special container for temporarily storing data and accessing it through a specific mechanism. As Goodrich and Tamassia defined its purpose "A stack is a collection of objects that are inserted and removed according to the last-in first-out (LIFO) principle", (2006). Stacks allow accessing only one item at a time, the last item inserted is accessed first, or in other words the Last-In-First-Out (LIFO) mechanism and the item next to the last item can be accessed when removing the last item and so on. The stack is actually like the pistol, where the last bullet is fired first and when it is released, the bullet which followed become ready to be shot the next, and so on until we fired at last the first bullet inserted i.e. the insertion and deletion is doing at the highest by using pushing and popping functions respectively and the top pointer i.e. doing the top one first as shown in Fig (2). Stacks are used for temporary storage for addresses and data while the program is running.

illustration not visible in this excerpt

Fig (2) Stacks structures

The most benefits of using stacks are represented in finding the values ​​of arithmetic expressions, using for the recursion purposes and calling of sub-programs. The pointer top holds the index value -1 when the stack is empty and this value is incremented by one whenever a new value is inserted in the stack until filled. During the out process the stack pointer value is decremented by one until its value becomes -1 which indicate that the stack is empty.

For example, suppose that we have the values a, b and c stored in stack and we need to store a new value d, and after that we decide to pull a value from the stack, it will be the last value entered The methods used for representing stack elements in memory with putting into account the ways for storing and retrieving values can be classified as in the two following points:

- Interconnected ring representation of stack elements in memory as a list
- Compact representation of stack elements in memory in the form as a one-dimensional array.

In java programming language we define the stack in the same way that we define the one-dimensional array as in the following statement:

long[ ] stackRef; // where stackRef is a reference to stack long integer .

stackRef = new long [10]; // initialize the stack of 10 elements

3.3 Queues

The queue Is a type of linear data structures and it resembles the stack in term of temporary storage of data while different from the organization that applied to input and output data while differ in the operation of input and output mechanism, the queue uses the First-In-First-Out FIFO mechanism. As Harris and Ross defined it, "a queue is a collection of objects that are inserted and removed according to the first-in first-out (FIFO) principle".

[...]