Skip to content

DoubleLinkedList ​

DoubleLinkedList<T> implementa uma lista duplamente encadeada com inserção e remoção O(1) em ambas as extremidades.

Construção ​

SintaxeDescrição
DoubleLinkedList<T>()Cria uma nova lista duplamente encadeada vazia
DoubleLinkedList.fromArray(arr)Cria uma lista duplamente 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étodoAssinaturaRetornoDescrição
pushFront(T) => voidvoidAdiciona um elemento à frente
pushBack(T) => voidvoidAdiciona 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() => usizeusizeNúmero de elementos
isEmpty() => booleanbooleanSe a lista não tem elementos
clear() => voidvoidRemove todos os elementos

popFront, popBack, front e back retornam T?, chame com uma checagem de presença ou valor padrão.

Complexidade ​

OperaçãoComplexidade de Tempo
pushFrontO(1)
pushBackO(1)
popFrontO(1)
popBackO(1)
frontO(1)
backO(1)
lenO(1)
isEmptyO(1)
clearO(n)

Exemplos ​

Construção ​

tyrus
import { DoubleLinkedList } from "tyrus:algorithm";

const dll = DoubleLinkedList<i32>();

pushFront e pushBack ​

tyrus
const dll = DoubleLinkedList<i32>();

dll.pushFront(1);
dll.pushBack(2);
dll.pushBack(3);

print(dll.len());  // 3

front e back ​

tyrus
const dll = DoubleLinkedList<i32>();

dll.pushBack(10);
dll.pushBack(20);

const f: i32? = dll.front();
if (f) {
    print(f);  // 10
}

const b: i32? = dll.back();
if (b) {
    print(b);  // 20
}

popFront ​

tyrus
const dll = DoubleLinkedList<i32>();

dll.pushBack(1);
dll.pushBack(2);
dll.pushBack(3);

const p1: i32? = dll.popFront();
if (p1) {
    print(p1);  // 1
}

const p2: i32? = dll.popFront();
if (p2) {
    print(p2);  // 2
}

print(dll.len());  // 1

popBack ​

tyrus
const dll = DoubleLinkedList<i32>();

dll.pushBack(1);
dll.pushBack(2);
dll.pushBack(3);

const p: i32? = dll.popBack();
if (p) {
    print(p);  // 3
}

print(dll.len());  // 2

len ​

tyrus
const dll = DoubleLinkedList<i32>();

print(dll.len());  // 0

dll.pushBack(1);
dll.pushFront(2);

print(dll.len());  // 2

isEmpty ​

tyrus
const dll = DoubleLinkedList<i32>();

print(dll.isEmpty());  // true

dll.pushBack(1);

print(dll.isEmpty());  // false

clear ​

tyrus
const dll = DoubleLinkedList<i32>();

dll.pushBack(1);
dll.pushBack(2);
dll.pushBack(3);

print(dll.len());  // 3

dll.clear();

print(dll.isEmpty());  // true
print(dll.len());      // 0

fromArray ​

tyrus
const vals: i32[] = [7, 8, 9];
const dll = DoubleLinkedList.fromArray(vals);

print(dll.len());  // 3

const f: i32? = dll.front();
if (f) {
    print(f);  // 7
}

const b: i32? = dll.back();
if (b) {
    print(b);  // 9
}