LinkedList
LinkedList<T> implementa uma lista encadeada simples com inserção e remoção O(1) na frente.
Construção
| Sintaxe | Descrição |
|---|---|
LinkedList<T>() | Cria uma nova lista encadeada vazia |
LinkedList.fromArray(arr) | Cria uma lista encadeada com os elementos de arr em ordem |
O parâmetro de tipo T determina o tipo do elemento. T pode ser um tipo de valor escalar (boolean, char, inteiro ou float); valores possuídos pelo heap, como string, não são suportados.
Métodos
| Método | Assinatura | Retorno | Descrição |
|---|---|---|---|
pushFront | (T) => void | void | Adiciona um elemento à frente |
pushBack | (T) => void | void | Adiciona um elemento ao final |
popFront | () => T? | T? | Remove e retorna o elemento da frente, ou vazio se vazia |
popBack | () => T? | T? | Remove e retorna o elemento do final, ou vazio se vazia |
front | () => T? | T? | Retorna o elemento da frente sem removê-lo, ou vazio se vazia |
back | () => T? | T? | Retorna o elemento do final sem removê-lo, ou vazio se vazia |
len | () => usize | usize | Número de elementos |
isEmpty | () => boolean | boolean | Se a lista não tem elementos |
clear | () => void | void | Remove todos os elementos |
popFront, popBack, front e back retornam T?, chame com uma checagem de presença ou valor padrão.
Complexidade
| Operação | Complexidade de Tempo |
|---|---|
pushFront | O(1) |
pushBack | O(n) |
popFront | O(1) |
popBack | O(n) |
front | O(1) |
back | O(n) |
len | O(1) |
isEmpty | O(1) |
clear | O(n) |
Exemplos
Construção
tyrus
import { LinkedList } from "tyrus:algorithm";
const ll = LinkedList<i32>();pushFront e pushBack
tyrus
const ll = LinkedList<i32>();
ll.pushFront(1);
ll.pushBack(2);
ll.pushBack(3);
print(ll.len()); // 3front e back
tyrus
const ll = LinkedList<i32>();
ll.pushBack(10);
ll.pushBack(20);
const f: i32? = ll.front();
if (f) {
print(f); // 10
}
const b: i32? = ll.back();
if (b) {
print(b); // 20
}popFront
tyrus
const ll = LinkedList<i32>();
ll.pushBack(1);
ll.pushBack(2);
ll.pushBack(3);
const p1: i32? = ll.popFront();
if (p1) {
print(p1); // 1
}
const p2: i32? = ll.popFront();
if (p2) {
print(p2); // 2
}
print(ll.len()); // 1popBack
tyrus
const ll = LinkedList<i32>();
ll.pushBack(1);
ll.pushBack(2);
ll.pushBack(3);
const p: i32? = ll.popBack();
if (p) {
print(p); // 3
}
print(ll.len()); // 2len
tyrus
const ll = LinkedList<i32>();
print(ll.len()); // 0
ll.pushBack(1);
ll.pushFront(2);
print(ll.len()); // 2isEmpty
tyrus
const ll = LinkedList<i32>();
print(ll.isEmpty()); // true
ll.pushBack(1);
print(ll.isEmpty()); // falseclear
tyrus
const ll = LinkedList<i32>();
ll.pushBack(1);
ll.pushBack(2);
ll.pushBack(3);
print(ll.len()); // 3
ll.clear();
print(ll.isEmpty()); // true
print(ll.len()); // 0fromArray
tyrus
const vals: i32[] = [7, 8, 9];
const ll = LinkedList.fromArray(vals);
print(ll.len()); // 3
const f: i32? = ll.front();
if (f) {
print(f); // 7
}
const b: i32? = ll.back();
if (b) {
print(b); // 9
}