Java BigO notation and LinkedList I have a Linked List the J

Java Big-O notation and LinkedList

I have a Linked List (the Java defined class) Declare an iterator. Remove the first and last nodes. LinkedList aList; What is the Big O notation, the worst case performance, of the code you wrote in part 6a?/How could I modify my code to make the performance more efficient (or what knowledge would I need ahead of time). What would my performance be if I had to iterate through my Linked List in two nested for loops?

Solution

A) ListIterator<Integer> listIterator = linkedList.listIterator();

while (listIterator.hasNext()) {

System.out.println(listIterator.next());

}
use the next() to iterate through the list, then use remove() to remove item from the list
listIterator.remove();

B) Since, we are iterating through the whole list to remove the last item, the complexity of this process becomes O(n) if the list contains n items.
In the given question we need to remove the first and the last element from the list, if maintain/store a Head and a Tail position in the LinkedList we can easily remove the first and the last item from the list as we already know the address of both the elements, thh complexity of this method would be O(1).
Iterating on a list with two nested for loops would cause both the loops to run for n times which results in O(n²) time, but since the LinkedList is a linear non-contigous data structure we don\'t need two for loops to traverse it, only one for loop would suffice.