Basic Terminology in Data structure

Data are simply values or set of values. A data item refers to a single unit of values. Data items that are divided into sub items are called group items; those that are not are called elementary items.

An entity is something that has certain attributes or properties which may be assigned values. The values themselves may be numeric or non numeric

Entities with similar attributes from an entity set. Each attribute of an entity set has a range of values, the set of all possible values that could be assigned to the particular attribute

The term information is used for data with given attributes, or in other words meaningful or processed data.

A field is a single elementary unit of information representing an attribute of an entity, a record is a collection of field values of a given entity and a file is the collection of records of the entities in a given entity set

Each record in a file may contain many field items, but the value in a certain field may uniquely determine the record in the file. Such a field is called primary key.

The above organization may not be complex enough to maintain and efficiently process certain collections of data. For this reason, data are also organized into more complex types of structures. The study of such structures includes the following three steps:

  • Logical or mathematical description of the structure.
  • Implementation of the structure on a computer.
  • Quantitative analysis of the structure, which includes determining the amount of memory needed to store the structure and the time required to process the structure

Data Structures

Data may be organized in many different ways; the logical or mathematical model of a particular organization of data is called a data structure

The choice of a particular data model depends on two considerations.

  • It must be rich enough in structure to mirror the actual relationships of the data in the real world.
  • The structure should be simple enough that one can effectively process the data whn necessary.

Data Structure Operations

The particular data structure that one chooses for a given situation depends largely on the frequency with which specific operations are performed. Some common operations are:

  • Traversing : Accessing each record exactly once
  • Searching: Finding the location of the record with a given key value
  • Inserting: Adding a new record to the structure.
  • Deleting: Removing a record from the structure.
  • Sorting: Arranging the records in some logical order
  • Merging: Combining the records in two different sorted files into a single sorted file


An algorithm is a finite step by step list of well defined instructions for solving a particular

Algorithm Analysis

In order to compare algorithms, we must have some criteria to measure the efficiency of our algorithms

Suppose M is an algorithm, and suppose ‘n’ is the size of the input data. The time and space used by the algorithm are the two main measures for the efficiency of M. The time is measured by counting the number of key operations-in sorting and searching algorithms, for example, the number of comparisons. That is because the key operations are so defined that the time for the other operations is much less than or at most proportional to the time for the key operations. The space is measured by counting the maximum memory needed by the algorithm

The complexity of a n algorithm is the function f(n) which gives the running time and/or storage space requirement of the algorithm in terms of the size ‘n’ of the input data. Frequently the storage space required by an algorithm is simply a multiple of the data size ‘n’. Accordingly unless otherwise stated or implied the “complexity” shall refer to the running time of the algorithm

Leave a Comment