Basic Concept of Data Structure

Data structure

Data structures is the specialized format to organize and manipulate data. A data structure dictate way data is acquire, and form in your computer.  The goal is to use and access data on efficient manner. There are type of data structure for example array, tree, hash, and graph. Different kind of application use specific data structure to achieve efficient operation.

The complexity and the use of data structure describe on big O notation where O(1) indicate a fast algorithm that will always execute in the same linear time. Contrary to O(N!) where execution time will be very slow. 

File structure and Storage structure. Storage structure refer to memory storage area of the computer. Fastest computer storage is register but it has limited capacity.

File structure refer to the way files are organize on computer.  The structure was chosen and organized for easy operations.

images images

Type of Data Structure

Type of data structures mainly categorize as primitive such as boolean, char, integer, string and Non primitive such as array, list, tree and so on. Non primitive data type derived from primitive type. All these data structures enable us to accomplish number of operations on data. Each structure has it own advantage and disadvantage. Is up to designer to pick right data structure to efficiently run certain algorithm.

Linear and Non Linear data structure

Linear data structure is a structure wherein data elements are form sequential process or arranged consecutively. Examples of this type are include arrays, stacks and queues. Contrary, non-linear data structure is each data element depend on others thus form a non-sequential process. Examples of this type are include trees, hash tree and graphs.

Data Structure Operation

Each data structure has each own time complexity in term of operation.  The fastest is O(1) and the slowest is O(n).  Table below gives us an idea of time complexity on each data structures.  For search, insert and delete operation, Hash table operate on O(1) notation while others are falling behind specifically on search operation.

images

Array

Array is the way to stored and retrieved data consist of equal size element using an index that usually refers to the element number of array. The advantage of array is constant time access to read and write. This means that data can be accessed in any order.  Arithmetic operation of array can be done by retrieve particular element address of array and retrieve the value. 

images

Time of operation of array are varies. Insert and delete operation of array element locate at the end or array are O(1), others location are O(n). 

images

Stack

A stack on data structure where insertion and deletion of data only allow on top. Stack structure is LIFO (last in first out). Operation on stack include Push, Empty, Top and Pop.  

images

Singly link list is a type of data structure where each element (node) contains key and reference to next node. Singly list operation include PushFront, TopFront, PushBack, TopBack, PopFront, PopBack, Find, Empty and Erase. 

images images

Doubly link list is a type of data structure where each element (node) contains key and reference to next node and back node. A can be travel in both forward and backward direction. Doubly list operation include AddBefore, PopBack,PushBack.

images images

Queue

A queue is a data structures that open on both end. It is mimic stream of data. One end use to insert data and other end to remove data.

images

Hash Table

A hash table is a type data structure that is utilized to maintain keys/value sets. Hash table using hash functionality to transform large key and spread key evenly throughout an array. Suitable characteristics of hash functionality consist of fast processing, direct addressing O(m), and distinct value for each object.

images

Binary Search Tree

A binary search tree saves data in a manner that they can be restored very easily. The left sub-tree of a node includes a key lower than or equal to its parent’s key, while the right sub-tree features a key higher than to its parent’s key. This algorithm is most effective utilized on lookup list once the elements have already been sorted. The search is beginning in the center, in a way that if midsection value isn’t the goal lookup key, it’s going to determine if it continues the search on left (lower key) or the right child (higher key).

images