Entender estruturas de dados pode ser uma grande vantagem para melhorar diversos aspectos em um software. Um programa computacional que faz uso desse tipo de implementação de forma eficiente pode performar muito melhor do que um programa que não o utiliza.

Esse é o primeiro artigo de uma série do qual o nosso objetivo será implementar uma tabela hash usando lista ligada ou busca binária. Mas não se preocupe, cada artigo será independente uma da outra;

Quando estamos aprendendo programação, uma das primeiras estruturas de dados que aprendemos são os vetores e as matrizes. Sabemos que usar arrays nem sempre é o melhor caminho, pois algumas operações, como por exemplo, inserção e deleção, podem sair “caro” do ponto de vista de processamento. São nesses detalhes que podemos buscar novas formas de aperfeiçoar as operações básicas usando uma estrutura de dados mais eficiente.

A partir disso, existe o que chamamos de lista ligada. A lista ligada entra nesse conjunto de estruturas de dados que fazem o aperfeiçoamento de algumas operações básicas que um vetor comum não conseguiria, por exemplo, como foi dito anteriormente, a deleção de um item em um vetor. Avaliando estudos anteriores sobre a complexidade de tempo para essas duas estruturas de dados, é possível afirmar que o melhor caso para deletar um item em uma lista ligada é O(1), enquanto que o melhor caso para deletar um item em um vetor é O(n), e o mesmo cenário aplica-se para a inserção de um item. Se tiver interesse em saber mais sobre a complexidade de tempo de outras estruturas de dados, você pode acessar esse link: https://www.bigocheatsheet.com/

Um ponto importante que vale ressaltar é que na computação, e na engenharia como um todo, não existe apenas uma forma de resolver o mesmo problema. Considerando que a implementação do algoritmo não esteja errada, é possível chegar na mesma solução utilizando n caminhos diferentes. A diferença de uma solução para outra se baseia em como você lida com o design do código, tempo de execução, utilização de memória e por aí vai.

O que é uma lista ligada?

A ideia desse artigo é construir uma lista ligada utilizando a linguagem typescript. A implementação será baseada no livro Lafore, R. (2003). Data Structures & Algorithms in Java (2nd ed., pp. 179-250). Sams. desenvolvida na linguagem de programação Java. Dado que são linguagens diferentes, o código fonte e detalhes específicos de cada linguagem também serão diferentes. É claro que, entender a linguagem de programação é importante, contudo, o objetivo final desse artigo será compreender o conceito de lista ligada, e não ficarmos exclusivamente dependentes da sintaxe e da semântica de uma linguagem específica. Portanto, para esse artigo, devemos tratar a linguagem de programação muito mais como uma ferramenta do que como a única forma de implementar uma lista ligada.

Podemos fazer algumas analogias com o mundo real para tentar explicar o fundamento básico da lista ligada. Desde que o mundo é mundo, existe a corrente de ferro, essa usada para prender bicicletas, travar cargas e assim por diante. Na corrente de ferro, o primeiro elemento que compõe a corrente está ligado ao segundo elemento, enquanto que o segundo elemento está ligado ao terceiro, esse comportamento se repete até que o penúltimo elemento esteja ligado ao último elemento, de modo que o conjunto de todas as partes mínimas da corrente forme a corrente como um todo. Dito isso, existe a lista ligada, ela recebe esse nome pois cada item da lista possui uma ligação com outro item da lista, podendo ser um item vizinho, o último item ou então, o primeiro item da lista. Dessa forma, toda a lista fica integrada, sendo uma coisa só. A imagem abaixo ilustra o que seria a lista ligada:

Cada item da lista recebe uma referência para o próximo item, essa referência se mantém até o último item da lista. Com essa simples imagem, percebemos que somente o primeiro e o último item da lista ligada será um pouco diferente dos demais itens.

• O primeiro item possuirá uma referência para o segundo item, porém ele não será referenciado por ninguém. Esse detalhe será importante pois algumas operações na lista ligada atuam exclusivamente em cima disso.
• A diferença do último item é que ele não apontará para item algum, dado que ele é o último objeto da lista. Dessa forma, o valor para o próximo item será nulo. Novamente, esse detalhe também será importante para a implementação da lista ligada.

Esses são alguns dos detalhes da lista ligada. No entanto, nós poderíamos fazer uma conexão do último item com o primeiro item da lista, porém estaríamos fugindo do que seria uma lista ligada. Estaríamos implementando o que chamamos de lista circular, o que já é outro assunto.

Implementação

A nossa lista ligada começará com as operações mais simples, depois vamos incrementando novas funcionalidades. Primeiro, começaremos com esses métodos:

