The list you are talking about only contains the very recently added TEs, all others are being retrieved through 2 HashMap lookups (one to get the Chunk, one to get the TE in there).
While a HashMap is fairly quick, it'll still take a lot longer than a direct array/field access. You are supposed to use an array like TileEntity[6], one entry for each direction, to cache the neighbor TEs, not another HashMap. Be aware of annoying and random side effects due to out of date caches though.