Time Complexity while deleting last element from arraylist and linkedlist

Question

1st Part :-

I was reading in the book - "Data Structure and Algorithms made easy in Java" that the time complexity for deleting the last element from Linkedlist and Arraylist is O(n). But the Linkedlist internally implements DoublyLinkedlist so the time complexity should be O(1) and similarly for Arraylist as it internally implement Array it should be O(1).

2nd Part :-

It also says that the insertion of an element at the ending of a linkedlist has a time complexity of O(n) but the linkedlist maintains pointers both at the end and at the front. So it this statement correct ? Moreover it says that the time complexity to insert an element in an arraylist at the end is O(1) if array is not full and O(n) if the array is full. Why O(n) if the array is full ?

Thanks for answering the 1st part . Can anyone please also explain the 2nd part. Thanks :)

The book is wrong, you are correct. 16% of reviews on Amazon say the book has lots of errors, and give it one or two stars. I think it's a good time to get yourself a better book. — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Mar 31, 2017 at 16:24
Is the book referring to the java.util classes with those names, or data structures of the same name but a different implementation provided in the book? — Andy Thomas
– Andy Thomas, Commented Mar 31, 2017 at 17:05

Andy Thomas · Accepted Answer · 2017-03-31 16:39:41Z

36

It depends on what methods you're calling.

A glance at the implementation shows that if you're calling LinkedList.removeLast(), that's O(1). The LinkedList maintains pointers both to the first and last node in the list. So it doesn't have to traverse the list to get to the last node.

Calling LinkedList.remove(index) with the index of the last element is also O(1), because it traverses the list from the closest end. [Noted by user @andreas in comment below.]

But if you're calling LinkedList.remove(Object), then there's an O(n) search for the first matching node.

Similarly, for ArrayList, if you're calling ArrayList.remove(index) with the index of the last element, then that's O(1). For all other indices, there's a System.arrayCopy() call that can be O(n) -- but that's skipped entirely for the last element.

But if you call ArrayList.remove(Object), then again there's an O(n) search for the first matching node.

edited Mar 31, 2017 at 16:39

answered Mar 31, 2017 at 16:27

Andy Thomas

86.8k12 gold badges111 silver badges160 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Andreas Over a year ago

Even linkedList.remove(lastIndex) is O(1), since LinkedList will search backwards for the index: Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Andy Thomas Over a year ago

@Andreas: Good point; added in answer above, with attribution.

user3747182 Over a year ago

@AndyThomas Can u plz also explain the 2nd part of my question. Thanks

Andy Thomas Over a year ago

@user3747182 - For your second question, inserting at the end of a java.util.LinkedList is O(1). Inserting at the end of an ArrayList can be O(n) because if the underlying array is full, its contents must be copied in O(n) to a new, larger array [see ArrayList.grow(minCapacity)]. ... By the way, I see that you have asked six questions but not accepted any answers. You can accept one answer to a question by clicking the checkmark to the left. You can vote for any number of answers by clicking the up-arrow to the left.

Collectives™ on Stack Overflow

Time Complexity while deleting last element from arraylist and linkedlist

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related