Estrutura de dados

Lista Linear
Giovani Rubert Librelotto Estrutura de Dados UFSM

Listas Lineares
— Uma das formas mais simples de interligar os elementos de um

conjunto.
— Estrutura em que as operações inserir, retirar e localizar são

definidas.
— Podem crescer ou diminuir de tamanho durante a execução de

um programa, de acordo com a demanda.
— Itens podem ser acessados, inseridos ou retirados de uma lista.

Listas Lineares
— Duas listas podem ser concatenadas para formar uma lista única,

ou uma pode ser partida em duas ou mais listas.
— Adequadas quando não é possível prever a demanda por

memória, permitindo a manipulação de quantidades imprevisíveis de dados, de formato também imprevisível.
— São úteis em aplicações tais como manipulação simbólica,

gerência de memória, simulações e compiladores.

Definição de Listas Lineares
— Seqüência de zero ou mais itens
— x1 ,x2 ,···,xn , na qual xi é de um determinado tipo e n representa o tamanho

da lista linear.
— Sua principal propriedade estrutural envolve as posições

relativas dos itens em uma dimensão.
— Assumindo n ≥ 1, x1 é o primeiro item da lista

e xn é o último item da lista.

— xi precede xi+1 para i = 1,2,···,n – 1 — xi sucede xi-1 para i = 2,3,···,n — o elemento xi é dito estar na i-ésima posição da lista.

TAD de Listas Lineares
— O que deveria conter?
— Representação do tipo da lista — Conjunto de operações que atuam sobre a lista

— Algumas operações que deveriam fazer parte deste conjunto?

O conjunto de operações a ser definido depende de cada aplicação.

TAD Listas Lineares
— Um conjunto de operações necessário a uma maioria de

aplicações é: 1) Criar uma lista linear vazia. 2) Inserir um novo item imediatamente após o i-ésimo item. 3) Retirar o i-ésimo item. 4) Localizar o i-ésimo item para examinar e/ou alterar o conteúdo de seus componentes. 5) Combinar duas ou mais listas lineares em uma lista única. 6)