Quick Index
Algorithm for 'removeFirst'


Before
We are about to remove the first node (BP)
After
The red shows the little bit of work to do in the algorithm.

In the algorithm, we'll also remember to decrement list size
Efficiency Compared to DynamicList
How does this algorithm's Big-O efficiency compare to that for DynamicList?



More efficient.

This algorithm has constant performance "O(1)".

Recall that a DynamicArray needs to do a full "shift" when removing the first element.


Algorithm for 'removeIndex'


The algorithm for "removeIndex(index)" could mimic the algorithm for "insert(insertIndex, newElem);" except that we would want to remove the selected node and adjust the links of the preserved nodes as needed.

We'll also want to decrement list size rather than increment.

Algorithm for 'removeLast'


The algorithm for "removeLast" is similar to "removeFirst". The only differences are that we do the link housekeeping appropriate for the end of the list.

Algorithm for 'removeAll'


ADT Method Description


 
 		

removeAll();
	/*
	Reset the list so it is empty.
	If list is already empty, then do nothing
	No action need be performed on individual elements.
	*/



 
 	
 


 	
 		
How Do We Reset the List?
 		
How do reset the list so that it is empty?
 		





We do the following:



Set "this.firstNode" to null

Set "this.lastNode" to null



Note -- if we have included other ivars in our object design, we would need to reset them as well.
 	
 





























































		

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

		

		









		

		Chapter 401 - Linked List Logic
Removing

		

		

		Contents
Intro
OO Review
Concepts
Design
Traversal
Algorithms
Memory

		

		

		Chapter
Top
Search
TOC