---
title: Data Structure
description:
---

# DS
###### tags: `Interview`

## Array vs Linked List

### Array

* 優點
* Random access，利用`index`即可在`O(1)`作存取。
* 較`Linked List`節省`記憶體空間`，因為`Linked List`需要一個`next pointer`來存下一個`Node`的位置。
* 缺點
* `新增/刪除`麻煩，若要更新`第一個`位置，就需要`O(N)`的時間來往前/往後後面的元素。
* 若`資料數量`常常在改變，就要常常調整`Array size`，也會花`O(N)`再搬動資料。

* 使用時機
* 希望能`快速存取`資料
* `已知資料數量`
* 要求的`記憶體空間越少越好`

### Linked List
* 優點
* `新增/刪除`較`Array簡單`，只要`O(1)`去更新`next pointer`就好了。
* `資料數量`可動態增加，不像`Array`有`resize`的問題。
* 缺點
* 找到特定的`Node`需要`O(N)`的時間去遍歷`List`。
* 要額外的記憶體來存`next pointer。
* 使用時機
* 無法預知`資料數量`的時候。
* 需要頻繁`更動資料`的時候。
* 不需要`快速查詢資料`的時候。

## Stack vs Queue

### Stack
* 優點
* LIFO
* 缺點
* 使用時機
* 應用
* 編譯器(word、sublime)的 undo 。
* 網頁瀏覽器中回到上一頁功能。
* 任何遞迴(recursion)形式的演算法都可以用Stack改寫。
* DFS
### Queue
* 優點
* FIFO
* 缺點
* 使用時機
* 應用
* Linux scheduling
* BFS