Blog do Tremper

Outubro 26th 2007 03:22 am

Utilizando listas encadeadas

Definição da interface

PLAIN TEXT

PHP:

1. <?php
2.  
3. interface IList {
4.  
5.     public function getCount();
6.     public function isEmpty();
7.     public function clear();
8.     public function getFirst();
9.     public function getLast();
10.     public function insertFirst($item);
11.     public function insertLast($item);
12.     public function removeFirst();
13.     public function removeLast();
14.     public function get($index);
15.     public function set($index, $item);
16.     public function remove($index);
17.     public function contains($item);
18.     public function removeItem($item);
19.  
20. }

Definição do Nodo

Está classe irá representar cada nodo da lista

PLAIN TEXT

PHP:

1. <?php
2.  
3. /**
4.  * Classe que representa cada nodo da lista encadeada
5.  *
6.  */
7. class Node {
8.  
9.     /**
10.      * armazena elemento que o node irá armazenar
11.      *
12.      * @var midex
13.      */
14.     private $item;
15.  
16.     /**
17.      * armazena próximo nodo da lista
18.      *
19.      * @var Node
20.      */
21.     private $nextNode;
22.  
23.     /**
24.      * construtor da classe
25.      *
26.      * @param mixed $item
27.      * @param Node $nextNode
28.      */
29.     public function __construct($item, Node $nextNode = null) {
30.         $this->item = $item;
31.         $this->nextNode = $nextNode;
32.     }
33.  
34.     /**
35.      * seta o elemento a ser armazenado no nodo
36.      *
37.      * @param mixed $item
38.      */
39.     public function setItem($item) {
40.         $this->item = $item;
41.     }
42.  
43.     /**
44.      * seta o próximo nodo da lista
45.      *
46.      * @param Node $nextNode
47.      */
48.     public function setNext(Node $nextNode = null) {
49.         $this->nextNode = $nextNode;
50.     }
51.  
52.     /**
53.      * retorna o elemento armazenado no nodo
54.      *
55.      * @return mixed
56.      */
57.     public function getItem() {
58.         return $this->item;
59.     }
60.  
61.     /**
62.      * retorna o próximo nodo da lista
63.      *
64.      * @return Node
65.      */
66.     public function getNext() {
67.         return $this->nextNode;
68.     }
69.  
70. }

Implementação da lista

Primeiramente criamos a classe LinkedList definindo seus três atributos: $head, $tail e $count. Onde $head, irá armazenar o primeiro nodo da lista, $tail irá armazerar o último atributo da lista e $count irá armazenar a quantidade de itens na lista.

PLAIN TEXT

PHP:

1. <?php
2.  
3. require_once('Node.php');
4. require_once('IList.php');
5. require_once('NoSuchElementException.php');
6.  
7. /**
8.  * Lista encadeada
9.  *
10.  */
11. class LinkedList implements IList {
12.  
13.     /**
14.      * cabeça da lista
15.      *
16.      * @var Node
17.      */
18.     private $head;
19.  
20.     /**
21.      * Calda da lista
22.      *
23.      * @var Node
24.      */
25.     private $tail;
26.  
27.     /**
28.      * Contador de elementos da lista
29.      *
30.      * @var int
31.      */
32.     private $count;
33.  
34.     /**
35.      * construtor da classe
36.      *
37.      * @return LinkedList
38.      */
39.     public function __construct() {
40.         $this->head = null;
41.         $this->tail = null;
42.         $this->count = 0;
43.     }
44. }

Agora iremos criar os principais métodos que nossa lista terá.

PHP LinkedList Lista encadeada Estrutura de dados

Compartilhe:

• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 

(Nenhuma avaliação ainda)

 Loading ...

Páginas: 1 2 3

3 Comments »

3 Responses to “Utilizando listas encadeadas”

1. 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

2. 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

3. 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

Trackback URI | Comments RSS

Leave a Reply