0

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?

shmosel
  • 49,289
  • 6
  • 73
  • 138
James Richard Lee
  • 71
  • 7

4 Answers4

1

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/

SomeStudent
  • 2,856
  • 1
  • 22
  • 36
  • Good point on resizing when the max size is reached. I get your point in saying the look up time is O(1) in an arraylist and O(n) for a linked list in terms of memory access when you want to get i-th element. However it might be a bit confusing as worded. I initially thought you meant when looking for a particular object in the list in which case both would be O(n) (though due to memory block access the array list will be faster). – Aaron Davis Mar 09 '17 at 04:56
  • I of course can't really comment too much on the confusion aspect since I mean I wrote it lol. But I will try to keep that in mind. If you have any edit suggestions let me know :) and yes, for a particular object when you don't know its index, it is O(n) for both; but for a known index it is still O(n) for LL, and O(1) for AL as an AL uses an array under the hood. – SomeStudent Mar 09 '17 at 06:07
1

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.

Rajesh Navagare
  • 47
  • 9
1

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).

Abhimanoj Yadav
  • 23
  • 4
0

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.

Aaron Davis
  • 1,731
  • 10
  • 13