Um Array é uma estrutura de dados que consiste de uma sequência de elementos em ordem na memória. Sua representação é algo como a seguinte tabela:

Declarando um Array

A declaração de um Array em JavaScript (linguagem que estaremos usando) é definida usando colchetes. Para representarmos o Array do exemplo acima, podemos definir algo como:

lista = ["Maçã", "Banana", "Pera"]

Funções de um Array

Os Arrays possuem quatro funções principais. Estas são:

• lookup() → O(1)

• push() → O(1)

• pop() → O(1)

• insert() → O(n)

• delete() → O(n)

1. lookup

O lookup possui complexidade temporal de O(1), e serve para pegarmos um ítem do Array pelo seu índice. Supondo que queremos saber qual é o item na posição 1 do nosso lista , podemos fazer o seguinte:

lista[1]

Isto irá retornar "Banana", item que está no índice 1 de nossa lista (lembrando que os índices de Arrays começam em 0 na maioria das linguagens).

2. push

A função push insere um elemento no final do array. Sendo assim, é uma operação instantânea de O(1). Supondo que queremos adicionar uma nova fruta em nossa lista; podemos fazer isso com:

lista.push("Manga")

Isso adiciona este elemento no final de nossa lista, transformando-a em:

[0123|"Maçã""Banana""Pera"

"Manga"]

Tente verificar o índice 3 usando o lookup agora em nossa lista. É garantido que ele irá retornar "Manga" .

3. pop

A função pop realiza o oposto do push, ao invés de adicionar o elemento ao fim do array, ele remove o último. Sendo assim é O(1). Supondo que ainda tenhamos a seguinte lista:

[0123|"Maçã""Banana""Pera"

"Manga"]

Se executarmos lista.pop() , o elemento do índice 3 - que é o último - será removido:

4. insert

A função insert adiciona um elemento no meio do array. Ela recebe dois parâmetros: índice de início e o que adicionar.

Note que a função insert não existe no JavaScript, sendo nomeada de splice que recebe três parâmetros: índice de início, o que remover e o que adicionar.

Supondo que temos nossa lista de frutas mencionada no começo do estudo, vamos imaginar que queremos adicionar "melancia" como segundo elemento. Podemos fazer isso com:

lista.insert(2,"Melancia")

Assim transformando a lista de:

Em:

Note que para esta função funcionar, devemos contar quantos índices andar do primeiro parâmetro recebido, para assim montarmos outro array, colocarmos o item com push() e depois dar push() nos outros elementos.

Veja o seguinte trem de pensamento:

Executamos lista.insert(2,"Melancia") , assim iteramos a quantidade de índices e anexamos ela a uma nova sublista. Podemos fazer isso com:

sublista1 = []
for(var i = 0; var < indice; i++) {
   sublista1.push(lista[i])
}

Assim resultando em:

Sublista:

Então, Melancia é adicionada com sublista.push("Melancia"), resultando em:

[01

2|"Maçã""Banana""Melancia"]

Então, podemos prosseguir da quantidade total dos índices da sublista1 para cima da lista original, incrementando o índice para pegar todos os outros elementos:

for(var y = indice; y < lista.length; y++) {
   sublista.push(lista[y])
}

Enfim retornando a sublista1 como resultado:

[01

23|"Maçã""Banana""Melancia"

"Pera"]

Como demonstrado, esta operação é uma operação de O(n).

5. delete

Assim como a função insert(), a operação delete também segue efetivamente a mesma lógica que a insert, mas realizando seu oposto, removendo um elemento presente do array dado um certo índice.

Em JavaScript, isso também é dado com a função splice nativa.

Poderiamos implementar um delete da seguinte maneira:

lista.delete(1)

Assim transformando a lista de:

Em:

Isto pode ser feito seguindo basicamente a mesma lógica que o insert, porém ignorando o elemento do indice passado e não adicionando nenhum elemento:

function remove(list, index) {
    let sublista = []
    for(let x = 0; x < index; x++) {
        sublista.push(list[x])
    }

    for(let y = index + 1; y < list.length; y++) {
        sublista.push(lista[y])
    }
    return sublista
}

Exercicio

Implemente uma função pushFirst() que adiciona um elemento no início de um array recebido. Não é permitido usar a função unshift() do Javascript. Esta função deve receber lista e valor.