Data Structures and Algorithms

Data Structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers. Data structures are used in almost every program or software system. Specific data structures are essential ingredients of many efficient algorithms, and make possible the management of huge amounts of data, such as large databases and internet indexing services. Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design.

Principles

Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by an address — a bit string that can be itself stored in memory and manipulated by the program. Thus the record and array data structures are based on computing the addresses of data items with arithmetic operations; while the linked data structures are based on storing addresses of data items within the structure itself. Many data structures use both principles, sometimes combined in non-trivial ways (as in XOR linking) The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure. The efficiency of a data structure cannot be analyzed separately from those operations. This observation motivates the theoretical concept of an abstract data type, a data structure that is defined indirectly by the operations that may be performed on it, and the mathematical properties of those operations (including their space and time cost).

Common data structures:

Common data structures include: array, linked list, hash-table, heap, B-tree, red-black tree, trie.

Language support

Most Assembly languages and some low-level languages, such as BCPL, generally lack support for data structures. Many high-level programming languages, and some higher-level assembly languages, such as MASM, on the other hand, have special syntax or other built-in support for certain data structures, such as vectors (one-dimensional arrays) in the C language, multi-dimensional arrays in Pascal, linked lists in Common Lisp, and hash tables in Java and in Python. Many languages also provide basic facilities such as references and the definition record data types, that programmers can use to build arbitrarily complex structures. Most programming languages feature some sort of library mechanism that allows data structure implementations to be reused by different programs. Modern languages usually come with standard libraries that implement the most common data structures. Examples are the C++ Standard Template Library, the Java Collections Framework, and Microsoft's .NET Framework.

Modern languages also generally support modular programming, the separation between the interface of a library module and its implementation. Some provide opaque data types that allow clients to hide implementation details. Object-oriented programming languages, such as C++, Java and .NET Framework use classes for this purpose. With the advent of multi-core processors, many known data structures have concurrent versions that allow multiple computing threads to access the data structure simultaneously.

Different Types of Data Structures:

The data structures can be classified into two different types namely

( i ) Primitive data structures and ( ii ) Non - primitive data structures

Primitive data structures

The data structure which can be directly operated are called primitive data structures. The integer, float, character etc. are some of the primitive data structures. Operations like creation, deletion, selection and updation can be carried out on primitive data structures.

Non - primitive data structures

The data structures which are not primitive are called non-primitive data structures which means these are data structures that cannot be manipulated directly. Non-primitive data structures can be again classified into two different types namely (i) Linear data structure and (ii) Non-linear data structure.

A linear data structure is the one which establishes the relationship of adjacency between the elements which means all the elements are stored linearly or sequentially. Some examples of linear data structures are arrays, linked list, stacks and queues.

Any data structure which establishes the relationship their tha the adjacency relationship are called as non-linear data structure. Some examples of non-linear data structures are trees and graphs.

Conclusion on Different Types of Data Structure:

Data structures provide a function that can be used to retrieve the individual data elements. It enables to solve the relationships between the data elements that are relevant to the solution of the problem. The data structures describes the logical and physical relationship between the data items and provides a mode of access of each element in the data structure. It helps in selection of an appropriate mathematical model to solve a problem.

Classification of Linear Data Structures:

Linear data structures can be classified as arrays, lists and files.

An array is an ordered set which consists of a fixed number of objects. No deletion or insertion operations are performed on arrays. But elements can be changed to a value which represents an element to be ignored. Generally an element is set to zero in an array to delete it .

A list is an ordered set consisting of a variable number of elements to which insertions and deletions can be made. Operations performed on lists include those which are performed on arrays. In addition to that, the size of a list may be changed by updating. The insertion and deletion of elements in a list is specified by its position.

Each element in a list is composed of one or more fields. A field can be considered to be the smallest piece of information. The other important operations performed on lists are listed as follows :

( i ) copying a list

(ii) Finding the numbers of elements in a list

( iii ) Split a list into a number of lists

( iv ) Combine two or more lists to form another list

( v ) Searching an element in a list

( v i ) Sorting the list in a predetermined order

A file is a large list that is stored in the external memory of a computer. A file may be used for storing records that are accessed infrequently and must be stored between various invocations of a program.

Linear Data Structure Conclusion:

Linear data structures are simple structures that are computationally simple because of its linear addressing function. An addressing function for a data structure is a function which maps the ith element of the data structure with n elements onto an integer between one and n. Addressing function is an operation associated with referencing of any element by knowing its position in the structure.Data structure plays a major role in problem solving.

Sample Problem for Graphs Data Structure:

Graphs data structure problem 1:

Evaluate the given nodes and find out the path between each nodes in given diagram.

Solution:

We are going to find out the shortest path between the given nodes.

Step 1:

Let as start with B_a, it connected with two nodes. They are node B_b and node B_e.

Step 2:

Let as start with node B_b, it connected with four nodes. They are node Ba, node B_c, node B_d and node B_e.

Step 3:

Let as start with node B_c, it connected with two nodes. They are node B_b and node B_d.

Step 4:

Let as start with node B_d, it connected with three nodes. They are node B_b, node B_c, and node B_e.

Step 5:

Let as start with node B_e, it connected with three nodes. They are node B_a, node B_b, and node B_d.

In the next we draw a data structure graph for the above nodes, we get

Graphs Data Structure Problem 2:

Evaluate the given nodes and find out the path between each nodes in given diagram.

Solution:

We are going to find out the shortest path between the given nodes.

Step 1:

Let as start with node V_a, it connected with two nodes. They are node V_b and node V_e.

Step 2:

Let as start with node V_b, it connected with four nodes. They are node V_a, node V_c, node V_d and node V_e.

Step 3:

Let as start with node V_c, it connected with two nodes. They are node V_b and node V_d.

Step 4:

Let as start with node V_d, it connected with three nodes. They are node V_b, node V_c, and node V_e.

Step 5:

Let as start with node V_e, it connected with three nodes. They are node V_a, node V_b, and node V_d.

In the next we draw a data structure graph for the above nodes, we get

Our tutors start working only after the payment is made, to ensure that we are doing work only for serious clients and also our solution meets the required standard.