Introduction to Data structures

In computer terms, a data structure is a Specific way to store and organize data in a
computer's memory so that these data can be used efficiently later. Data may be arranged in
many different ways such as the logical or mathematical model for a particular organization of
data is termed as a data structure. The variety of a particular data model depends on the two
factors -
 Firstly, it must be loaded enough in structure to reflect the actual relationships of the data with
the real world object.
 Secondly, the formation should be simple enough so that anyone can efficiently process the
data each time it is necessary.

Categories of Data Structure:

The data structure can be sub divided into major types:

 Linear Data Structure

 Non-linear Data Structure

Linear Data Structure:

A data structure is said to be linear if its elements combine to form any specific order.
There are basically two techniques of representing such linear structure within memory.

 First way is to provide the linear relationships among all the elements represented by means of
linear memory location. These linear structures are termed as arrays.
 The second technique is to provide the linear relationship among all the elements represented
by using the concept of pointers or links. These linear structures are termed as linked lists.

The common examples of linear data structure are:

 Arrays
 Queues
 Stacks
 Linked lists

Non linear Data Structure:

This structure is mostly used for representing data that contains a hierarchical relationship among
various elements.

Examples of Non Linear Data Structures are listed below:

 Graphs
 family of trees and
 table of contents
Basic Operations
Following are the basic operations
 Traverse − print all the array elements one by one.
 Insertion − Adds an element at the given index.
 Deletion − Deletes an element at the given index.
 Search − Searches an element using the given index or by the value.
 Update − Updates an element at the given index.

STACK
A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is
named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of
plates, etc.

A real-world stack allows operations at one end only. For example, we can place or remove a
card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at
one end only. At any given time, we can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the
element which is placed (inserted or added) last, is accessed first. In stack terminology, insertion
operation is called PUSH operation and removal operation is called POP operation.
Stack Representation
The following diagram depicts a stack and its operations –

Basic Operations
Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from
these basic stuffs, a stack is used for the following two primary operations –
 push() − Pushing (storing) an element on the stack.

pop() − Removing (accessing) an element from the stack.

Push Operation
The process of putting a new data element onto stack is known as a Push Operation. Push
operation involves a series of steps −
 Step 1 − Checks if the stack is full.
 Step 2 − If the stack is full, produces an error and exit.
 Step 3 − If the stack is not full, increments top to point next empty space.
 Step 4 − Adds data element to the stack location, where top is pointing.
 Step 5 − Returns success.

Algorithm for PUSH Operation

begin procedure push: stack, data

if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure

Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In an array
implementation of pop() operation, the data element is not actually removed, instead top is
decremented to a lower position in the stack to point to the next value. But in linked-list
implementation, pop() actually removes data element and deallocates memory space.
A Pop operation may involve the following steps −
 Step 1 − Checks if the stack is empty.
 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
 Step 4 − Decreases the value of top by 1.
 Step 5 − Returns success.

A simple algorithm for Pop operation can be derived as follows –

begin procedure pop: stack

if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure

Three applications of stacks are presented here.

1. Expression evaluation
2. Backtracking (game playing, finding paths, exhaustive searching)
3. Memory management, run-time environment for nested language features.

QUEUE
Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is
open at both its ends. One end is always used to insert data (enqueue) and the other is used to
remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored
first will be accessed first.
A real-world example of queue can be a single-lane one-way road, where the vehicle enters first,
exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.

Queue Representation
As we now understand that in queue, we access both ends for different reasons. The following
diagram given below tries to explain queue representation as data structure –

Basic Operations
Queue operations may involve initializing or defining the queue, utilizing it, and then completely
erasing it from the memory. Here we shall try to understand the basic operations associated with
queues −
 enqueue() − add (store) an item to the queue.
 dequeue() − remove (access) an item from the queue.

Few more functions are required to make the above-mentioned queue operation efficient. These
are −
 peek() − Gets the element at the front of the queue without removing it.
 isfull() − Checks if the queue is full.
 isempty() − Checks if the queue is empty.

Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively
difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
 Step 1 − Check if the queue is full.
 Step 2 − If the queue is full, produce overflow error and exit.
 Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
 Step 4 − Add data element to the queue location, where the rear is pointing.
 Step 5 − return success.

Algorithm for enqueue operation

procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure

Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data where front is pointing
and remove the data after access. The following steps are taken to perform dequeue operation −
 Step 1 − Check if the queue is empty.
 Step 2 − If the queue is empty, produce underflow error and exit.
 Step 3 − If the queue is not empty, access the data where front is pointing.
 Step 4 − Increment front pointer to point to the next available data element.
 Step 5 − Return success.