• isEmpty(): valida se a lista está vazia;
• insertFirst(): insere um item no início da lista;
• deleteFirst(): deleta o primeiro item da lista;

Antes de iniciarmos a implementação da classe que representa a lista ligada, é interessante organizarmos o que será um item da lista, para isso, criaremos a interface Link

/**
 * link.ts
 * 
 * 1. Recebe um tipo genérico T
 * 2. Armazena o dado T no atributo data
 * 3. Faz uma referência para um outro dado do
 * tipo T no atributo next
 */
export class Link<T> {
  data: T;
  next: Link<T> | null;

  constructor(
    data: T,

    next: Link<T> | null = null
  ) {
    this.data = data;
    this.next = next;
  }
}

Agora que já temos a classe Link, podemos começar a montar o que será a nossa classe que fará todo o gerenciamento da lista. Para isso, criamos a classe LinkedList com os seguintes métodos:

• construtor()
• isEmpty()
• insertFirst()
• deleteFirst()

// linked-list.ts
import { Link } from './link';

export class LinkedList<T> {
  private first: Link<T> | null;

  constructor() {
    this.first = null;
  }

  /* se não tiver o primeiro item da lista, então a lista está vazia */
  isEmpty(): boolean {
    return !this.first;
  }

  find(field: keyof T, value: string): T {}

  insertFirst(data: T): T {}

  deleteFirst(): Link<T> | null {}
}

A classe LinkedList poderia ser uma interface, mas como estamos construindo apenas uma única estrutura de dados, não vejo necessidade de deixá-la em uma interface para ser implementada posteriormente.

insertFirst()

Ppodemos começar a implementar os métodos da classe. Iniciaremos pelo método insertFirst:

// linked-list.ts
insertFirst(data: T): T {
  const newLink: Link<T> = new Link(data);
  newLink.next = this.first;
  this.first = { ...newLink };
  return this.first.data;
}

o método insertFirst recebe apenas um parâmetro, o dado que queremos armazenar na lista. O método se inicia com a transformação do dado para que ele seja um item da lista, ou seja, um Link. Como ele será o mais novo primeiro item da lista, o seu próximo item será o atual primeiro item. Para finalizar, o primeiro item da lista será o item que recebemos no parâmetro do método. Parece um pouco confuso, mas o método apenas insere o item na primeira posição da nossa lista ligada.

Existem muitas boas práticas para se implementar testes unitários, alguns programadores criam testes antes mesmo da implementação do método, enquanto outros criam testes após a implementação do método, no entanto, não vem ao caso tentarmos discutir esse tópico no momento, por isso, para esse artigo, iremos criar testes após a implementação de cada método, dessa forma conseguimos validar cada método logo após a sua criação. O mais importante é validarmos, de alguma forma, o que estamos querendo fazer e não escrevermos código errado.

Para os nossos testes, vamos usar o jest, ele nos fornece uma api simples e abrangente para praticamente todos os nossos cenários de teste.

Antes de iniciar a implementação, precisamos definir o tipo da informação que vamos salvar na nossa lista ligada, ele preencherá aquele nosso tipo T genérico que usamos na classe LinkedList.

// linked-list.test.ts

type Data = {
  id: string;
  name: string;
};

describe('testing linked list', () => {
  // nossos testes ser˜ão escritos aqui...
})

no código abaixo estamos testando a inserção de um item e a inserção de três itens, respectivamente:

// linked-list.test.ts

test('should not be empty when insert one element', () => {
  const linkedList = new LinkedList<Data>();
  linkedList.insertFirst({ id: '1', name: 'first' });
  expect(linkedList.isEmpty()).toBeFalsy();
});

test('should insert an item', () => {
  const linkedList = new LinkedList<Data>();

  const item: Data = { id: '1', name: 'first' };

  linkedList.insertFirst(item);

  expect(linkedList.list()).toEqual([item]);
});

test('should insert three items in sequence', () => {
  const linkedList = new LinkedList<Data>();

  const items: Data[] = [
    { id: '1', name: 'first' },
    { id: '2', name: 'second' },
    { id: '3', name: 'third' },
  ];

  linkedList.insertFirst(items[0]);
  linkedList.insertFirst(items[1]);
  linkedList.insertFirst(items[2]);

  expect(linkedList.list()).toEqual(items.reverse());
});

Rodando os testes e validando eles, podemos seguir para o próximo método. Acredito que não há necessidade de explicar cada cenário de teste, dado que existe uma breve explicação em cada teste unitário.

find()

Agora, vamos implementar o método find():

// linked-list.ts

find(field: keyof T, value: string): T {
  let current = this.first;
  while (current) {
    if (current.data[field] === value) {
      return current.data;
    }
    current = current.next;
  }
}

