Quick Index
' Algorithm "size"'


ADT


ADT
The ADT defines "size" as follows:
size();
	/*
	Return number of elements in this list.
	*/


Algorithm


In this algorithm we keep "size" in an instance variable.

This is a much more efficient algorithm. No iteration is necessary.

However, it does require that we properly adjust the ivar in when adding, inerting and removing elements.

The algorithm would then just be something like:

size() {
	//Return the instance variable
	return this.getSize();
}

Alternative Algorithm


This is an alternative algorithm. But why would we ever want an alternative algorithm? There may be cases (during coding) when we want to do cross-checks on "size()". Thus, we could name this alternative something like "size2()", and use it only for that purpose.

Recall the algorithm we learned in Traversal. We'll copy and modify it to compute size as is shown below.

Traversal Algorithm Modified to Compute Linked List Size
count = 0
node = this.firstNode
While node is not null
	Increment count
	node = node.getNextNode()
Return count


' Algorithm "isEmpty"'


The ADT defines the method "isEmpty" as: Return true is this list contains no elements.

We can simply return true if "size()" returns zero (0).





























Data Structures And Algorithms (DSA) (Chapter 401 - Linked List Logic)










Chapter 401 - Linked List Logic Stats

Contents Intro OO Review Concepts Design Traversal Algorithms Memory

Chapter Top Search TOC