java - List of string with occurrences count and sort -

i'm developing java application reads lot of strings data likes this:

1 cat (first read) 2 dog 3 fish 4 dog 5 fish 6 dog 7 dog 8 cat 9 horse ...(last read) 

i need way keep couple [string, occurrences] in order last read first read.

string   occurrences
horse     1 (first print)
cat         2
dog        4
fish        2 (last print)

actually use 2 list:
1) list<string> input; add data
in example:

input.add("cat"); input.add("dog"); input.add("fish"); ... 

2)list<string> possibilities; insert strings once in way:

if(possibilities.contains("cat")){     possibilities.remove("cat"); } possibilities.add("cat"); 

in way i've got sorted list possibilities. use that:

int occurrence; for(string possible:possibilities){     occurrence = collections.frequency(input, possible);     system.out.println(possible + " " + occurrence); } 

that trick works it's slow(i've got millions of input)... help?
(english isn’t first language, please excuse mistakes.)

use map<string, integer>, @radoslaw pointed, keep insertion sorting use linkedhashmap , not treemap described here:

linkedhashmap keeps keys in order inserted, while treemap kept sorted via comparator or natural comparable ordering of elements.

imagine have strings in array, call listofallstrings, iterate on array , use string key in map, if not exists, put in map, if exists, sum 1 actual result...

map<string, integer> results = new linkedhashmap<string, integer>(); (string s : listofallstrings) {     if (results.get(s) != null) {         results.put(s, results.get(s) + 1);     } else {         results.put(s, 1);     } }