Outubro 26th 2007 03:22 am
Utilizando listas encadeadas
Inserção no início da lista:
1) criamos o novo nodo a ser inserido na lista
2) fazemos ele apontar para o primeiro elemento da lista
3) setamos o head para nosso novo nodo
Código
-
/**
-
* insere um elemento ao início da lista
-
*
-
* @param mixed $item
-
*/
-
public function insertFirst($item) {
-
$node = new Node($item, $this->head);
-
-
if ($this->tail == null)
-
$this->tail = $node;
-
-
$this->head = $node;
-
$this->count++;
-
}
Inserção no final da lista:
1) criamos o novo nodo a ser inserido na lista
2) setamos o próximo nodo do ultimo elemento da lista para apontar para nosso novo nodo
3) setamos o tail para nosso novo nodo
Código
-
/**
-
* insere um elemento ao fim da lista
-
*
-
* @param mixed $item
-
*/
-
public function insertLast($item) {
-
$node = new Node($item);
-
-
if ($this->tail != null)
-
$this->tail->setNext($node);
-
else
-
$this->head = $node;
-
-
$this->tail = $node;
-
$this->count++;
-
}
Remoção do primeiro elemento da lista:
1) basta setar o head para o próximo elemento do atual head de nossa lista
Código
-
/**
-
* remove/remove o primeiro elemento da lista
-
*
-
* @return mixed
-
*/
-
public function removeFirst() {
-
if ($this->isEmpty())
-
throw new NoSuchElementException;
-
-
$item = $this->head->getItem();
-
$tmp = $this->head;
-
$this->head = $this->head->getNext();
-
-
$tmp->setItem(null);
-
$tmp->setNext(null);
-
-
if ($this->head == null)
-
$this->tail = null;
-
-
$this->count--;
-
-
return $item;
-
}
Remoção de um elemento do meio da lista:
Supondo que o acesso ao elemento da lista seja feito por índice e se queira remover o item 2
Código
-
/**
-
* remove um elemento da lista a partir do index
-
*
-
* @param int $index
-
* @return mixed
-
*/
-
public function remove($index) {
-
-
if ($index <0 || $index>= $this->count)
-
throw new OutOfRangeException('Index: ' + $index);
-
-
$target = $this->head;
-
$prev = null;
-
-
for ($i=0; $i<$index; $i++) {
-
$prev = $target;
-
$target = $target->getNext();
-
}
-
-
$item = $target->getItem();
-
-
if ($target == $this->head)
-
$this->head = $target->getNext();
-
else
-
$prev->setNext($target->getNext());
-
-
if ($target == $this->tail)
-
$this->tail = $prev;
-
-
$target->setItem(null);
-
$target->setNext(null);
-
-
$this->count--;
-
-
return $item;
-
}
Inserção de um elemento do meio da lista:
Código
-
/**
-
* insere um elemento qualquer uma posição da lista
-
*
-
* @param int $index
-
* @param mixed $item
-
*/
-
public function insert($index, $item) {
-
if ($index <0 || $index>= $this->count)
-
throw new OutOfRangeException('Index: ' + $index);
-
-
$target = $this->head;
-
$prev = null;
-
$tmp = new Node($item);
-
-
for ($i=0; $i<$index; $i++) {
-
$prev = $target;
-
$target = $target->getNext();
-
}
-
-
$tmp->setNext($target);
-
-
if ($prev != null) {
-
$prev->setNext($tmp);
-
} else {
-
$this->head = $tmp;
-
}
-
}
Ai estão os principais métodos de nossa lista, com base nesta lógica os outros se tornão muito simples.
Para quem quiser baixar o código completo e os exemplos de uso basta fazer o download neste link Arquivos do post
Mais informações: http://pt.wikipedia.org/wiki/Lista_ligada
[]'s
(Nenhuma avaliação ainda)
Loading ...4 Comments »
Fill on 12 Dez 2007 at 11:28 #
Eu já implementei isso em C na faculdade mas, sinceramente, nunca vi uma boa aplicação para isso. Voce teve de usar isso em php porque? Responde no meu e-mail por favor =)
Grato
Diego Tremper on 14 Dez 2007 at 02:26 #
Felipe,
de fato nunca utilizei uma lista encadeada em algum sistema em produção, mas pelo que sei, a vantagem de utilizar listas encadeadas está na inserção e remoção de elementos no meio da lista, sendo que não há a necessidade de mover os demais elementos da lista para esta ação.
Obs.: A idéia do blog é justamente difundir e expor opiniões sobre assuntos diversos, por isso respondi aqui sua pergunta. Espero que não se ofenda.
Abraço
Dil Okulu on 31 Mar 2008 at 07:00 #
hello everybody. my Portuguese is not good but it seems like a very nice web site. thanks
milla on 26 Jun 2009 at 04:43 #
muito boa explicação