PHP で、LinkedList を実装する

基本構造

Node クラスと LinkedList クラスの 2つを作成
Node クラス→ $data と $next の 2つのメンバー変数、このうち $data は private で宣言、アクセス用のメソッド function data() を用意
LinkedList クラスは $first メンバー変数のみ、$first が Node オブジェクトをキープする。あとに続くすべてのノードの起点となる。
insert
=====
リストの最後に追加するノード $last を new Node($data) で新規作成
$this->first が NULL の場合を判定、NULL だったら $this->first に $last を代入（この状態ではノードが１つしかなく、最初のノードが最後のノードと同義だから）
$current を一時的なノードを表す変数としてまずは $this->first を代入してノードの先頭から始め、
$current->next != NULL になるまで while をまわす
while が終わったら、最後は $node->next に $last を代入
$last を return する
delete
=====
$this->first と一致した場合、$this->first を NULL にする
$current を一時的なノードを表す変数としてまずは $this->first を代入してノードの先頭から始め、
$current->next != NULL になるまで while をまわす
もし $current->next == $current の場合
5. $current->next = $current->next->next にして現在の $current をとばす。そのまま return して while を抜ける
$current を次のノード $current->next にして while に戻る（$current = $current->next`）
read
=====
array() を用意（この場合は $list 変数）
$current を一時的なノードを表す変数としてまずは $this->first を代入して
ノードの先頭から始め、$current != NULL になるまで while をまわす
array_push($list, $current->data());
$current に次のノード $current->next を代入
foreach で $list as $value、print $value する
コード
=====

<?php

class Node {

  private $data;
  public  $next;

  function __construct($data) {
    $this->data = $data;
    $this->next = NULL;
  }

  public function data() {
    return $this->data;
  }
}

class LinkedList {

  private $first = NULL;

  function __construct() {

    $this->first = NULL;
  }

  public function insert($data) {

    $last = new Node($data);
    if($this->first == NULL) {
      // if the number of node = 0
      return $this->first = $last;
    }   

    $current = $this->first;
    // if count($node) > 1 
    while($current->next != NULL) {
      $current = $current->next;
    }
    // if the number of node >= 1
    $current->next = &$last;
    return $last;
  }

  public function delete($node) {

    if($node == $this->first) {
      $this->first = NULL;
      return;
    }

    $current = $this->first;
    while($current->next != NULL) {
      if($current->next == $node) {
        $current->next = $current->next->next;
        return;
      }
      $current = $current->next;
    }
  }

  public function read() {
    $list = array();
    $current = $this->first;
    while($current != NULL) {
      array_push($list, $current->data());
      $current = $current->next;
    }

    foreach($list as $value)
      print "$value ";
  }
}

$linkedlist = new LinkedList();

print "step 1: ";
$node1 = $linkedlist->insert(1);
print $node1->data() . "\n";

print "step 2: ";
$node2 = $linkedlist->insert(2);
print $node2->data() . "\n";

print "step 3: ";
$node3 = $linkedlist->insert(3);
print $node3->data() . "\n";

print "step 4: ";
$node4 = $linkedlist->insert(4);
print $node4->data() . "\n";

print "step 5: ";
$linkedlist->delete($node3);
print "deleted node3\n";

print "\nValues -----\n";
$linkedlist->read();
print "\n";

出力結果

step1: 1
step 2: 2
step 3: 3
step 4: 4
step 5: deleted node3

Values -----
1 2 4