CODEWITHSUNDEEP
javadata-structures
James Richard Lee
James Richard Lee

Reputation: 71

why the running time of the LinkedList and the ArrayList are not the same

I am studying data structures and algorithm in Java and I cannot understand this part of the book.

Here is what is written on the book:

On the other hand, if we construct a List by adding items at the front,

 public static void makeList2( List<Integer> lst, int N )
     {
         lst.clear( );
         for( int i = 0; i < N; i++ )
             lst.add( 0, i );
}

the running time is O(N) for a LinkedList, but O(N2) for an ArrayList, because in an ArrayList, adding at the front is an O(N) operation.

And my question is that I cannot understand why the running time is different? And why in the ArrayList, adding at the front is an O(N) operation?

Upvotes: 0

Views: 1585

Answers (4)

Abhimanoj Yadav
Abhimanoj Yadav

Reputation: 23

1) ArrayList get(int index) operation runs in constant time O(1) while LinkedList get(int index) operation run time is O(n) .

The reason behind ArrayList being faster than LinkedList is that ArrayList uses index based system for its elements as it internally uses array data structure , on the other hand , LinkedList does not provide index based access for its elements as it iterates either from the beginning or end (whichever is closer) to retrieve the node at the specified element index.

2) insert() or add(Object) operation : Insertions in LinkedList are generally fast as compare to ArrayList.

In LinkedList adding or insertion is O(1) operation . While in ArrayList, if array is full i.e worst case, there is extra cost of resizing array and copying elements to the new array , which makes runtime of add operation in ArrayList O(n) , otherwise it is O(1) .

3) remove(int) operation : Remove operation in LinkedList is generally same as ArrayList i.e. O(n). In LinkedList , there are two overloaded remove methods. one is remove() without any parameter which removes the head of the list and runs in constant time O(1) . The other overloaded remove method in LinkedList is remove(int) or remove(Object) which removes the Object or int passed as parameter . This method traverses the LinkedList until it found the Object and unlink it from the original list . Hence this method run time is O(n).

While in ArrayList remove(int) method involves copying elements from old array to new updated array , hence its run time is O(n).

Upvotes: 1

Rajesh Navagare
Rajesh Navagare

Reputation: 47

Retrieval operation of ArrayList is faster than LinkedList whereas insert,delete,update operation of LinkedList are faster than ArrayList. There is specific reason for it. ArrayList is kind of list in which objects are stored in next to each other in memory s when one of them is changed, new ArrayList is created and all elements are copied whereas it is easy to traverse ArrayList easily. Now when we talk about LinkedList, they are not stored in heap in heap in continuous manner ut they hold address of next and previous objects so when we do changes, it just change referring address of next and previous objects. And so retrieval is time consuming as compared to ArrayList as it tracks through address to find n'th index element.

Upvotes: 1

SomeStudent
SomeStudent

Reputation: 3048

The answer lies in the names. LinkedList vs. ARRAYList. Since a LinkedList is a dynamic structure which maintains a tail (can also contain a head pointer) pointer each time you want to add to the tail it is a simple matter of setting a few new values and set the tail pointer to the newly added value.

With an array list, as Aaron Davis mentioned, you must shift all of the values. Another thing to keep in mind, is that an array is a limited size structure, so each time you hit its max you need to resize it which takes time. For these reasons LinkedLists are better with addition. However, because an array list uses an array under its hood, it will be faster in terms of look up as it is a continuous block of memory rather than a collection of different pointers. As such look up in an array list is O(1), whilst LinkedList is O(n)

Here's a very useful link describing the difference between the two: http://beginnersbook.com/2013/12/difference-between-arraylist-and-linkedlist-in-java/

Upvotes: 1

Aaron Davis
Aaron Davis

Reputation: 1731

With a linked list you just alter the head pointer to the new node when you insert at the front of the list. With an array list you have to move every element in the array each time you insert at the front of the list.

Upvotes: 0

Related Questions