CHAPTER OUTLINE
14.1
Introduction to Data Structure
14.2 List
14.3
Implementation of a List
14.4
Traversal of a List
14.5
Searching and Retrieving an Element
14.6
Predecessor and Successor
14.7 Insertion
14.8 Deletion
14.9 Sorting
14.10 Merging Lists
14.11
Representation of a Stack
14.12
Stack-related Terms
14.13
Operation on a Stack
14.14 Implementation of a Stack
14.15 Queues
14.16
Various Positions of Queue
14.17
Representation of Queue
14.18 Single Linked List
14.19 Linked List with and without Header
14.20
Insertion
14.21
Deletion
14.22
Double Linked List
14.23
Applications
Exercises
14.1 INTRODUCTION TO DATA STRUCTURE
Data structure is a method of representation of logical relationships between individual data elements
related to the solution of a given problem. Data structure is the most convenient way to handle data
of different data types including abstract data type for a known problem. For example, the
characteristics of a house can be represented by house name, house number, location, number of
floors, Number of rooms on each floor, kind of fencing to the house (either with brick walls or wire),
electrification (either underground or open), balcony provided or not, and so on.
Fig. 14.1 shows few details of the house. Here one can use a variety of data types, such as char, int,
468 Programming and Data Structures
Boolean type and so on to represent the data elements while solving a problem with the help of a
computer language. For example, with the help of a computer, the characteristics of a house such as
the number of floors of the house can be represented with either int or char type. House number and
the number of rooms can also be declared with the same type, provided that the data must be in
limits of the range of data type. In C/C++, the char data type perfectly works as integer data in its
range from -128 to 127 and as unsigned char from 0 to 255. At few places, selection is also important
to minimize the overhead. For example, if we are going to fence the house with brick instead of wire.
Here, the brick wall may be expensive. Likewise, if we are using signed int to store a positive number
(number of floors) instead of char, we are wasting one byte of the system. Hence, here char is
appropriate which takes only one byte.
Electrification should be declared with char data type. Like the above example, in practical
application of data structure, to create a data structure some components are involved directly or
indirectly to built the system. In other words, data structure is a structured set of variables associated
with one another in different manner, co-operatively defining components of the system.
The components of data can be organized and records are maintained. Further, the record
formation leads to the development of abstract data type and database systems.
Fig. 14.1 Brief details of a house
In data structure, we also have to decide on the storage, retrieval and operation that should be
carried out between the logically related items.
For example, the data must be stored in the memory of the computer in a format that is
understandable, that is, 0 and 1. The data stored in the computer must be retrieved in a
predictable/understandable format, that is, ASCII. In order to transform data, various operations
are to be performed.
As stated earlier, data structure involves the following effects.
1) Data organization or clubbing
2) Accessing technique
3) Level of associatively
4) Manipulating selections for information
Data structure is the base of the programming tools and the choice of data structure provides the
following things.
1) The data structure should be satisfactory to represent the relationship between data elements.
2) The data structure should be easy so that the programmer can easily process the data, as per
requirement.
Data structures have been classified in several ways. Different authors classify them differently. Fig.
14.2 shows different types of data structures. Besides these data structures, other types of data
structures are lattice, Petri nets, neural nets, semantic nets, search graphs, and so on.
Linear: In the linear data structure, values are arranged in a linear fashion. An array, linked list,
stacks and queues are examples of linear data structure in which values are stored in a sequence.
There is a relation between the adjacent elements of a linear list.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.