O método faz as executa as seguintes instruções: Dado uma chave e um valor, busque um item da lista que seja compatível com esse conjunto chave valor. Portanto, o método find faz uma iteração sobre cada item da lista, essa iteração se mantém até que a condição seja satisfeita. Caso a condição não seja satisfeita para nenhum dos itens da lista, retorne void.

Os parâmetros chave e valor ficarão mais fáceis de serem entendidos nos testes abaixo:

// linked-list.test.ts

// queremos encontrar o item que tenha id = '1'
test('should not find an item because list is empty', () => {
  const linkedList = new LinkedList<Data>();

  const item = linkedList.find('id', '1');
  expect(item).toBe(undefined);
});

// queremos encontrar o item que tenha id = '1'
test('should find first item in the list', () => {
  const linkedList = new LinkedList<Data>();

  const itemToAdd: Data = { id: '1', name: 'first' };
  linkedList.insertFirst(itemToAdd);

  const item = linkedList.find('id', '1');
  expect(item).toBe(itemToAdd);
});

// queremos encontrar o item que tenha id = '1'
test('should find second item in the list', () => {
  const linkedList = new LinkedList<Data>();

  const itemsToAdd: Data[] = [
    { id: '1', name: 'first' },
    { id: '2', name: 'second' },
  ];
  itemsToAdd.map(i => linkedList.insertFirst(i));

  const item = linkedList.find('id', '1');
  expect(item).toBe(itemsToAdd[0]);
});

// queremos encontrar o item que tenha id = '2'
test('should not find item because value doest not exists', () => {
  const linkedList = new LinkedList<Data>();

  const itemToAdd: Data = { id: '1', name: 'first' };
  linkedList.insertFirst(itemToAdd);

  const item = linkedList.find('id', '2');
  expect(item).toBe(undefined);
});

Perceba que nos testes acima buscamos sempre um item pelo id. É comum buscarmos um item pelo seu identificador único, porém isso não é uma regra, dessa forma seria possível buscar um item pelo name. um exemplo seria:

const item = linkedList.find('name', 'first')
expect(item).toBe(undefined);

Isto é, busque o item em que a chave name tenha o valor first.

deleteFirst()

Nosso terceiro e último método base será o deleteFirst():

deleteFirst(): Link<T> | null {
  const first = this.first;
  this.first = !!first ? first.next : null;
  return first;
}

Perceba que a deleção do primeiro item é apenas uma reatribuição do item this.first, ou seja, caso a lista tenha um tamanho > 1, então o primeiro item será o atual segundo item, e caso contrário, a lista se tornará vazia, isto é, this.first === null;

Os testes ficaram da seguinte forma:

test('should be empty when insert and remove an element', () => {
  const linkedList = new LinkedList<Data>();
  linkedList.insertFirst({ id: '1', name: 'first' });
  linkedList.deleteFirst();
  expect(linkedList.isEmpty()).toBeTruthy();
});

test('should insert three items and delete two items', () => {
  const linkedList = new LinkedList<Data>();

  const items: Data[] = [
    { id: '1', name: 'first' },
    { id: '2', name: 'second' },
    { id: '3', name: 'third' },
  ];

  linkedList.insertFirst(items[0]);
  linkedList.insertFirst(items[1]);
  linkedList.insertFirst(items[2]);

  linkedList.deleteFirst();
  linkedList.deleteFirst();

  expect(linkedList.list()).toEqual([items[0]]);
});

Essa é uma das implementações mais simples da nossa classe, ela não recebe parâmetro algum, deixando mais simples o entendimento.

deleteOne()

Pode ser que ter um método que remova sempre o primeiro item não seja tão efetivo, o que mais usaremos na prática será um método que remove um determinado item da lista, podendo estar na primeira, ou em qualquer outra posição da lista. Dessa forma, vamos implementar um outro método, chamado deleteOne().

Os parâmetros desse método funcionarão da mesma forma que os parâmetros do método find, ou seja, vamos passar uma chave e um valor.

Abaixo segue a sua implementação:

deleteOne(field: keyof T, value: string): void {
  let current = this.first;
  let previous = this.first;

  if (value === this.first.data[field]) {
    this.first = current.next;
    return;
  }

  while (current) {
    if (value === current.data[field]) {
      previous.next = current.next;
      return;
    }
    previous = current;
    current = current.next;
  }
}

Talvez esse seja o método com maior complexidade da classe LinkedList. Primeiro, validamos se o item que queremos deletar é o primeiro item da lista, em caso positivo, apenas mudamos a referência do primeiro item. Se não, iteramos cada elemento até encontrá-lo. Em caso positivo, pegamos o "ponteiro" do item anterior e o apontamos para o próximo item do item atual da iteração. Em outra palavras, é como se ignorássemos o item que queremos deletar da lista ligada, dessa forma ele não será mais referenciado por nenhum outro item da lista.