Algorithm for dequeue operation

procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure

LINKED LIST
A linked list is a sequence of data structures, which are connected together via links.
Linked List is a sequence of links which contains items. Each link contains a connection to
another link. Linked list is the second most-used data structure after array. Following are the
important terms to understand the concept of Linked List.
 Link − Each link of a linked list can store a data called an element.
 Next − Each link of a linked list contains a link to the next link called Next.
 LinkedList − A Linked List contains the connection link to the first link called First.

Linked List Representation

Linked list can be visualized as a chain of nodes, where every node points to the next node.
As per the above illustration, following are the important points to be considered.
 Linked List contains a link element called first.
 Each link carries a data field(s) and a link field called next.
 Each link is linked with its next link using its next link.
 Last link carries a link as null to mark the end of the list.

Types of Linked List

Following are the various types of linked list.
 Simple Linked List − Item navigation is forward only.
 Doubly Linked List − Items can be navigated forward and backward.
 Circular Linked List − Last item contains link of the first element as next and the first
element has a link to the last element as previous.

Basic Operations
Following are the basic operations supported by a list.
 Insertion − Adds an element at the beginning of the list.
 Deletion − Deletes an element at the beginning of the list.
 Display − Displays the complete list.
 Search − Searches an element using the given key.
 Delete − Deletes an element using the given key.

.1 Introduction to files

Real life situations involve large volumes of data. In such cases, the console (keyboard)
oriented I/O operations create two major problems: a) it becomes cumbersome and time
consuming to handle large volumes of data through terminals; and b) the entire data is lost when
either the programme is terminated or computer is turned off. Thus, it is necessary to have more
flexible approach where data can be stored on the disks and read whenever necessary, without
destroying the data. This method employs the concept of files to store data.
In this section, you will learn about files, which are very important for storing
information permanently. You store information in files for many purposes like data processing
by your programmes.

What is a File?
A file is a collection of bytes stored on a secondary storage device, which is generally a
disk of some kind. The collection of bytes may be interpreted, for example, as characters, words,
lines, paragraphs and pages from a textual document; fields and records belonging to a database;
or pixels from a graphical image. The meaning attached to a particular file is determined entirely
by the data structures and operations used by a programme to process the file.
File: the file is a permanent storage medium in which we can store the data permanently.

Types of file can be handled

we can handle three type of file as
(1) sequential file
(2) random access file
(3) binary file

Access to files generally requires four basic operations:

Open: This allows access to a file and establishes the position, offset, in the file.
Close: This ends access to the file. When access to a file completes, it should be closed. The
number of files that a running program can have any time is limited; by closing file properly
these limited facilities can be used more intelligently.
Read: This gets information from the file, either in the form of characters strings, or in the form
of data (combined integers, characters, floating point numbers, and structures).
Write: This adds information to the file or replaces information already in the file.
___________________________________________________________________________
OPERATIONS ON FILES
The commonly performed operations over files are the following:
1. Opening a file
2. Reading from a file
3. Writing a file
4. Appending to a file
5. Updating a file
6. Deleting a file
7. Renaming a file
8. Closing a file
These operations are accomplished by means of standard library functions that are
provided by C.
____________________________________________________________________________
5.4 OPENING AND CLOSING OF FILES

5.5fopen ()
The fopen () is to open a file. Opening a file basically establishes a link between a program and
the file being opened.
SYNTAX
fp=fopen(“filename‟,”mode of opening”);
where,
filename->is the name of the Purpose
file being opened(which is
remembered by the operating
system).Mode of opening can
be any one of the following.
Mode of opening
 w To create a text file. If the file
already exits, its contents are
destroyed; otherwise it is
created, if possible.
r To open a text file for reading;
the file must exist.
a To open a text file for
appending (writing at the end);
if the file does not exist, it is
created, if possible.
(ii) fclose ()
The fclose () is the counterpart of fopen ().This is used to close a file. Closing a file names means
de-linking the file from the program and saving the contents of the file.
SYNTAX
fclose (fp);
where
fp->is the pointer to FILE type and represents a file. The file represented by fp is closed.

Reading a character from a file

getc() is used to read a character into a file
Syntax:
character_variable=getc(file_ptr);
Writing acharacter into a file
putc() is used to write a character into a file
puts(character-var,file-ptr);