• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            copied from Pankaj Kumar's Weblog


            The trade-offs in using java.util.ArrayList and java.util.LinkedList should be straight-forward, shouldn't it? At least this is what I used to think till today. But then most of my thinking around these datastructures were formed during college days, when C was the hottest language and Java and its Collection classes just didn't exist.

            Not surprisingly, it is natural for me to think of arrays as fixed size containers, where elements can be accessed at random location through O(1) operation (ie; in constant time) and insertion/deletion in the middle are O(N) operations (ie; could take time proportional to the size of the array) and hence, are better avoided. In contrast, a linked list can grow in size, access of its head or tail and insertion/deletion in the middle are all O(1) operations (assuming that you have pointer to an adjacent element).

            It is possible get around the fixed size limitation of arrays by writing a wrapper which will allocate a new array, copy the elements of the old array into the new one and then discard the old one (BTW, this is what ArrayList does). Still, the basic arrays remain a datastructure for collections of fixed size. In contrast, a linked list consists of nodes with 'pointers' to the next and previous node in the list. So, adding or removing a node is simply a matter of reassigning the pointers. Of course, this implies linear time for traversing upto an indexed node, starting from beginning or end. This simple model is very handy in deciding when to use an array and when to use a linked list.

            In Java, the ArrayList and LinkedList classes provide a uniform interface to both these datastructures and hence, destroy this simple conceptual model, so necessary to make judicious implementation decisions, in impressionable young minds of many Java programmers. Let me further elaborate this with my recent own experience.

            Today, while going over a graph traversal code, I was somewhat alarmed by the generous use of ArrayLists. This code was written by someone who perhaps had learnt programming with Java. As hinted earlier, both ArrayList and LinkedList implement List interface and support similar operations. An ArrayList can grow dynamically and allows insertion/deletion of elements. A LinkedList also allows access of elements through an index, exactly the same way as an ArrayList. This is all fine. However, the problem is that the apparent similarity in the API hides the widely different memory and time costs of these datastructures for different kinds of operations, luring the unwary to use them in dangerous ways:

            1. An empty ArrayList takes two to three times more memory than an empty LinkedList (because ArrayList would typically preallocate memory). This becomes important if you plan to keep an adjacency list of nodes for each node in the graph and you know beforehand that the nodes will have at most one or two adjacent nodes and the total number of nodes in the graph can be quite large.

            2. The following straight-forward loop to iterate over all elements of a list


              ??for (int i = 0; i < list.size(); i++)
              ????doSomething(list.get(i));


              works great for an ArrayList but will cause serious performance problems for a LinkedList. Can you guess why? The right way to iterate over a LinkedList is:


              ??ListIterator li = list.listIterator(0);
              ??while (li.hasNext())
              ????doSomething(li.next());


            3. Although both ArrayList and LinkedList allow insertion/deletion in the middle through similar operations (ie; by invoking add(int index) or remove(index)), these operations do not offer you the advantage of O(1) insertion/deletion for a LinkedList. For that, you must work through a ListIterator.

            While researching on this topic, I did find a couple of good articles on the Web:


            • JDC Tech Tip article on Using ArrayList/LinkedList. Good coverage of the topic. Worth reading if you want to know more about performance tradeoffs.
            • joustlog entry titled LinkedList vs. ArrayList performance tests and subsequent clarification. This entry is more focussed in scope, pointing out the fact that addition as the end is faster for ArrayList than for LinkedList. The only thing I would like to add is that addition at the end of a LinkedList is always O(1) whereas addition at the end of an ArrayList is amortized O(1), meaning if you do M at-the-end additions then the total cost will be proportional to M. This is due to the fact that the underlying array may have to be grown (a new one to be allocated, old one to be copied and discarded) when the capacity is reached. However, I can understand that a normal at-the-end addition (ie; not involving resizing of the underlying array) will be faster for ArrayList (compared to LinkedList).

            I am not advocating either ArrayList or LinkedList, though it can be justifiably argued that the use of ArrayList is better suited in many more programming scenarios, and I have no contention with that. The point I am making is that the sameness of the API makes it easy for programmers to assume that these can be used interchangeably. Nothing can be farther from truth. They are distinct datastructures, each optimized for certain kinds of operations and domain of applicability. And a good programmer should be aware of the distinction. The API exposed by the above mentioned Java classes blur this distinction. In my opinion, this is one of those areas where implementation hiding behind a common, easy-to-use interface (think of List interface that both ArrayList and LinkedList implement) may not be in the best interest of the primary user of these classes.

            国产激情久久久久影院| 国产成人无码精品久久久性色| 久久久精品国产sm调教网站| av无码久久久久久不卡网站| 久久综合欧美成人| 国产一区二区久久久| 国产精品一久久香蕉产线看| 久久黄色视频| 久久亚洲精品无码AV红樱桃| 国产精品99久久久久久董美香 | 久久九九久精品国产免费直播| 麻豆久久久9性大片| 国产成人久久精品一区二区三区 | 91精品国产高清久久久久久io| 国产精品一区二区久久精品无码 | 精品久久国产一区二区三区香蕉 | 国产精品美女久久久网AV| 亚洲精品无码久久千人斩| 国产高潮久久免费观看| 国产亚洲美女精品久久久久狼| 亚洲国产成人精品女人久久久 | 99麻豆久久久国产精品免费| 亚洲国产精品狼友中文久久久| 久久成人影院精品777| 色欲久久久天天天综合网精品| 色综合合久久天天给综看| 久久综合久久久| 久久青草国产手机看片福利盒子| 少妇久久久久久久久久| 久久精品成人欧美大片| 精产国品久久一二三产区区别| 亚洲国产日韩欧美久久| 久久精品人妻一区二区三区| 国产福利电影一区二区三区,免费久久久久久久精 | 久久99国产综合精品| 亚洲级αV无码毛片久久精品| 婷婷久久五月天| 久久狠狠爱亚洲综合影院 | 色综合久久综精品| 伊人久久综在合线亚洲2019 | 亚洲精品白浆高清久久久久久|