Banco de dados

Listas Lineares
Siang Wun Song - Universidade de São Paulo - IME/USP

MAC 5710 - Estruturas de Dados - 2008

Siang Wun Song - Universidade de São Paulo - IME/USP

Listas Lineares

Referência bibliográfica

Os slides sobre este assunto de listas lineares são parcialmente baseados no segundo capítulo do livro D. E. Knuth. The Art of Computer Programming. Volume 1, Addison Wesley, 1973.

Siang Wun Song - Universidade de São Paulo - IME/USP

Listas Lineares

Introdução
Uma estrutura de dado armazena dados na memória do computador a fim de permitir o acesso eficiente dos mesmos. A maioria das estruturas de dados consideram a memória primária (a chamada RAM) como pilhas, filas, árvores binárias de busca, árvores AVL e árvores rubro-negras. Outras são especialmente projetadas e adequadas para serem armazenadas em memórias secundárias como o disco rígido, e.g. B-árvores. Uma estrutura de dado bem projetada permite a manipulação eficiente, em tempo e em espaço, dos dados armazenados através de operações específicas. Um conceito relacionado com a estrutura de dado é o tipo abstrato de dados, que veremos em breve.
Siang Wun Song - Universidade de São Paulo - IME/USP Listas Lineares

Lista linear

Uma lista linear é um conjunto de n elementos (de informações) x1 , x2 , ..., xn , cuja propriedade estrutural envolve as posições relativas de seus elementos. Supondo n > 0, temos x1 é o primeiro elemento para 1 < k < n, xk é precedido por xk −1 e seguido por xk +1 xn é o último elemento.

Siang Wun Song - Universidade de São Paulo - IME/USP

Listas Lineares

Operações
Algumas operações que podemos querer realizar sobre listas lineares: Ter acesso a xk , k qualquer, a fim de examinar ou alterar o conteúdo de seus campos Inserir um elemento novo antes ou depois de xk Remover xk Colocar todos os elementos da lista em ordem. Combinar 2 ou mais listas lineares em uma só Quebrar uma lista linear em duas ou mais Copiar uma lista linear em um outro espaço