Page 9 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures
Notes
2 LOVELY PROFESSIONAL UNIVERSITY
1.1 Overview of Data Structure
A data structure is a scheme for organizing data in the memory of a computer. A 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.
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.
Some of the more commonly used data structures include lists, arrays, stacks, queues, heaps,
trees and graphs. The way in which the data is organized affects the performance of a program
for different tasks. 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.
Notes 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.
Data may be organized in many different ways: the logical or mathematical model of a particular
organization of data is called data structure. Data model depends on two things. First, it must be
rich enough in structure to mirror the actual relationship of the data in the real world. On other
hand, the structure should be simple to execute the process the data when necessary.
Data are also organized into more complex types of structures. The study of such data structure,
which forms the subject matter of the text, includes the following three steps:
1. Logical or mathematical description of the structure.
2. Implementation of the structure on a computer.
3. Quantitative analysis of the structure, which include determining the amount of memory
needed to store the structure and the time required to process the structure.
Computer programmers decide which data structures to use based on the nature of the data and
the processes that need to be performed on that data.
When selecting a data structure to solve a problem, you should follow these steps.
1. Analyze your problem to determine the basic operations that must be supported.
2. Quantify the resource constraints for each operation.
3. Select the data structure that best meets these requirements.
Examples of Basic operations include inserting a data item into the data structure, deleting a data
item from the data structure, and finding a specified data item.