Linked List Based Implementation of Stack and Queue

Why different implementations

• The way the data structure is implemented is a measure of its efficiency (time and space)
  
• It is important to see different alternatives
  
• So far we have discussed array based implementation (vector). What if we use second class arrays?
  

Objectives:
Discuss linked list based implementation of stack and queue.
Compare and contrast two implementations

Linked List based Stack

• Stack is LIFO data structure
  
  
  
  
  
  
  
  
  
• Linked list is a collection of nodes where each node has a data element and a pointer to the next element in the list.
  
  

Linked List based Stack- basic concepts

• Stack we push into and pop from the top of the stack.
  
• Therefore a special pointer “toOftheStack” which is pointing to the top of the stack is created.
  
• Intially toOftheStack is null.
  
• Try following operations
  
• push (a), push(b), push(c)
  
• pop()
  

Linked List based Stack- C++ Details
A Node: (figure 16.19)

struct ListNode
{
Object element;
ListNode *next;
ListNode ( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { }

};

Linked List based Stack- C++ Details
Template
template <class Object> class Stack {
public:
Stack( );
Stack( const Stack & rhs );
~Stack( ); bool isEmpty( ) const;
const Object & top( ) const;
void makeEmpty( );
void pop( );
void push( const Object & x );
Object topAndPop( );
const Stack & operator=( const Stack & rhs );

private:
struct ListNode { Object element; ListNode *next; ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { } };

ListNode *topOfStack; };

Linked List based Stack- C++ Details
Implementation
Stacklist.cpp
push, pop, top, makeEmpty and = operator

Linked List based Queue

• Queue if FIFO data structure
• Implementation is very similar to stack. Here, both from and back of the data structure need pointers.

Linked List based Queue- basic concepts

• Queue, enqueue into the front of the stack. Dequeue from the back of the stack
• Therefore two special pointers “front,” and “back,” are created.
• Initially both both front and back are null.
• Try following operations
• enqueue (a), enqueue(b), enqueue(c)
• dequeue()

Linked List based Queue - C++ Details
A Node:

struct ListNode {
Object element;
ListNode *next;
ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n )
{ }
};

Linked List based Queue - C++ Details
Template
Queuelist.h
Notice that there are two pointers, front and back

Linked List based Queue - C++ Details
Implementation
Queuelist.cpp
Enqueue, dequeue, copy constructure and = operator

Array base vs. Linked list based Implementation

• For large size stacks and queue specially the size is not known linked list is better.
• For memory scare devices such as small handheld devices, linked list may perform better.

Algorithms & Data Structures - Linked List

Objectives
At the end of the class you should be able to answer:

Explain the design, use, and operation of a linear list

Implement a linear list using a linked list structure

Understand the operation of the linear list ADT

Write application programs using the linear list ADT

Design and implement different link-list structures

Basic Operations
The four basic list operations are :

1. Insertion
2. Deletion
3. Retrieval
4. Traversal

Insertion

• Insertion is used to add a new element to the list.
• List insertion can be ordered or random.
• Ordered list are maintained in sequence according to the data or, when available, a key that identifies the data.
• In random lists there is no sequential relationship between two elements.Random lists are sometimes called chronological lists.

Figure 5-1 Shows the insertion of data into a list



Deletion

• Deletion is used to remove an element from the list.
• Deletion from a list requires that the list be searched to locate the data being deleted
• Once located, the data are removed from the list.

Figure 5-2 Shows the Deletion operation


Retrieval

• Retrieval is used to get the information related to an element without changing the structure of the list.
• List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the list.

Figure 5-3 Shows retrieving data from a list



Traversal

• List traversal processes each element in a list in sequence
• It requires a looping algorithm rather than a search.

Implementation

• Several data structures can be used to implement a list; we use a linked list.
• Linked list is a good structure for a list because data are easily inserted and deleted at the beginning, in the middle, or at the end of the list.

Data Structure
To implement a list, we need two different structures, a head node and data node.


Figure 5-5 Shows a head node and data node



Algorithm
Create List:
Create list allocate the head structure and initializes the metadata for the list.
Figure 5-6 shows the header before and after it is initialized by create list.


Figure 5-6 Create list



Algorithm for creating a list



Insert Node
Insert node adds data to a list. Given the predecessor, there are three steps to the insertion:
1. Allocate memory for the new node and move data to the node.
2. Point the new node to its successor.
3. Point the new node’s predecessor to the new node.


Figure 5-7 Add node to empty list



Insert at Beginning

• To insert a node at the beginning of the list, we simply point the new node to the first node of the list and then ser the head pointer to point to the new first node.
• Figure 5-8 shows inserting a node at the beginning

Figure 5-8 Shows Add node at Beginning



Insert in Middle

• To insert a node between two nodes, we point the new node to its successor and then point its predecessor to the new node.
  
• Figure 5-9 shows inserting a node in the middle.
  

Figure 5-9 Add node in Middle



Insert at End

• To add at the end of the list, we only need to point the predessor to the new node.
  
• The Figure5-10 insert the node at the end
  

Figure 5-10 Add node at End