Caso esse método seja implementado de forma errada, podemos ter muitos problemas com toda a cadeia que forma a lista, por esse motivo vale muito a pena a criação de testes automatizados que cuidem dessa implementação:

test('should delete first item when list has only one item', () => {
  const linkedList = new LinkedList<Data>();

  const itemToAdd: Data = { id: '1', name: 'first' };
  linkedList.insertFirst(itemToAdd);

  linkedList.deleteOne('id', '1');

  const list = linkedList.list();
  expect(list).toEqual([]);
});

test('should delete first item when list has many items', () => {
  const linkedList = new LinkedList<Data>();

  const itemsToAdd: Data[] = [
    { id: '1', name: 'first' },
    { id: '2', name: 'second' },
    { id: '3', name: 'third' },
  ];

  itemsToAdd.map(i => linkedList.insertFirst(i));
  linkedList.deleteOne('id', '3');

  const list = linkedList.list();
  expect(list).toEqual([itemsToAdd[1], itemsToAdd[0]]);
});

test('should delete middle item when list has many items', () => {
  const linkedList = new LinkedList<Data>();

  const itemsToAdd: Data[] = [
    { id: '1', name: 'first' },
    { id: '2', name: 'second' },
    { id: '3', name: 'third' },
  ];

  itemsToAdd.map(i => linkedList.insertFirst(i));
  linkedList.deleteOne('id', '2');

  const list = linkedList.list();
  expect(list).toEqual([itemsToAdd[2], itemsToAdd[0]]);
});

test('should delete last item when list has many items', () => {
  const linkedList = new LinkedList<Data>();

  const itemsToAdd: Data[] = [
    { id: '1', name: 'first' },
    { id: '2', name: 'second' },
    { id: '3', name: 'third' },
  ];

  itemsToAdd.map(i => linkedList.insertFirst(i));
  linkedList.deleteOne('id', '1');

  const list = linkedList.list();
  expect(list).toEqual([itemsToAdd[2], itemsToAdd[1]]);
});

Com isso, finalizamos a classe LinkedList escrita em typescript. O código fonte final pode ser visto aqui: github.

De qualquer forma, a nossa classe final está logo abaixo:

/* link.ts */
class Link<T> {
  data: T;
  next: Link<T> | null;

  constructor(
    data: T,

    next: Link<T> | null = null
  ) {
    this.data = data;
    this.next = next;
  }
}

/* linked-list.ts */
class LinkedList<T> {
  private first: Link<T> | null;

  constructor() {
    this.first = null;
  }

  isEmpty(): boolean {
    return !this.first;
  }

  insertFirst(data: T): T {
    const newLink: Link<T> = new Link(data);
    newLink.next = this.first;
    this.first = { ...newLink };
    return this.first.data;
  }

  find(field: keyof T, value: string): T {
    let current = this.first;
    while (current) {
      if (current.data[field] === value) {
        return current.data;
      }
      current = current.next;
    }
  }

  deleteOne(field: keyof T, value: string): void {
    let current = this.first;
    let previous = this.first;

    if (value === this.first.data[field]) {
      this.first = current.next;
      return;
    }

    while (current) {
      if (value === current.data[field]) {
        previous.next = current.next;
        return;
      }
      previous = current;
      current = current.next;
    }
  }

  deleteFirst(): Link<T> | null {
    const first = this.first;
    this.first = !!first ? first.next : null;
    return first;
  }

  list(): T[] {
    let list = [];
    let current = this.first;
    while (current) {
      list = [...list, current.data];
      current = current.next;
    }
    return list;
  }
}

Conclusão

Essa é a ideia geral de uma lista ligada. Vale ressaltar que existem milhares de variações para construir uma lista, isso irá variar de acordo com o problema que você estiver resolvendo. A grande vantagem da lista ligada sobre um vetor ou array é a eficiência na remoção e na inserção de um item. A inserção e a remoção no início da lista possui complexidade O(1). Os métodos find e deleteOne possuem complexidade O(n). A vantagem do método deleteOne é que não precisamos copiar todos os itens para uma posição anterior, como fazemos para um vetor comum e além disso, o espaço de memória alocado varia dinamicamente, enquanto que a maioria das linguagens aloca um espaço fixo na memória para os arrays.

Referências e Links Úteis

• O livro base para a criação dessa classe é um livro escrito em java: Lafore, R. (2003). Data Structures & Algorithms in Java (2nd ed., pp. 179-250). Sams.

• Essas são algumas das aplicações da lista ligada: aplicações de listas ligadas