Fundamental of Data Structure

Click Here for Dynamic Memory Allocation/De-allocation Methods

Click Here for Difference between Malloc() and Calloc()

Introduction of Fundamental of Data Structure

• Data structures are used in almost every program/software system.
• It is a data storage format to store different types of computer data differently.
• Both data structure and algorithm work together.
• The term data structure is used to describe the way data is stored in the computer’s memory.

Definition

• Data structure is a logical or mathematical model of a particular organization of data. The mathematical model explains how the data is stored in memory and which operations are possible on it.
• Data structure is a specific way of storing and organizing data in a computer’s memory so that it can be retrieved efficiently later. 
• A data structure is a data organization, management, and storage format of data inside a computer’s memory for efficient access to data.

Features

• The data structure allows for improvement in program efficiency.
• Logical organization of data in the memory/file of the computer for better storage purposes.
• The data structure is a representation of the logical relationship existing between individual elements of data.
• Data structures and algorithms are interrelated i.e., Algorithm + Data structure = Program.

Example

• Examples of data structures are Array, String, Linked list, Stack, Queue, Tree, Graph, Heap, Hash table, etc.

Types of Data Structure

(A) Based on the data arrangement order in the memory/file inside the computer, the data structure is of two categories. These are – 

(a) Linear Data Structure

• • When the data/data elements are arranged sequentially/one after another in a linear order, it is called a linear data structure.
  • A data structure is said to be linear if its elements form a sequence or a linear list.
  • They are of two types –
    • Contiguous Data Structure – Example – Array.
      • When the data/data elements are arranged/kept together in memory (either RAM or in a file) sequentially/one after another in a continuous memory location in a given order, is called a contiguous linear data structure.
      • A contiguous data structure can be broken drawn further into two kinds: those that contain data items of all having the same type and size i.e., an array) where each element is of the same type and size the other kind of contiguous structure is called structure, where each element may be of different data types and thus may have different sizes.
    • Non-contiguous Data Structure – Example – Linked list, Stack, Queue
      • When the data/data elements are arranged/kept sequentially/one after another but scattered (not contiguous) in the memory i.e., here and there in the memory, is called a non-contiguous linear data structure.
      • Non-contiguous data structures are implemented as a collection of data items, each data item is called a node, where each node can point to one or more other nodes in the collection.
      • The simplest kind of non-contiguous structure is a linked list. A linked list represents a linear, one-dimensional type of non-contiguous structure, where there is only the notation of backward and forwards.
      • A tree is an example of a two-dimensional non-contiguous structure. Here, there is the notion of up and down and left and right. In a tree, each node has only one link that leads into the node and links can only go down the tree.
      • The most general type of non-contiguous structure, called a graph has no such type of restrictions.
    • Hybrid Data Structure
      • When two basic types of structures are mixed it creates a hybrid form where one part may be contiguous and another part non-contiguous.
      • Example – doubly linked list.

(B) Non-linear Data Structure

• • When the data/data elements are arranged in an unorganized manner in the memory of a computer, it is called a non-linear data structure.
  • This structure is mostly used for representing data that contains a hierarchical relationship among various elements with different data items.
  • A data structure is said to be non-linear if its elements form a hierarchical classification where data items appear at various levels.
  • They are of two types –
    • Non-Cyclic/Acyclic Data Structure – Example – Tree.
    • Cyclic Data Structure – Example – Graph.

(B) Based on the structure/nature of Data, Data structures are further divided into two types: –

(a) Primitive Data Structures:

• • These are the basic data structures that directly operate upon the machine’s instructions.
  • They have different representations on different computers in the form of Boolean, Integers, floating point/real numbers, character constants, string constants, Enumerated type, Date & Time, and pointers/references.

(b) Non-primitive/Composite Data Structures:

• • These are more complicated data structures and are derived from primitive data structures.
  • They emphasize grouping the same or different data items with a relationship between each data item.
  • Examples are – Arrays, Structures, unions, lists (Linear and Non-linear) and files that come under this category.

Use/Application of Data Structure

• Different kinds of data structures are suited to store different kinds of application’s data, and some are highly for specific tasks. For example – B-tree for databases, Hash table for compiler, etc.
• Data structure provides a way to manage huge amounts of data efficiently such as large databases, internet indexing services, etc.