A Brief Introduction to Data Structures

[Psycho_Coder]

A Brief Introduction to Data Structures

Hello All  ,

Readers Note:-

• In this part don't expect that this is the limit of data structures as the things I will mention here are the most basic elements
• My further tutorials on Data structure,if any, they will assume that you are well versed with C or C++ or Basic Java or at least know some programming, though the codes and explanation will be java based, but if you have a problem then post here.
• This part will be a theoretical one.
• Data Structures and algorithm's are two different aspects. So, don't think I will be teaching algorithms (To be true I am still not very proficient with principles of algorithm I need 5 more months to become able to teach others.)
• Lastly and most important point do read till the end of this tutorial.

Tutorial Objectives

• What are Data Structures ?
• Abstract Data type (ADT).
• Classification of Data Structures.
• Basic Operations on Data Structures.
• Relation between Data Structures and Algorithms
• Basic Data Structures :- Arrays, Stack, Queue, Lists, Trees and HashTable
• Application of Data Structures
• Conclusion.
• Recommended Reading.

Let's begin


What are Data Structures ?

Perhaps this the most important question in this particular tutorial. So let us define data structures.

A Data Structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. The data can be more than one variable. They also contain algorithms to process the data stored.

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. 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. A data structure may be defined indirectly by the operations that may be performed on it, and the mathematical properties of those operations (including space and time complexity.)

Abstract Data Type (ADT)

An abstract data type is a data type that satisfies two conditions:-

• The representation, or definition, of the type and the operations are contained in a single syntactic unit.
• The representation of objects of the type is hidden from the program units that use the type, so only direct operations possible on those objects are those provided in the type’s definition.

Another Definition :-

An abstract datatype is an encapsulation mechanism. In general it is composed of several components:-

• A data structure or structures (often called the sorts)
• A set of operations (called the methods or operations).
• A precise description of the types of the methods (called a signature).
• A precise set of rules about how it behaves (called the abstract specification or the axiomatic description).
• An implementation hidden from the programmer who uses the data type.

Example of an ADT (I assume that you know what array means)

Code: [Select]

Array ADT

create(A,N)                   :     creates an arrayAwith storage forNitems;
bool isEmpty()                : - Retrurns true if array is empty
bool isFull()                    : - Retrurns true if array is full
int length()                    : - Returns the length of the array
void add(int item,int pos) :– Adds the element at the given position
void del(int item)            : - Deletes the given item from the array.
void display()                 : - Prints the elements of array.

Note: Stack , queue, Lists etc are all examples of ADT.

Classification of Data Structures

Data Structures are normally divided into two broad categories :-

Primitive Data Structures

The integers, reals, logical data, character data, pointer and reference are primitive data structures. Data structures that normally are directly operated upon by machine-level instructions are known as primitive data structures.

Non-primitive Data Structures

These are more complex data structures. These data structures are derived from the primitive data structures. They stress on formation of sets of homogeneous and heterogeneous data elements.

Other classifications :-

Homogeneous and Heterogeneous Data Structures

Homogeneous data structure

Homogeneous data structures are those data structures that contain only similar type of data e.g. like a data structure containing only integral values or float values. The simplest example of such type of data structures is an Array.

Heterogeneous Data structure

Heterogeneous Data Structures are those data structures that contains a variety or dissimilar type of data, for e.g. a data structure that can contain various data of different data types like integer, float and character. The examples of such data structures include structures, class etc.

 
Static and Dynamic Data Structures

Static data structure

Static data structures are those data structures to which the memory is  assigned at the compile time, means the size of such data structures has to be predefined in the program and their memory can be increased or decreased during the execution. The simplest example of static data structure is an array.

Dynamic data structure

Dynamic Data Structures are those data structures to which memory  is assigned at the runtime or execution time and hence their size can be increased or decreased dynamically as per requirement of the program. The example of such data structures include class, linked lists etc.

Linear and Non-Linear Data Structures

Linear data structure

In linear data structures the data is kept in the sequential manner which means that the previous data has knowledge of next data or we can say that the data is interrelated. The example such data structures include arrays, linked lists etc.

Non-linear data-structure

