title: Combining like items in a List
body: <p>I saw an <strong><a href="https://stackoverflow.com/questions/5370294/how-to-merge-similiar-items-in-a-list">earlier post</a></strong> which is trying to do a similar sort of thing in Python.</p>
  
  <p>Here is a boiled down example of what I want.  Let us say I have List.</p>
  
  <pre><code>public class MyObject {
      private String purchase;
      private Double price;
  }
  </code></pre>
  
  <p>Let us say that a typical <code>List&lt;MyObject&gt;</code> will hold:</p>
  
  <pre><code>Bike 95.00
  Clothes 24.99
  Clothes 10.76
  Food 6.35
  Food 91.46
  </code></pre>
  
  <p>I want all of the items with same purchase value to be combined into a single item with the price summed for that item.  For example, clothes would be a single item with price 35.75 (if I have done the addition correctly).</p>
  
  <p>The way I thought about doing it was:</p>
  
  <ol>
  <li><code>Collections.sort</code> the list by purchase for O(n log n)</li>
  <li>Walk the sorted list (it is an <code>ArrayList</code> I am using) as same items will be consecutive and perform a merge on 2 items at a time O(n)</li>
  </ol>
  
  <p>Giving a total runtime of O(n log n).</p>
  
  <p>Now that sounds reasonable to me, however is there a library out there which at the very least beats the pants of my constants?  I always support going with a streamlined version if one exists.  So are there any existing implementations that I should think about using or improvements over my algorithm?</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>After thinking about my boiled down case as I went home yesterday, yes I easily saw it is a map.  All I had to do is reduce it to the simpler problem I posted and it became very obvious.  My real structure is</p>
  
  <pre><code>public class MyObject {
     Map bucketOfStuff;
  }
  </code></pre>
  
  <p>In reality, bucketOfStuff is really <code>Map&lt;String, Object&gt;</code> where sometimes the value is a String and sometimes the value is a Double (it can also be an Integer sometimes, but hey I can treat it as double).  For all of the objects which are of type String, they would be used to form the key in this problem.  So If I had</p>
  
  <ul>
  <li>color => Red </li>
  <li>size => Small</li>
  <li>texture => Smooth</li>
  </ul>
  
  <p>Then I could encode all into a single String such as <code>Red,Small,Smooth</code> because I know comma will not be a character present in any of the values so I can use it as a delimiter.</p>
  
  <p>For the value for our hypothetical new Map, it would be List because I have to perform (mathematical) vector addition on all of the <code>bucketOfStuff</code> values which are doubles.  So the proposed new Map would either be <code>Map&lt;List&lt;String&gt;, List&lt;Double&gt;&gt;</code> or simply <code>Map&lt;String, List&lt;Double&gt;&gt;</code> if I used the delimiter as above.</p>
  
  <p>Another thing which corrupted my thought process is that in the end the collection has to be a List to pass on so I was in a narrow-minded way thinking List all the way. So I have to be able to reconstruct the original object which is a bit involved, but not impossible.  Thanks all for the help and nice catch.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>I have to modify my description slightly because I just recalled that I should maintain the original ordering of the <code>List&lt;MyObject&gt;</code>, therefore my original solution would have been incorrect anyway since I was doing the sort.  Because of this, I shall continue to follow the path of assistance offered and use a <code>LinkedHashMap&lt;String, List&lt;Double&gt;&gt;</code>.  Coming from <a href="http://download.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html" rel="nofollow noreferrer">Java 6 API</a> "This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order)".</p>