java - Removing duplicates from one list by comparing with another list -

i have 2 lists of objects , remove instances 1 list there in other list.

e.g. have following 2 lists , suppose each letter represents object.

list lista = {a, b, c , d, e, f, g, h , , j}

list listb= {d, g, k, p, z}

now, listb has d , g there on lista want lista

lista = {a, b, c , e, f, h , , j}

can guys please suggest solution o(n) or less o(n2).

i can iterate on both lists , remove duplicate instances comparing want have more efficient.

if lists unsorted, , arraylists or other similar list implementations o(n) contains method, should create hashset items of listb in order perform removal. if items not put set end o(n^2) performance.

easiest way need thus:

lista.removeall(new hashset(listb)); 

arraylist.removeall(collection) not put items set (at least in jdk 1.6 , 1.7 versions checked), why need create hashset in above.

the removeall method copy items wish keep beginning of list traverses it, avoiding array compacting each removal, using against passed in hashset shown reasonably optimal , o(n).