前兩天開始認識演算法後，我一直看到另一個很常一起出現的名詞：資料結構（Data Structure）。

資料結構的定義就是：

「資料結構（Data Structure）是電腦中儲存、組織資料的方式。」

這句定義引用自 Chupai－資料結構，也讓我開始理解：資料不只是「存起來」，怎麼組織資料也是一件重要的事。

為什麼資料需要「結構」？

假設今天有 10 萬張學生的考卷全部放在一個倉庫裡。

現在我要找：

一年級、A 班、生物科的考卷。

如果這 10 萬張考卷完全沒有整理，可能就只能從第一張開始，一張一張確認：

這張是一年級嗎？是 A 班嗎？是生物科嗎？

直到找到我要的考卷。

但如果一開始就按照某種方式整理：

所有考卷
│
├── 一年級
│   ├── A 班
│   │   ├── 國文
│   │   ├── 數學
│   │   └── 生物
│   └── B 班
│
├── 二年級
│
└── 三年級

那麼當我要找「一年級 → A 班 → 生物科」時，就可以逐漸縮小尋找的範圍，而不是每次都面對全部 10 萬張考卷。

當然，實際上電腦中的資料結構並不等於「把考卷分類」這麼簡單。

但這個例子讓我開始理解一件事情：

同樣都是資料，「怎麼組織」會影響我們之後可以怎麼處理它。

而資料結構，就是在處理這件事情。

資料結構還分成「線性」跟「非線性」？

資料結構可以從資料之間的關係，初步理解成線性與非線性。

線性資料結構可以想成「排隊」：

A → B → C → D

資料一個接著一個，常見的 Array、Stack、Queue 都可以先這樣理解。

非線性資料結構則不一定只有單純的前後關係，例如 Graph：

    B
   / \
  A   D
   \ /
    C

一筆資料可能同時與多筆資料產生關係。

原來這些都是資料結構？

Array（陣列）

Array（陣列）其實是前端非常熟悉的東西：

const scores = [80, 65, 90, 72];

資料按照一定的順序排列，並且可以透過索引（index）直接存取指定位置：

index     0     1     2     3

        ┌────┬────┬────┬────┐
        │ 80 │ 65 │ 90 │ 72 │
        └────┴────┴────┴────┘

Stack（堆疊）

Stack（堆疊）則像疊盤子，最後放上去的盤子會最先被拿走，也就是：

LIFO（Last In, First Out，後進先出）

假設今天依序放入三個盤子：

        ↓ 放入

      ┌─────┐
      │  C  │ ← 最後放入
      ├─────┤
      │  B  │
      ├─────┤
      │  A  │ ← 最先放入
      └─────┘

如果現在要拿盤子，通常會先拿最上面的 C。

Graph（圖）

Graph（圖）則適合描述資料之間的連結關係。

假設今天有四個地點：

A ──5── B
│       │
2       3
│       │
C ──1── D

A、B、C、D 可以看成不同的地點。

這些地點稱為節點（Vertex / Node），節點之間的連線則稱為邊（Edge），而線上的數字可以代表兩個地點之間的距離。

這時候就出現了一個很有趣的問題：

如果今天我要從 A 走到 D，怎麼走才是最短的？

Graph 幫我們描述了：

「有哪些地點，以及這些地點之間有什麼關係。」

但要怎麼從這些路線裡找出最短路徑，就是另一個問題了。

而這也是之後預計會學到的 Dijkstra 演算法要解決的問題。

所以資料結構跟演算法有什麼關係？

我覺得可以用這一句話來說明：

資料結構決定「資料怎麼被組織」，演算法決定「資料要怎麼被處理」。

參考資料

• Chupai，〈資料結構〉
  https://chupai.github.io/posts/200419_data_structure/

• Jimmy's Web Note，〈Array、Linked List〉
  https://jimmyswebnote.com/article/array-linked-list/

• Hello 演算法，〈資料結構分類〉
  https://www.hello-algo.com/zh-hant/chapter_data_structure/classification_of_data_structure/