---
# System prepended metadata

title: Data Structure
tags: [Interview]

---

---
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 







