>Mas afinal de contas, o que é um *array*? É uma lista indexada sequencialmente? Ou é um *container* de itens indexados manualmente (como no PHP)?

Formalmente qualquer coisa que não seja uma sequência única e contínua de valores não é um *array*.

Continue usando o termo que todo mundo da comunidade da tecnologia usa.

Cada tecnologia pode dar o nome que quiser para cada elemento dela. Isso não quer dizer que formalmente seja correto na computação, ou mesmo na matemática já que a computação é uma aplicação específica da matemática.

>Seria correto afirmar que o conceito de *array* da linguagem PHP está errado? Se está "errado", qual seria o nome mais apropriado para o "array" dessa linguagem?

É difícil afirmar isso concretamente.

PHP possui uma estrutura com elementos esparsos e seu acesso feito por uma chave que não é a posição do elemento na sequência. Pelo menos ele chama de [***array* associativo**][1] e provavelmente *array* é só uma forma encurtada. Se prestar atenção na documentação é dito que é um *array* associativo apesar de usar o termo `Array` na sintaxe.

Grosso modo ele é o mesmo que uma tabela *hash*. Não precisa chamar de *hash table*, inclusive porque isso pode ser só detalhe de implementação. Algumas pessoas chamam isso de mapa ou dicionário.

Está longe do ideal em performance, mas como é para executar *scripts* nada muito problemático. Tanto *array* quanto *hash table* possuem complexidade O(1), mas o *array* faz uma aritmética simples de ponteiro, uma tabela *hash* precisa de uma aritmética mais complexa e em alguns casos a complexidade da fórmula pode ser O(n) em relação ao tamanho do objeto que serve de chave.

Da mesma forma que se fala em *hash* quando na verdade está se falando *hash table*. Ou quando usa lista para lista ligada. Então dependendo de onde olhar algo pode parecer errado, tem lugar que classificam aquilo da maneira certa, sem simplificação.

>Lista e *array* é a mesma coisa? Se não, qual é a diferença?

Lista é um conjunto de valores que possuem uma certa sequência, mas a forma exata de organização na memória e acesso a ela não é definido. Uma lista deve aceitar novos elementos. Um *array* não costuma aceitar.

Embora o nome *array* possa ser usado existem nomes mais específicos para estruturas de dados mais específicas, exceto para o vetor mais puro. Lista pode ser usado assim livremente, mas dependendo de como ela é implementada ela pode ter um nome mais específico.

Veja https://pt.stackoverflow.com/q/124849/101.

[Coloquei no **GitHub** para referência futura][2].


  [1]: https://pt.stackoverflow.com/q/429851/101
  [2]: https://github.com/maniero/SOpt/blob/master/Conceptual.md