What are Data structures?

Made up of 2 words “ DATA” + “STRUCTURES”. It is a way to arrange data on computers.

Example:

 Linear fashion – Array/Linked List

 One the other – Stacks
 Hierarchical Fashion – Trees
 Connect Nodes – Graph

Data Definition –defines a particular data with the following:

 Atomic – definition should define a single concept

 Traceable – definition should be able to be mapped to some data element.
 Accurate - definition should be unambiguous.
 Clear and concise – definition should be understandable.

Data Object represents an object having a data.

Data type is a way to classify various type of data such as integer, string, etc. which determines the
values that can be used with the corresponding type of data, the type of operations that can be
performed on the corresponding type of data.

There are two data types:

 Built-in Data Type

 Derived Data Type

Built – in Data type

Those data types for which a language has built-in support are known as Built- in Data types. For
example, most the languages provide the following built-in data types.

 Integers
 Boolean (true, false)
 Floating (decimal numbers)
 Character and Strings

Derived data type

Those data types which are implementation independent as they can be implemented in one or the
other way are known as derived data types. These data types are normally built by the combination of
primary or built-in data types and associated operations on them.

For example:

 List
 Array
 Stack
  Queue

Basic operations

The data in the data structures are processed by certain operations. The particular data structure chosen
largely depends on the frequency of the operation that needs to be performed on the data structure.

 Traversing
 Searching
 Insertion
 Deletion
 Sorting
 Merging

Data Structures and Algorithms – Array

Array – is a container which can hold a fix number of items and these items should be of the same type.
Most of the data structures make use arrays to implement their algorithms.

Following are the important terms to understand the concept of Array

 Element – each item stored in array is called an element

 Index – each location of an element in an array has a numerical index, which is used to identify
the element.

Array Representation

Arrays can be declared in various ways in different languages. For illustration, let’s take C array
declaration.

Elements Size Name

Int array [10] = {35, 33, 42, 10, 14,19, 27, 44, 26, 31}

Arrays can be declared in various ways in different languages. For illustration, let’s take C array
declaration.

35 33 42 10 14 19 27 44 26 31
0 1 2 3 4 5 6 7 8 9

Index

As per the above illustration, following are the important points to be considered .

 Index stats with 0

 Array length is 10 which means it can store 10 elements
  Each element can be accessed via its index. For example, we can fetch an element at index 6 as
9.

Basic operations

Following are the basic operations supported by an array.

 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.

Traverse operation – this operation is to traverse through the elements of an array.

Insertion operation – insert operation is to insert one or more data elements into an array. Based on the
requirement, a new element can be added at the beginning, end, or any given index of array.

Deletion operation – refers to removing an existing element from the array and re-organizing all
elements of an array.

Search operation – you can perform a search of an array element based on its value or its index.

Update operation – update operation refers to updating an existing element from the array at a given
index

Data Structure and Algorithms – Linked List

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 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

 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

 Insertion – adds an element at the beginning of the list.

 Deletion – deletes an element at the beginning of the list.
 Display – display the complete list.
 Search – searches an element using the given key.
 Delete – delete an element using the given key.

Insertion operation

Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams
here. First, create a node using the same structure and find the location where it has to be inserted.

Imagine that we are inserting a node B (NewNode), between A (leftnode) and C (rightnode). Then
point B next to C.

NewNode next → RightNode,

It should look like this-

LeftNode next → NewNode,

This will put the new node in the middle of the two . the new list should like this

Similar steps should be taken if the node is being inserted at the beginning of the list. While
inserting it at the end, the second last node of the list should point to the new node and the new
node will point to NULL.

Deletion operation

Deletion is also a more than one step process. We shall learn with pictorial representation. First,
locate the target node to be removed, by using searching algorithms.

The left (previous) node of the target node now should point to the next node of the target node-
LeftNode next → TargetNode

This will remove the link that was pointing to the target node. Now, using the following code, we will
remove what the target node is pointing at.

TargetNode.next→ Null

We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate
memory and wipe off the target node completely.

Reverse operation
this operation is a through one. We need to make the last node to be pointed by the head node and
reverse the whole linked list.

First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to
its previous node-
We have to make sure that the last node is not the last node. So we’ll have some temp node, which
looks like the head node pointing to that last node. Now, we shall make all left side nodes point to
their previous nodes one by one.

Except the node (first node ) pointed by the head node, all nodes should point to their, predecessor,
making them their new successor. The first node will point to NULL.

We’ll make the head node point to the new first node by using the temp node.

Data Structure and Algorithms – 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- firs- 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.
 Stact Representation

