Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Data Structure - Doubly Linked List
A double linked list, a kind of linked list, makes it easier to go
ahead and backward than a single linked list
...

Link − Each link of a linked list can store a data called
an element
...

• Prev − Each link of a linked list contains a link to the
previous link called Prev
...

Doubly Linked List Representation
•

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

Each link carries a data field(s) and two link fields called
next and prev
...

Each link is linked with its previous link using its
previous link
...

Basic Operations
•

Following are the basic operations supported by a list
...

• Deletion − Deletes an element at the beginning of the
list
...

• Delete Last − Deletes an element from the end of the
list
...

• Delete − Deletes an element from the list using the key
...

• Display backward − Displays the complete list in a
backward manner
...

Example
//insert link at the first location
void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
Deletion Operation
Following code demonstrates the deletion operation at the
beginning of a doubly linked list
...

Example
//insert link at the last location
void insertLast(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;

//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}

Data Structure - Circular Linked List
A circular linked list is a type of linked list where the first member
points to the final element and the last element points to the
first element
...

Singly Linked List as Circular
In singly linked list, the next pointer of the last node points to the
first node
...


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

• The first link's previous points to the last of the list in
case of doubly linked list
...

insert − Inserts an element at the start of the list
...

• display − Displays the list
...

Example
insertFirst(data):
Begin
create a new node
node -> data := data
if the list is empty, then
head := node
next of node = head

else
temp := head
while next of temp is not head, do
temp := next of temp
done
next of node := head
next of temp := node
head := node
end if
End
Deletion Operation
Following code demonstrates the deletion operation in a circular
linked list based on single linked list
...

display():
Begin
if head is null, then
Nothing to print and return
else
ptr := head
while next of ptr is not head, do
display data of ptr
ptr := next of ptr
display data of ptr
end if
End

Data Structure and Algorithms - Stack
A stack is an Abstract Data Type (ADT), commonly used in most
programming languages
...


In the real world, a stack only permits activities at one end
...
Similar to this, Stack ADT only permits data
operations at one end
...

It is a LIFO data structure because of its property
...
In this case, the piece that was
added or inserted last is the one that is accessible first
...

Stack Representation
The following diagram depicts a stack and its operations −

A stack can be implemented by means of Array, Structure,
Pointer, and Linked List
...
Here, we are going to

implement stack using arrays, which makes it a fixed size stack
implementation
...
Apart from these basic stuffs, a stack is
used for the following two primary operations −
•
•

push() − Pushing (storing) an element on the stack
...


When data is PUSHed onto stack
...
For the same purpose, the following functionality is added
to stacks −
•

•
•

peek() − get the top data element of the stack, without
removing it
...

isEmpty() − check if stack is empty
...
As this pointer always represents the top of the stack,
hence named top
...

First we should learn 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 −
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedure
Implementation of isfull() function in C programming language −
Example
bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;

}
isempty()
Algorithm of isempty() function −
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedure
Implementation of isempty() function in C programming
language is slightly different
...
So we check if the top is below zero or -1
to determine if the stack is empty
...
Push operation involves a series of steps −

•
•
•

•

•

Step 1 − Checks if the stack is full
...

Step 3 − If the stack is not full, increments top to point
next empty space
...

Step 5 − Returns success
...

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
...
\n");
}
}
Pop Operation
Accessing the content while removing it from the stack, is known
as a Pop Operation
...
But in linked-list implementation, pop()
actually removes data element and deallocates memory space
...

Step 2 − If the stack is empty, produces an error and
exit
...


•
•

Step 4 − Decreases the value of top by 1
...


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
Implementation of this algorithm in C, is as follows −
Example
int pop(int data) {

if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty
...

An arithmetic expression can be written in three different but
equivalent notations, i
...
, without changing the essence or
output of an expression
...
We shall learn the same here in this chapter
...
g
...
It is easy for us
humans to read, write, and speak in infix notation but the same
does not go well with computing devices
...

Prefix Notation
In this notation, operator is prefixed to operands, i
...
operator is
written ahead of operands
...
This is equivalent
to its infix notation a + b
...

Postfix Notation
This notation style is known as Reversed Polish Notation
...
e
...
For example, ab+
...

The following table briefly tries to show the difference in all
three notations −
Sr
...


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

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

As multiplication operation has precedence over addition, b * c
will be evaluated first
...

Associativity
Associativity describes the rule where operators with the same
precedence appear in an expression
...
Here, both + and − are left
associative, so the expression will be evaluated as (a + b) − c
...
Following is an operator precedence and
associativity table (highest to lowest) −
Sr
...


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
...
For example −
In a + b*c, the expression part b*c will be evaluated first, with
multiplication as precedence over addition
...

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



---