Qual é a medida de complexidade do algoritmo para adicionar um elemento ao início de uma lista duplamente ligada?

A adição de um elemento ao início de uma lista duplamente ligada é feita em tempo constante, ou seja, tem complexidade O(1).

Isto deve-se ao facto de uma lista duplamente ligada ter um ponteiro para o primeiro elemento (cabeça), e para inserir um novo elemento basta:

1. Criar um novo nó.
2. Definir o seu ponteiro next para o elemento atual em cabeça.
3. Definir o ponteiro prev do elemento atual em cabeça para o novo nó.
4. Atualizar o ponteiro da cabeça da lista para o novo nó.

Todas estas operações não dependem do tamanho da lista, por isso a complexidade — O(1).