Inserting

ADT

The method description from the ADT.

insert(insertIndex, newElem);
	/*
	Shift to the right the element currently at "insertIndex" (if any) and all elements to the right
	Insert passed arg "newElem" into position "insertIndex"
	Valid "insertIndex" values are between 0 and "size"
	If index = "size" then it becomes a simple "add" operation
	If "insertIndex" is invalid, throws exception:
		"(insert) Index %d is out of bounds"
	*/

Finding the Insertion Point

We want to find the existing node (insertion point) where we will insert a new node.

We can mimic what we did for "get" and "set" for finding a node at a given index.

We can copy and tweak the algorithm from either of those methods.

Insert Schematic

With the insertion point (existing node) from the previous step, we can now perform the insert. We are inserting -- not replacing any data.

The red shows "work" needed to insert a new node into the list.

Create new node and give it the data (object)
Do housekeeping on links as shown (similar to our previous algorithms for "addFirst" or "addLast")
Increment list size

O(n) or O(1)?

Is this algorithm O(n) or O(1)?

Unfortunately, it is "O(n)".

The reason is that finding the node is O(n) and the actual insertion operation is O(1). The less efficient level "O(n)" governs.