Algorithm for Insertion is shown in figure 5-2



Delete Node

• The delete node algorithm logically removes a node from the list by changing various link pointers and then physically delete the node from dynamic memory.
  
• Figure 5-11 shows Deleting the first node
  

Delete First Node



Algorithm for Deleting a node


Retrieve Node
Figure 5-5 Shows retrieve list node algorithm








Advance Linked List

• Circular Linked List
  
• Circular linked list is a type of linked list where the last node will point back to the first node
  

Graphical view of a circular linked list

Algorithms & Data Structures - Heap

A priority queue is a special type of queue where items with special characteristic are removed from the list first.

Heap is a priority queue data structure.

heap is a structure that fulfils two properties:

1.Shape (no hole)
A heap must be a complete tree.

2.Order of its element
The value stored in each node of the heap must be greater than, less than, or equal to the value of its children, depending on what type of heap it is.


Nodes in a heap are filled from left to right, and we cannot proceed to the next lower level of the tree until all nodes in that particular level are filled.


There are two types of heaps:

Ascending heap

This is a heap in which the values of the parent's nodes are smaller than or equal to the value of the children's nodes.



Descending heap

This is a heap in which the value of the parent's nodes are greater than or equal to the value of the children's nodes




Example:
Given these data: 17, 8, 12, 4, 26, 5, 14.
Build a descending and ascending Heap


BINARY HEAP

The binary heap is the classic method used to implement priority queues.

A binary heap is a binary tree that, except for the bottommost level, is completely filled from left to right.



HEAP SORT

A heapSort is a method of sorting an array of items of no particular order into an array of certain order.

Applicable to its name, this method uses a heap to facilitate sort operations.

Operations with HEAPSORT

• Insertion
• Deletion
• delete Min
• delete Max

Insertion

REHEAP UP CONCEPT

Delete Min

Coding : check previous courseware

Delete Max
Involved descending heap


Exercise 1:
Given the following numbers, build an ascending and descending heap.

8, 54, 43, 3, 77, 89, 21, 23, 5, 40

Perform deletemin for the ascending heap and deletemax for the descending heap

Exercise 2:
Use heapsort to sort the numbers into ascending list.

8, 54, 43, 3, 77, 89, 21, 23, 5, 40

Algorithms & Data Structures - Hashing

Objective

At the end of the class learner will be able to answer the following:

• Design and implement hash-list searches
• Discuss the merits of different collision resolution algorithms

Hashed List Searches

• The goal of a hashed search is to find the target data in only one test. After discussing some basic hashed list concepts, we discuss eight hashing methods.

Definition:
Hashing is a key-to-address mapping process.


Terms must be familiarized.
Synonyms: The set of keys that hash to the same location
Collision: A collision occurs when a hashing algorithm produces an address for an insertion key and that address is already occupied.
Home address: The address produced by the hashing algorithm is known as the home address.
Prime area: The memory that contains all of the home addresses is known as the prime area.
Probe: Each calculation of an address and test for success is known as a probe.


Hash Concept



Figure 13-7 shows collision Resolution concept



Hashing Methods
There are eight hashing methods they are:

1. Direct method
2. Substraction method
3. Modulo-division
4. Midsquare
5. Digit extraction
6. Rotation
7. Folding
8. Pseudorandom generation

Figure 13-8 shows Basic Hashing Techniques


Direct Method
In direct hashing the key is the address without any algorithmic manipulation.
Direct hashing is limited, but it can be very powerful because it guarantees that there are no synonyms and therefore no collision.

Example:



Modulo-division Method

• This is also known as division remainder method.
• This algorithm works with any list size, but a list size that is a prime number produces fewer collisions than other list sizes.
• The formula to calculate the address is:
  Address = key MODULO listsize + 1
  Where listsize is the number of elements in the arrary.

Example:
Given data : 
Keys are : 137456 214562 140145
137456 % 19 +1 = 11
214562 % 19 + 1 = 15
140145 % 19 + 1 = 2



Digit-extraction Method

• Using digit extraction selected digits are extracted from the key and used as the address.

Example:

• Using six-digit employee number to hash to a three digit address (000-999), we could select the first, third, and fourth digits( from the left) and use them as the address.

The keys are:
379452 -> 394
121267 -> 112
378845 -> 388


Folding Method
Two folding methods are used they are:

1. Fold shift
2. Fold boundary

Fold Shift
In fold shift the key value is divided into parts whose size matches the size of the required address. Then the left and right parts are shifted and added with the middle part.


Fold boundary
In fold boundary the left and right numbers are folded on a fixed boundary between them and the center number. The two outside values are thus reversed.

Example:



Midsquare Method

• In midsquare hashing the key is squared and the address is selected from the middle of the square number.
• Limitation is the size of the key.

Example:
9452² = 89340304: address is 3403


Rotation Method

• Rotation method is generally not used by itself but rather is incorporated in combination with other hashing methods.
• It is most useful when keys are assigned serially.

Example:


Pseudorandom Hasing
A common random-number generator is shown below.
y= ax + c
To use the pseudorandom-number generator as a hashing method, we set x to the key, multiply it by the coefficient a, and then add the constant c. The result is then divided by the list size, with the remainder being the hashed address.

Example:
Y= ((17 * 121267) + 7) modulo 307
Y= (2061539 + 7) modulo 307
Y= 2061546
Y=41


Hashing Algorithm


Collision Resolution
There are several methods for handling collisions, each of them independent of the hashing algorithm.

Collision resolution methods

In this section I will discuss the Linear probe and Quadratic probe


Linear Probe
In a linear probe when data cannot be stored in the home address we resolve the collision by adding 1 to the current address.


Example for Linear Probe collision Resolution



Quadratic Collision Resolution
In the quadratic probe, the increment is the collision probe number squared. Thus for the first probe we add 1², for the second collision probe we add 2² etc.

Algorithms & Data Structures - Algorithm analysis

OBJECTIVES

Understands what is algorithms analysis

Identify the reasons for conducting algorithm analysis

Obtain the basic mathematics background

Able to estimate the running time

Understand the efficiency of algorithm

Able to select the best algorithm for a program

What is algorithm analysis?

• The process of estimating the running time of an algorithm.
• Used to find the best algorithm to solve the problem.
• The role of algorithm analysis is to estimate the algorithm resource consumption.
• Algorithm analysis estimates the exact time and memory space required by an algorithm to solve a certain problem.

Algorithm Analysis --> Algorithm Efficiency

• less code
• economic
• less workload
• easy to maintain
• Faster to execute and get the result (speed)

How to conduct?

• Algorithm Analysis
• Empirical Analysis
• based on experimental Analysis
• Theoretical Analysis
• based on mathematical Analysis

Theoretical Analysis

• Use mathematical calculation
• Big–O notation
• Omega (Ω) notation

Big-O notation

Expressed as O(n) - On the Order of n

Instruction speed in loop

Program Structure	Big-O	Iterations	Estimate Time
Logarithmic	O(log n)	14	Microseconds
Linear	O(n)	10000	0.1 second
Linear Logarithmic	O(n(log n))	140000	2 seconds
Quadratic	O(n2)	100002	15 – 20 min

ALGORITHM EFFICIENCY

• Comparing two different algorithms that solve the same problem
• Algorithmics : “the systematic study of the fundamental techniques used to design and analyze efficient algorithms”
• Linear loops
• Logarithmic loops
• Linear logarithmic
• Dependent Quadratic
• Quadratic
• Best Case
• Worst Case
• Average case

CALCULATION Big O

• State the equation
• Remove the coefficients
• Keep the largest factor
• State in Big O notation

Exercises
Calculate the running time for this segment program
int i, j, p, q;
p = 5;
for (i = 0; i < 15; i++)
p = p + i;
q = 0;
for (j = 0; j < 60; j++)
q = q + j;

Calculate the running time for this segment program
int i, j, p, q;
p = 5;
for (i = 0; i < 30; i++)
for (j = 0; j < 60; j++)
p = p + i + j;
for (i = 0; i < 60; i++)
q = q * i + p;

Order the following function by growth rate:
n log2(n), n + n2, 24, n, √n, log2 n, 2n
Indicate which function grow at the same rate.

Calculate the running time for this segment program
Fun(int x)
{
if (x < 1)
return 1;
else
return (Fun(x - 2));

Calculate the running time

log(n) * n + 2n + log (n)

3n4 + 8n3/5 + 4

6 log(n) + 9n

3 n5/2 + n log(n)

6 log(n) + 7 log(n)

Algorithms & Data Structures - Data Structures And Operations

Objectives
At the end of the class learner will be able to answer the :

Insert, delete, and process nodes in an AVL tree

Understand the operation of the AVL tree ADT

Write application programs using an AVL tree

AVL Tree

Introduction
In 1962, two Russian mathematicians, G.M Adelson-velskii and E.M Landis, created the balanced binary tree structure that is named after them-the AVL tree.

Definition
An AVL tree is a height-balanced binary search tree.

AVL Balance Factor:
The formula to calculate the height-balance is :
│ H_L – H_R │ <=1 Where H_L is the height of the left subtree and H_R is the height of the right subtree

The balance factor for any node in an AVL tree must be +1, or -1,we will use the descriptive identifiers

• LH for left hight(+1) to indicate that the left subtree is higher than the right subtree.
• EH for even high(0) to indicate that the subtrees are the same height, and
• RH for right high(-1) to indicate that the left subtree is shorter than the right subtree.

Example of an AVL tree



Balancing Trees
Whenever we insert or delete a node the tree is unbalance. To make it balance we have to perform the rotations either to the left or to the right.

There are four cases required to rebalance the tree they are:

1. Left of Left
2. Right of Right
3. Right of left
4. Left of right

Left of Left - Single Rotation right:

Right of Right - Single Rotation Left:

Right of Left - Double Rotation Right:

Left of Right - Double Rotation Right:

AVL tree Implementation

AVL Tree Insert:

AVL Tree Left Balance:

Rotate AVL Tree Right and Left:

AVL Tree delete: