五十一、PHP核心探索：數組與連結清單 ☞ C語言中數組和連結清單的一些事情

在C語言中，我們可以自定義各種各樣的資料結構，用來把很多資料儲存在一個變量裡面，但是每種資料結構都有自己的優缺點，PHP核心規模如此龐大，是否已經找到了一些非常棒的解決方法呢？

我們在選擇各種資料結構時，往往會考慮我們需要處理的資料規模以及需要的性能。下面讓我們簡要的看一下看C語言中數組和連結清單的一些事情。

數組

作者這裡用的不是Array，而是Vector，可能指的是C++裡的Vector，它與數組幾乎是完全一樣的，唯一的不同便是可以實作動态存儲。本節下文都是用數組一詞代替之，請各位注意。數組是記憶體中一塊連續的區域，其每一個元素都具有一個唯一的下标值。

int a[3];
a[0]=1;
a[2]=3;      

不僅是整數，其它類型的變量也可以儲存在數組中，比如我們前面用到的zend_get_parameters_array_ex()，便把很多zval**類型的變量儲存到一個數組裡，為了使其正常工作，我們提前向系統申請了相應大小的記憶體空間。

zval ***args = safe_emalloc(ZEND_NUM_ARGS(), sizeof(zval**), 0);      

這裡我們仍然可以用一個整數來當作下标去數組中取出我們想要的資料，就像var_dump()的實作中通過args[i]來擷取參數并把它傳遞給php_var_dump()函數那樣。

使用數組最大的好處便是速度！讀寫都可以在O(1)内完成，因為它每個元素的大小都是一緻的，隻要知道下标，便可以瞬間計算出其對應的元素在記憶體中的位置，進而直接取出或者寫入。

連結清單

連結清單也是一種經常被使用的一種資料結構。連結清單中的每一個元素都至少有兩個元素，一個指向它的下一個元素，一個用來存放它自己的資料，就像下面定義的那樣：

typedef struct _namelist namelist;
struct
{
  struct _namelist *next;
  char *name;
}_namelist;      

我們可以聲明一個其類型的元素：

static namelist *people;      

假設每一個元素都代表一個人，元素中的name屬性便是這個人的名字，我們通過這樣的語句來得到它：people->name; 第二個屬性指向後面的一個元素，那我們便可以這樣來通路下一個人的名字：people->next->name, 或者下一個人的下一個人的名字：people->next->next->name,一次類推，直到next的值是NULL，代表結束。

//通過一個循環來周遊這個連結清單中的所有人～
void name_show(namelist *p)
{
  while (p)
  {
    printf("Name: %s\n", p->name);
    p = p->next;
  }
}      

連結清單可以被用來實作FIFO模式，達到先進者先出的目的！

static namelist *people = NULL, *last_person = NULL;
void name_add(namelist *person)
{
    person->next = NULL;
    if (!last_person) {
        /* No one in the list yet */
        people = last_person = person;
        return;
    }
    /* Append new person to the end of the list */
    last_person->next = person;

    /* Update the list tail */
    last_person = person;
}
namelist *name_pop(void)
{
    namelist *first_person = people;
    if (people) {
        people = people->next;
    }
    return first_person;
}      

這樣，我們便可以随意的向這個連結清單中添加或者删除資料，而不向數組那樣，謹慎的考慮是否越界等問題。

上面實作的結構的學名叫做單向連結清單，也有地方叫單連結清單，反正是比較簡單的意思～。它有一個緻命的缺點，就是我們在插入或者讀取某條資料的時候，都需要從這個連結清單的開始，一個個元素的向下尋找，直到找到這個元素為止。如果連結清單中的元素比較多，那它很容易成為我們程式中的CPU消耗大戶，進而引起性能問題。為了解決這個問題，先人們發明了雙向連結清單：

typedef struct _namelist namelist;
struct
{
  namelist *next, *prev;
  char *name;
} _namelist;      

改動其實不大，就是在每個元素中都添加了一個prev屬性，用來指向它的上一個元素。

void name_add(namelist *person)
{
  person->next = NULL;
  if (!last_person)
  {
    /* No one in the list yet */
    people = last_person = person;
    person->prev = NULL;
    return;
  }
  /* Append new person to the end of the list */
  last_person ->next = person;
  person->prev = last_person;

  /* Update the list tail */
  last_person = person;
}      

單單通過上面的程式你還體會不到它的好處，但是設想一下，如果現在你有這個連結清單中其中一個元素的位址，并且想把它從連結清單中删除，那我們該怎麼做呢？如果是單向連結清單的話，我們隻能這樣做：

void name_remove(namelist *person)
{
    namelist *p;
    if (person == people) {
        /* Happens to be the first person in the list */
        people = person->next;
        if (last_person == person) {
            /* Also happens to be the last person */
            last_person = NULL;
        }
        return;
    }
    /* Search for prior person */
    p = people;
    while (p) {
        if (p->next == person) {
            /* unlink */
            p->next = person->next;
            if (last_person == person) {
                /* This was the last element */
                last_person = p;
            }
            return;
        }
        p = p->next;
    }
    /* Not found in list */
}      

現在讓我們來看看雙向連結清單是怎樣來處理這個問題的：

void name_remove(namelist *person)
{
    if (people == person) {
        people = person->next;
    }
    if (last_person == person) {
        last_person = person->prev;
    }
    if (person->prev) {

        person->prev->next = person->next;
    }
    if (person->next) {
        person->next->prev = person->prev;
    }
}      

對元素的周遊查找不見了，取而代之的是一個O(1)的運算，這将極大的提升我們程式的性能。

王者歸來：HashTable才是我們的銀彈！

也許你已經非常喜歡使用數組或者連結清單了，但我還是要向你推薦一種威力極大的資料結構，有了它之後，你可能會立即抛棄前兩者，它就是HashTable.