SplDoublyLinkedList クラス
(PHP 5 >= 5.3.0, PHP 7, PHP 8)
はじめに
SplDoublyLinkedList クラスは、双方向リンクリストの主要な機能を提供します。
クラス概要
/* 定数 */
/* メソッド */
}定義済み定数
イテレーションの方向
SplDoublyLinkedList::IT_MODE_LIFO-
スタックのように、LIFO (最後に入れたものを最初に取り出す) の順で走査されます。
SplDoublyLinkedList::IT_MODE_FIFO-
キューのように、FIFO(先入れ先出し) の順で走査されます。
イテレーションの振る舞い
SplDoublyLinkedList::IT_MODE_DELETE-
走査された要素を削除します。
SplDoublyLinkedList::IT_MODE_KEEP-
走査されても要素を削除しません。
目次
- SplDoublyLinkedList::add — 特定のインデックスに新しい値を 追加/挿入 する
- SplDoublyLinkedList::bottom — 双方向リンクリストの最初のノードを取得する
- SplDoublyLinkedList::count — 双方向リンクリストの要素数を数える
- SplDoublyLinkedList::current — 現在の配列の要素を返す
- SplDoublyLinkedList::getIteratorMode — 反復処理のモードを返す
- SplDoublyLinkedList::isEmpty — 双方向リンクリストが空かどうかを調べる
- SplDoublyLinkedList::key — 現在のノードのインデックスを返す
- SplDoublyLinkedList::next — 次のエントリに移動する
- SplDoublyLinkedList::offsetExists — 指定した $index が存在するかどうかを返す
- SplDoublyLinkedList::offsetGet — 指定した $index の値を返す
- SplDoublyLinkedList::offsetSet — 指定した $index の値を $value に設定する
- SplDoublyLinkedList::offsetUnset — 指定した $index の値を削除する
- SplDoublyLinkedList::pop — 双方向リンクリストの末尾からノードを取り出す
- SplDoublyLinkedList::prev — 前のエントリに移動する
- SplDoublyLinkedList::push — 双方向リンクリストの末尾に要素を追加する
- SplDoublyLinkedList::rewind — イテレータを先頭に巻き戻す
- SplDoublyLinkedList::serialize — ストレージをシリアライズする
- SplDoublyLinkedList::setIteratorMode — 反復処理のモードを設定する
- SplDoublyLinkedList::shift — 双方向リンクリストの先頭からノードを取り出す
- SplDoublyLinkedList::top — 双方向リンクリストの最後のノードを取得する
- SplDoublyLinkedList::unserialize — ストレージをアンシリアライズする
- SplDoublyLinkedList::unshift — 双方向リンクリストの先頭に要素を追加する
- SplDoublyLinkedList::valid — 双方向リンクリストにまだノードがあるかどうかを調べる
＋add a note
User Contributed Notes 6 notes
Gilles A ¶
11 years ago
FIFO and LIFO in SplDoublyLinkedList
$list = new SplDoublyLinkedList();
$list->push('a');
$list->push('b');
$list->push('c');
$list->push('d');
echo "FIFO (First In First Out) :\n";
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
for ($list->rewind(); $list->valid(); $list->next()) {
echo $list->current()."\n";
}
Result :
// FIFO (First In First Out):
// a
// b
// c
// d
echo "LIFO (Last In First Out) :\n";
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
for ($list->rewind(); $list->valid(); $list->next()) {
echo $list->current()."\n";
}
Result :
// LIFO (Last In First Out):
// d
// c
// b
// a
Maaz Rehman ¶
9 years ago
/*
php doubly link list is an amazing data structure ,doubly means you can traverse forward as well as backward, it can act as a deque(double ended queue) if you want it to,
here is how it works
*/
//instantiating an object of doubly link list
$dlist=new SplDoublyLinkedList();
//a push inserts data at the end of the list
$dlist->push('hiramariam');
$dlist->push('maaz');
$dlist->push('zafar');
/* the list contains
hiramariam
maaz
zafar
*/
//while an unshift inserts an object at top of the list
$dlist->unshift(1);
$dlist->unshift(2);
$dlist->unshift(3);
/* the list now contains
3
2
1
hiramariam
maaz
zafar
*/
//you can delete an item from the bottom of the list by using pop
$dlist->pop();
/* the list now contains
3
2
1
hiramariam
maaz
*/
//you can delete an item from the top of the list by using shift()
$dlist->shift();
/* the list now contains
2
1
hiramariam
maaz
*/
/* if you want to replace an item at particular index you can use a method named add , note that if you want to replace an item that does not exist , an exception will be thrown*/
$dlist->add(3 , 2.24);
/*
to go through the list we use a simple for loop, the rewind() method shown below point to the initials of the list depending on the iterator, a valid() method checks whether a list is still valid or not , meaning it ensures the loop does not go on and on after we reach the last data in the list , and the next() method simply points to the next data in the list.
*/
for($dlist->rewind();$dlist->valid();$dlist->next()){
echo $dlist->current()."<br/>";
}
echo "<br/>";
/*
To traverse backward
*/
$dlist->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
for($dlist->rewind();$dlist->valid();$dlist->next()){
echo $dlist->current()."<br/>";;
}
dongchao769390531 at 163 dot com ¶
7 years ago
<?php
$splDoubleLinkedList = new SplDoublyLinkedList();
$splDoubleLinkedList->push('a');
$splDoubleLinkedList->push('3');
$splDoubleLinkedList->push('v');
$splDoubleLinkedList->push('1');
$splDoubleLinkedList->push('p');
//First of all, we need rewind list
$splDoubleLinkedList->rewind();
//Use while, check if the list has valid node
while ($splDoubleLinkedList->valid()){
//Print current node's value
echo $splDoubleLinkedList->current()."\n";
//Turn the cursor to next node
$splDoubleLinkedList->next();
}
?>
77931774 at qq dot com ¶
3 years ago
$list = new SplDoublyLinkedList();
for ($i = 0; $i < 2000001; $i++) {
$list->push($i);
}
$s = microtime(true);
//$res = $list->offsetGet(2000000); // spend 7 ms
$res = $list->offsetGet(0); // spend 0.07 ms
var_dump($res);
$e = microtime(true);
echo ($e - $s) * 1000;
Premysl Karbula ¶
2 years ago
A function which replaces some portion od doubly linked list (DLL) with items from specified array.
<?php
/**
* Replace some portion (specified by index and length) of DLL with items
* from the specified replacement array.
*/
public function dll_splice(
\SplDoublyLinkedList $dll,
int $start,
int $length,
array $replacement,
): void {
if ($start < 0 || ($start + $length) > $dll->count()) {
throw new \OutOfRangeException("Invalid range for splicing");
}
for ($i = 0; $i < $length; $i++) {
$dll->offsetUnset($start);
}
foreach ($replacement as $item) {
$dll->add($start, $item);
}
}
?>
lincoln dot du dot j at gmail dot com ¶
7 years ago
$a = new SplDoublyLinkedList;
$arr=[1,2,3,4,5,6,7,8,9];
for($i=0;$i<count($arr);$i++){
$a->add($i,$arr[$i]);
}
$a->push(11); //push method
$a->add(10,12); //add method must with index
$a->shift(); //remove array first value
$a->unshift(1); //add first value
$a->rewind(); //initial from first
echo "SplDoublyLinkedList array last/top value " . $a->top() ." \n";
echo "SplDoublyLinkedList array count value " . $a->count() ." \n";
echo "SplDoublyLinkedList array first/top value " . $a->bottom() . " \n\n";
while($a->valid()){ //check with valid method
echo 'key ', $a->key(), ' value ', $a->current(),"\n"; //key and current method use here
$a->next(); //next method use here
}
$a->pop(); //remove array last value
print_r($a);
$s=$a->serialize();
echo $s;
//Output
SplDoublyLinkedList array last/top value 12
SplDoublyLinkedList array count value 11
SplDoublyLinkedList array first/top value 1
key 0 value 1
key 1 value 2
key 2 value 3
key 3 value 4
key 4 value 5
key 5 value 6
key 6 value 7
key 7 value 8
key 8 value 9
key 9 value 11
key 10 value 12
SplDoublyLinkedList Object
(
[flags:SplDoublyLinkedList:private] => 0
[dllist:SplDoublyLinkedList:private] => Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 6
[6] => 7
[7] => 8
[8] => 9
[9] => 11
)
)
i:0;:i:1;:i:2;:i:3;:i:4;:i:5;:i:6;:i:7;:i:8;:i:9;:i:11;