Non-linear data structures does not maintain any kind of relationship among the data. The data is stored in non-sequential manner and examples of these types of data structures includes graphs, trees etc.


Basic Operations on Data Structure

Traversing : Accessing each record exactly once so that certain items in the record may be processed.(This accessing or processing is sometimes called 'visiting" the records.)

Searching : Finding the location of the record with a given key value, or finding the locations of all records, which satisfy one or more conditions.

Sorting : Arranging the data in some logical order.

Inserting : Adding new records to the structure.

Deleting : Removing a record from the structure.

Merging : Combining the data of two different sorted file into a single sorted file.

Sometimes two or more data structure of operations may be used to create another operation.


Relation between Data Structures and Algorithms

An algorithm in data structure are step-by-step instructions that a computer can read. It is used for programming software and applications based on calculations.

Algorithms and Data Structures are tightly wound together. Algorithm depends on data structures, if you change either of them, complexity will change considerably. They are not same, but are definitely two sides of the same coin. Selecting a good Data Structure is itself a path towards better algorithm.


Basic Data Structures :- Arrays, Stack, Queue, Lists, Trees and Graph.

Arrays

Arrays are a very simple data structure, and may be thought of as a list of a fixed length. Arrays are nice because of their simplicity, and are well suited for situations where the number of data items is known (or can be programmatically determined). Suppose you need a piece of code to calculate the average of several numbers. An array is a perfect data structure to hold the individual values, since they have no specific order, and the required computations do not require any special handling other than to iterate through all of the values. The other big strength of arrays is that they can be accessed randomly, by index. For instance, if you have an array containing a list of names of students seated in a classroom, where each seat is numbered 1 through n, then studentName(i) is a trivial way to read or store the name of the student in seat i.

An array might also be thought of as a pre-bound pad of paper. It has a fixed number of pages, each page holds information, and is in a predefined location that never changes.

Linked Lists

A linked list is a data structure that can hold an arbitrary number of data items, and can easily change size to add or remove items. A linked list, at its simplest, is a pointer to a data node. Each data node is then composed of data (possibly a record with several data values), and a pointer to the next node. At the end of the list, the pointer is set to null.

By nature of its design, a linked list is great for storing data when the number of items is either unknown, or subject to change. However, it provides no way to access an arbitrary item from the list, short of starting at the beginning and traversing through every node until you reach the one you want.

Stack

Stacks are, in a sense, the opposite of queues, in that they are described as "last in, first out". The classic example is the pile of plates at the local buffet. The workers can continue to add clean plates to the stack indefinitely, but every time, a visitor will remove from the stack the top plate, which is the last one that was added.

While it may seem that stacks are rarely implemented explicitly, a solid understanding of how they work, and how they are used implicitly, is worthwhile education. Those who have been programming for a while are intimately familiar with the way the stack is used every time a subroutine is called from within a program. Any parameters, and usually any local variables, are allocated out of space on the stack. Then, after the subroutine has finished, the local variables are removed, and the return address is "popped" from the stack, so that program execution can continue where it left off before calling the subroutine.

An understanding of what this implies becomes more important as functions call other functions, which in turn call other functions. Each function call increases the "nesting level" (the depth of function calls, if you will) of the execution, and uses increasingly more space on the stack. Of paramount importance is the case of a recursive function. When a recursive function continually calls itself, stack space is quickly used as the depth of recursion increases.

Queue

A queue is a data structure that is best described as "first in, first out". A real world example of a queue is people waiting in line at the bank. As each person enters the bank, he or she is "enqueued" at the back of the line. When a teller becomes available, they are "dequeued" at the front of the line.

Perhaps the most common use of a queue is to implement a Breadth First Search (BFS). BFS means to first explore all states that can be reached in one step, then all states that can be reached in two steps, etc. A queue assists in implementing this solution because it stores a list of all state spaces that have been visited.

A common type of problem might be the shortest path through a maze. Starting with the point of origin, determine all possible locations that can be reached in a single step, and add them to the queue. Then, dequeue a position, and find all locations that can be reached in one more step, and enqueue those new positions. Continue this process until either a path is found, or the queue is empty (in which case there is no path). Whenever a "shortest path" or "least number of moves" is requested, there is a good chance that a BFS, using a queue, will lead to a successful solution.

Tree

Trees are a data structure consisting of one or more data nodes. The first node is called the "root", and each node has zero or more "child nodes". The maximum number of children of a single node, and the maximum depth of children are limited in some cases by the exact type of data represented by the tree.

One of the most common examples of a tree is an XML document. The top-level document element is the root node, and each tag found within that is a child. Each of those tags may have children, and so on. At each node, the type of tag, and any attributes, constitutes the data for that node. In such a tree, the hierarchy and order of the nodes is well defined, and an important part of the data itself. Another good example of a tree is a written outline. The entire outline itself is a root node containing each of the top-level bullet points, each of which may contain one or more sub-bullets, and so on. The file storage system on most disks is also a tree structure.

HashTable

Hash tables are a unique data structure, and are typically used to implement a "dictionary" interface, whereby a set of keys each has an associated value. The key is used as an index to locate the associated values. This is not unlike a classical dictionary, where someone can find a definition (value) of a given word (key).

Unfortunately, not every type of data is quite as easy to sort as a simple dictionary word, and this is where the "hash" comes into play. Hashing is the process of generating a key value (in this case, typically a 32 or 64 bit integer) from a piece of data. This hash value then becomes a basis for organizing and sorting the data. The hash value might be the first n bits of data, the last n bits of data, a modulus of the value, or in some cases, a more complicated function. Using the hash value, different "hash buckets" can be set up to store data. If the hash values are distributed evenly (which is the case for an ideal hash algorithm), then the buckets will tend to fill up evenly, and in many cases, most buckets will have no more than one or only a few objects in them. This makes the search even faster.

A hash bucket containing more than one value is known as a "collision". The exact nature of collision handling is implementation specific, and is crucial to the performance of the hash table. One of the simplest methods is to implement a structure like a linked list at the hash bucket level, so that elements with the same hash value can be chained together at the proper location. Other, more complicated schemes may involve utilizing adjacent, unused locations in the table, or re-hashing the hash value to obtain a new value. As always, there are good and bad performance considerations (regarding time, size, and complexity) with any approach.


Most standard libraries, such the Java API, and the .NET framework, provide a Stack, Queue, Lists, HashTables class that provides the various data structure operations. Details on how to use the API will be discussed later.


Applications of Data Structure


Every application uses Data structure but it is upto how you can use data structure to create more efficient programs and applications. To name some are :-

• Compiler Design,
• Network flow model
• Operating System,
• Database Management System,
• Statistical analysis package,
• Numerical Analysis,
• Graphics,
• Artificial Intelligence,
• Simulation

Conclusion

To conclude I would say that data structures have a enormous application in the field of computing and it has touched us in every manner. I would recommend you to study data structure in very very detail if you really want to be a good and efficient programmer. If you are interested  then I would ask you  to buy the books I have referred. If you face any problem then I am always there for all HCer's :happy:


Recommended Reading

1. Art of Computer Programming, Volume 1: Fundamental Algorithms by Donald E. Knuth

2. Data Structures and Algorithm Analysis in C++, by Mark Allen Weiss

3. Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching by Robert Sedgewick



References Taken

1. My Text Book (Data Structures by Lipshutz and another one by Baluja)
2. Wikipedia.
3. http://www.topcoder.com/

Thank You for reading my tutorial and I hope that you enjoyed it as much as you do. To be true I am not willing to call this as a tutorial even because you know only 0.000001% of the beauty of data structures and if you find it useful and feel interest then I will post further papers on Data Structures and covering each and every aspect in detail and in very depth. But only upon request.


Thank you,
Sincerely,
Psycho_Coder.

[proxx]

Very nice write-up , you are very well capable of making a clean, short yet informative description.
Not a lot of new things to me but its always good to recap things.
Sure hope you like cookies!

[Psycho_Coder]

Very nice write-up , you are very well capable of making a clean, short yet informative description.
Not a lot of new things to me but its always good to recap things.
Sure hope you like cookies!

Thank you. Yes I do like cookies but I don't know but my 3 cookies were stolen , however they don't matter much

[parad0x]

Awesome dude, you are really a Psycho coder.


You like cookies?
Here is yours, if you don't like them, return it to me.