Quando alguém disser o que deve fazer, peça justificativa.
Iteração
Iterar qualquer estrutura de dados com um conjunto de dados não tem problema algum, na forma geral.
Se quer iterar de forma específica, em uma estrutura específica, e quer um resultado específico, aí pode ter um problema.
Essencialmente todas as estruturas de dados básicas podem ser iteradas em complexidade linear O(n). Só não seria assim alguma estrutura bem complexa e muito específica que praticamente ninguém usa. Em geral não consegue fazer em menos tempo que isso, e não levará mais. Tanto que ninguém coloca qual é a complexidade para este algoritmo, ela é "sempre" igual.
Você quer iterar em alguma ordem específica? Precisa ser na ordem que os elementos foram inseridos? Ou precisa uma classificação específica? Se precisar de algo assim é melhor usar outra estrutura, se puder. Mapas geralmente não possuem ordem definida. Até existem implementações que permitem ordem, mas só podem ser usados em circunstâncias específicas, a maioria dos mapas usam tabelas de espalhamento, que não permitem ordem.
Alternativas
Se precisa da ordem use um array ou estrutura baseada nele. É ótimo na imensa maioria das necessidades.
Se precisa dos dados classificados então deve ser mais interessante usar uma árvore, que é uma lista ligada que tem mais de um caminho para seguir na sequência.
É muito raro a lista ligada pura ser útil, em geral só quando ela não precisa ser manipulada depois de criada, a não ser na(s) ponta(s) e também não precisa de acesso aleatório, o que faz com que outras estruturas também sejam adequadas.
Listas ligadas, como se aprende no curso de computação, essencialmente não são usadas no "mundo real". Implementações mais sofisticadas, provavelmente combinadas com outras estruturas, podem ser úteis em certos cenários.
É muito comum as pessoas acharem que inserir e remover um elemento de uma lista ligada pode ser feito em complexidade constante, porque a operação em si realmente é constante. Porém quase sempre precisa chegar no ponto onde o elemento será inserido ou removido, e aí a complexidade é linear.
Eu devo ser uma das poucas pessoas que usam lista ligada em banco de dados em certa circunstância. Usei onde me deu alguma vantagem sobre o índice normal que o DB já possui. Embora hoje é raro eu ter esta necessidade. Tem que pesar tudo para decidir qual é a melhor estrutura.
Não avalie errado
Eu já vi gente transformar um array em mapa para poder indexar em tempo constante em vez de linear. Não digo que isto seja inútil em todos os casos, mas quase sempre a complexidade passou ser O(n + k) no melhor caso, ou seja só desvantagem. A pessoa esquece de contar o tempo da cópia da estrutura. Se tivesse feito no array seria O(n) no pior caso e O(1) no melhor.
Talvez o seu problema seja mais adequado para uma lista ligada, mas não sabemos ao certo qual seria esse problema. Pode ser que precise o uso conjunto de mais de uma estrutura, e uma delas seja uma lista ligada (talvez não tradicional).
Coloquei no GitHub para referência futura.