The following diagram depicts a stack and its operations

A stack can be implemented by means Array, Structure, Pointer, and Linked List. Stack can either be
a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack
using arrays, which makes it a fixed size stack implementation.

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.

When data is PUSHed onto stack.

To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the
following functionality is added to stacks.

Peek()-get the tod data element of the stack, without removing it.
isFull()-check if stack is full
isEmpty- check if stack is empty

At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always
represents the top of the stack, hence named top. The top pointer provides top value of the stack
without actually removing it.

First we should about procedures to support stack functions

peek ()

Algorithm of peek () function –

begin procedure peek

Return stack [top]

end procedure

Implementation of peek () function in C programming language –

Example:

int peek () {

return stack [top]

isFull ()

Algorithm of isfull () function-

regin procedure isfull {

Iftop equals to MAXSIZE

return true

else
return false,

Implementation of isfull () in C programming language –

bool isfull () {

If (top == MAXSIZE)

return true;

else

return false;

isempty ()

Algorithm of is empty () function –

begin procedure isempty

if top less than 1

return true

else

return false

endif

end procedure

Implementation of isempty () in C programming language is slightly different . We initialize top at -1, as

the index in array starts from 0. So we check if the top is below zero or-1 to determine if the stack is
empty. Here’s the code-

bool isempty(){

if(top == -1)

return true;

else

return false;

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.
If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.

Algorithm for PUSH Operation

A simple algorithm for Push operation can be derived as follows-

begin procedure push: stack, data

if stack is full

return null

endif

top←top + 1

stack [top]←data

end procedure

Implementation of this algorithm in C, is very easy. See the following code-

void push (int data){

if(!isFull()){

top = top +1;

stack[top] =data;

}else{
printf(“could not insert data, Stack is full.\n”);

}
}

POP Operation
Accessing the content while removing it from the stack, is know as pop operation. In 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 the 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 – return success.

Algorithm for pop operation

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
 Data Structure – Expressing Parsing

The way to write arithmetic expression is known as a notation. An arithmetic expression can be
written in three different but equivalent notations, i.e., without changing the essence or output of
an expression.

These notations are-

Infix Notation
Prefix (Polish) Notation
Postfix (Reverse-Polish) Notation

Infix Notation

We write expression in infix notation, e.g. a – b + c, where operators are used in between operands. It is
easy for us humans to read, write, and speak in infix notation but the same does not go well with
computing devices. An algorithm to process infix notation could be difficult and costly in terms of time
and space consumption.

Prefix Notation

In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For
example, +ab. This is equivalent to its infix notation a + b. Prefix notation also known as Polish
Notation.

Postfix Notation

This notation style is known as Reversed Polish Notation. In this notation style, the operator is
postfixed to the operands i.e.,the operator is written after the operands.

For example, ab+ This is equivalent to its infix notation a +b.

Sr.No. Infix Notation Prefix Notation Postfix Notation

1 a+b +ab ab+

2 (a + b) ∗ c ∗+abc ab+c∗

3 a ∗ (b + c) ∗a+bc abc+∗

4 a/b+c/d +/ab/cd ab/cd/+

5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗

6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

 Parsing Expressions

As we have discussed, it is not a very efficient way to design an algorithm or program to parse infix
notations. Instead, these infix notations are first converted into either postfix r prefix notations and
then computed.

To parse any arithmetic expression, we need to take care of operator precedence and associativity
also.

Precedence

When an operand is in between two different operators, which operator will take the operand first,
is decided by the precedence of an operator over others. For example:

As multiplication operation has precedence over addition, b*c will be evaluated first. A table of operator
precedence is provided later.

Associativity

Associativity describes the rule where operators with the same precedence appear in an expression. For
example a + b –c , both + and - have the same precedence, the then which part of the expression will
be evaluated first, is determined by associativity of those operators. Here, both + and – are left
associative, so the expression will be evaluated as (a+b)-c.

Precedence and associativity determines the order of evaluation of an expression.

Following is an operator precedence and associativity table (highest to lowest) −

Sr.No. Operator Precedence Associativity

1 Exponentiation ^ Highest Right Associative

2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative

3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

The above table shows the default behavior of operators. At any point of time in
expression evaluation, the order can be altered by using parenthesis. For example −
In a + b*c, the expression part b*c will be evaluated first, with multiplication as
precedence over addition. We here use parenthesis for a + b to be evaluated first,
like (a + b)*c.

Postfix Evaluation Algorithm

We shall now look at the algorithm on how to evaluate postfix notation −

Step 1 − scan the expression from left to right
Step 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operation