php鏈表

作用：是隨機(jī)存儲(chǔ)，查找必須順序引導(dǎo)查找，優(yōu)點(diǎn)是增加新節(jié)點(diǎn)和刪除節(jié)點(diǎn)方便，缺點(diǎn)是不能直接讀取數(shù)據(jù)

要點(diǎn)：鏈表是一種常見(jiàn)的重要的數(shù)據(jù)結(jié)構(gòu)。它是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。它可以根據(jù)需要開(kāi)辟內(nèi)存單元（避免內(nèi)存的浪費(fèi)）

鏈表無(wú)非是幾種固定形式：單向的，雙向的，循環(huán)的，帶或不帶頭節(jié)點(diǎn)的，帶或不帶尾節(jié)點(diǎn)的，熟悉一種結(jié)構(gòu)，其它的類推

★數(shù)組和鏈表的區(qū)別

   數(shù)組是將元素在內(nèi)存中連續(xù)存放，由于每個(gè)元素占用內(nèi)存相同，可以通過(guò)下標(biāo)迅速訪問(wèn)數(shù)組中任何元素。但是如果要在數(shù)組中增加一個(gè)元素，需要移動(dòng)大量元素，在內(nèi)存中空出一個(gè)元素的空間，然后將要增加的元素放在其中。同樣的道理，如果想刪除一個(gè)元素，同樣需要移動(dòng)大量元素去填掉被移動(dòng)的元素。如果應(yīng)用需要快速訪問(wèn)數(shù)據(jù)，很少或不插入和刪除元素，就應(yīng)該用數(shù)組。

   鏈表恰好相反，鏈表中的元素在內(nèi)存中不是順序存儲(chǔ)的，而是通過(guò)存在元素中的指針聯(lián)系到一起。比如：上一個(gè)元素有個(gè)指針指到下一個(gè)元素，以此類推，直到最后一個(gè)元素。如果要訪問(wèn)鏈表中一個(gè)元素，需要從第一個(gè)元素開(kāi)始，一直找到需要的元素位置。但是增加和刪除一個(gè)元素對(duì)于鏈表數(shù)據(jù)結(jié)構(gòu)就非常簡(jiǎn)單了，只要修改元素中的指針就可以了。如果應(yīng)用需要經(jīng)常插入和刪除元素你就需要用鏈表數(shù)據(jù)結(jié)構(gòu)了。

★雙向鏈表和單向鏈表的區(qū)別

①單向鏈表內(nèi)存占用比雙向的少②在查找一個(gè)前節(jié)點(diǎn)，雙向比單向快，因?yàn)閱蜗蜴湵淼脑挘惚仨殢念^節(jié)點(diǎn)開(kāi)始遍歷，而雙向鏈表的節(jié)點(diǎn)中本身就有前節(jié)點(diǎn)信息

④單向鏈表存儲(chǔ)結(jié)構(gòu)的節(jié)點(diǎn)中只有一個(gè)指向后繼節(jié)點(diǎn)的指針；⑤雙向鏈表的節(jié)點(diǎn)中有兩個(gè)指針，其中一個(gè)后繼節(jié)點(diǎn)的指針，另一個(gè)指向前一個(gè)節(jié)點(diǎn)的指針。

一、單鏈表

鏈表：是一個(gè)有序的列表，但是它在內(nèi)存中是分散存儲(chǔ)的，使用鏈表可以解決類似約瑟夫問(wèn)題，排序問(wèn)題，搜索問(wèn)題，廣義表

單向鏈表，雙向鏈表，環(huán)形鏈表

PHP的底層是C，當(dāng)一個(gè)程序運(yùn)行時(shí)，內(nèi)存分成五個(gè)區(qū)（堆區(qū)，棧區(qū)，全局區(qū)，常量區(qū)，代碼區(qū)）

規(guī)定：基本數(shù)據(jù)類型，一般放在棧區(qū)

復(fù)合數(shù)據(jù)類型，比如對(duì)象，放在堆區(qū)

定義一個(gè)類Hero

定義成員屬性排名 $no

定義成員屬性姓名 $name

定義成員屬性昵稱 $nickname

定義成員屬性 $next，是一個(gè)引用，指向下一個(gè)Hero對(duì)象

定義構(gòu)造函數(shù)，傳遞參數(shù)：$no，$name，$nickname

創(chuàng)建一個(gè)頭head，該head只是一個(gè)頭，不放入數(shù)據(jù)

獲取$head對(duì)象，new Hero()

獲取第一個(gè)Hero對(duì)象$hero，new Hero(1,”宋江”,”及時(shí)雨”)

連接兩個(gè)對(duì)象，$head->next=$hero

獲取第二個(gè)Hero對(duì)象$hero2，new Hero(2,”盧俊義”,”玉麒麟”)

連接兩個(gè)對(duì)象，$hero->next=$hero2

遍歷鏈表

定義一個(gè)函數(shù)showHeros()，參數(shù)：$head對(duì)象

定義一個(gè)臨時(shí)變量$cur來(lái)存儲(chǔ)$head對(duì)象

while循環(huán)，條件$cur->next不為null

打印一下

指針后移，$cur=$cur->next

<?php/*** 英雄類*/class Hero{  public $no;  public $name;  public $nickname;  public $next=null;  public function __construct($no='',$name='',$nickname=''){    $this->no=$no;    $this->name=$name;    $this->nickname=$nickname;  }}class LinkListDemo{  public static function main(){    $head=new Hero();    $hero1=new Hero(1,"宋江","及時(shí)雨");    $head->next=$hero1;    $hero2=new Hero(2,"盧俊義","玉麒麟");    $hero1->next=$hero2;    LinkListDemo::showHeros($head);  }  /**  * 展示英雄  */  public static function showHeros($head){    $cur=$head;    while($cur->next!=null){      echo "姓名：".$cur->next->name."<br/>";      $cur=$cur->next;    }  } } LinkListDemo::main();