數(shù)組

數(shù)組（Array） 是一種線性表（Linear List）數(shù)據(jù)結構。它用一組連續(xù)的內存空間(對內存要求比較高)，來存儲一組具有相同類型的數(shù)據(jù)。
因如上特點，通過尋址公式，可隨機訪問數(shù)組中元素，時間復雜度為O（1）。但為保證連續(xù)性，在數(shù)組中刪除插入數(shù)據(jù)時，需要做大量數(shù)據(jù)搬移工作，時間復雜度是O（n）
小技巧：插入操作做成兩個元素互換；刪除操作先記錄下已刪除的數(shù)據(jù)再統(tǒng)一刪除。（JVM標記清除垃圾回收算法）

數(shù)組從0開始編號：考慮尋址公式 a[k]_address = base_address + k * type_size，便于計算。另歷史原因，java沿用C習慣

ArrayList（容器類）：將很多數(shù)組操作的細節(jié)封裝起來，如插入刪除搬移數(shù)據(jù)。支持動態(tài)擴容（擴為1.5倍）。但擴容耗時，最好事先指定數(shù)據(jù)大小。

Array優(yōu)勢：省去自動裝箱拆箱的性能消耗，多維數(shù)組更直觀，操作簡單用不到ArrayList大部分方法時可直接用數(shù)組。

鏈表

鏈表（Linked List）通過指針將一組零散的內存塊串聯(lián)起來使用。
結點：即內存塊，存儲數(shù)據(jù)并記錄鏈上下一個結點的地址，記錄下一個結點地址的指針叫后繼指針next。頭結點記錄鏈表基地址，尾結點指向空地址NULL。
單鏈表 的插入刪除操作只需要考慮相鄰結點的指針改變，時間復雜度O(1)
單鏈表 隨機訪問需根據(jù)指針一個結點一個結點依次遍歷，時間復雜度O(n)
循環(huán)鏈表 尾結點指針指向鏈表頭結點，處理環(huán)形結構的數(shù)據(jù)方便。
雙向鏈表 每個結點有后繼指針next和前驅指針prev，需額外兩個控件存儲后繼和前驅指針地址，占內存。但支持雙向遍歷，操作靈活，查找遍歷高效。

LinkedHashMap實現(xiàn)用到雙向鏈表結構。

空間換時間設計思想：內存充足時可選擇空間復雜度較高時間復雜度較低的算法或數(shù)據(jù)結構，否則相反。
數(shù)組與鏈表：數(shù)組連續(xù)存儲對CPU緩存友好，鏈表不友好，鏈表需存儲指向下一個結點的指針地址更耗內存，且對鏈表頻繁插入刪除容易造成內存碎片（Java頻繁GC）；數(shù)組大小固定，鏈表沒有大小限制天然支持擴容；
指針：將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針，或者反過來說，指針中存儲了這個變量的內存地址，指向了這個變量，通過指針就能找到這個變量。
帶頭鏈表不管鏈表是否為空，head指針一直指向不存儲數(shù)據(jù)的哨兵結點。

因為哨兵結點一直存在，所以插入/刪除第一個結點或其他結點都可以統(tǒng)一為相同的代碼實現(xiàn)，這種利用哨兵簡化編程難度的技巧很常用，如插排，歸并，動態(tài)規(guī)劃等。

常見的緩存淘汰策略：先進先出（ FIFO）,最少使用（LFU），最近最少使用（LRU，可考慮有序單鏈表實現(xiàn)，新入列存表頭）

棧

棧(Stack)結構 操作受限的線性表數(shù)據(jù)結構，只允許在一端插刪數(shù)據(jù)(入棧出棧)，先進后出，后進先出。
順序棧 用數(shù)組實現(xiàn)，操作棧頂指針，入棧出棧空間復雜度O(1)；可改造以支持動態(tài)擴容，則入棧需重新申請內存和數(shù)據(jù)搬移時，時間復雜度O(n)，按攤還分析法，入棧均攤時間復雜度為O(1)。
鏈式棧 用鏈表實現(xiàn)，入棧出棧空間復雜度O(1)。

應用：函數(shù)調用棧；編譯器實現(xiàn)表達式求值；括號匹配；使用兩個棧實現(xiàn)瀏覽器前進后退

隊列

隊列(Queue) 同為操作受限的線性表數(shù)據(jù)結構，支持入隊出隊，先進先出。
順序隊列 用數(shù)組實現(xiàn)有界隊列，操作隊頭(head)指針，隊尾(tail)指針,判斷隊空(head == tail)隊滿(tail == n)需考慮數(shù)據(jù)搬移的成本，入隊隊滿時統(tǒng)一處理搬移。

大部分資源有限的場景如線程池請求排隊，數(shù)據(jù)庫連接池等，沒有空閑資源時基本上都可以通過“隊列”實現(xiàn)請求排隊。

鏈式隊列 用鏈表實現(xiàn)，可實現(xiàn)一個支持無限排隊的無界隊列（過多等待響應時間過長）
循環(huán)隊列 避免數(shù)據(jù)搬移，關鍵要確定好隊空(head == tail)和隊滿((tail + 1)%n==head)的判定條件
阻塞隊列隊列為空阻塞隊頭讀取操作，隊列已滿阻塞插入操作，可用于實現(xiàn)生產者-消費者模型。
并發(fā)隊列線程安全的隊列

應用：具有額外特性的隊列如循環(huán)隊列，阻塞隊列，并發(fā)隊列，在很多偏底層系統(tǒng)框架中間件的開發(fā)中起關鍵作用。如高性能隊列Disruptor，Linux環(huán)形存儲（循環(huán)并發(fā)隊列）；Java concurrent 并發(fā)包用ArrayBlockingQueue實現(xiàn)公平鎖。

跳表

跳表(Skip List) 是一種加多級索引結構的鏈表，是一種優(yōu)秀的動態(tài)數(shù)據(jù)結構，實現(xiàn)了基于鏈表的“二分查找”，支持快速插入刪除查找，實現(xiàn)不復雜
查詢數(shù)據(jù)的時間復雜度：O(logn) , ??：n個數(shù)據(jù)，建h級索引，最高級索引有兩個結點，故n/(2h)=2，h=(log2n)-1，設每層最多遍歷m個結點，則時間復雜度O(mlogn)
空間復雜度：O(n) ，為等比數(shù)列相加和，??：若每2個結點抽1個，則和為(n/2+n/4+n/8+...+8+4+2)=n-2，間隔越大和越小，且存儲的數(shù)據(jù)對象占用空間越大，索引空間占比越小
動態(tài)更新： 通過隨機函數(shù)維護索引與原始鏈表大小間的平衡性，隨機函數(shù)決定將結點插入到哪幾級索引。避免出現(xiàn)某幾個索引結點之間數(shù)據(jù)非常多復雜度退化(極端情況退化成單鏈表)，查找插入刪除性能下降

跳表結構查詢刪除插入數(shù)據(jù)實現(xiàn)較簡單，可讀性好，且區(qū)間查找數(shù)據(jù)效率優(yōu)于紅黑樹；但紅黑樹出現(xiàn)早，很多編程語言中的Map類型都是通過紅黑樹實現(xiàn)，而跳表沒有現(xiàn)成的實現(xiàn)

散列表

散列表(Hash Table) 源于數(shù)組，利用數(shù)組支持按下標隨機訪問元素的特性，借助散列函數(shù)進行拓展
散列函數(shù)：hash(key) key為元素鍵值，hash(key)為經過散列函數(shù)計算得到的散列值 ，要求

• 散列函數(shù)計算得到的散列值是一個非負整數(shù)
• 如果 key1 = key2，那hash(key1)==hash(key2)
• 如果key1≠key2，那hash(key1)≠hash(key2)
  第三點要求即避免散列沖突
  **散列沖突： ** 想完全避免散列沖突幾乎不可能，常用的解決沖突的辦法有兩類開放尋址法(open addressing)和鏈表法(chaining)

1. 開放尋址法
   • 核心思想：重新探測一個空閑位置插入數(shù)據(jù)
   • 線性探測(Linear Probing) 往散列表插入數(shù)據(jù)時，若某個數(shù)據(jù)經過散列函數(shù)散列后，存儲位置已被占用，則從當前位置開始依次往后查找看是否有空閑位置，找到為止；查找元素同，如果遍歷到數(shù)組中空閑位置還沒找到說明要查找到元素并沒有在散列表中；刪除元素將元素特殊標記為deleted；極端情況需探測整張散列表，最壞情況時間復雜度O(n)
   • 二次探測(Quadratic probing) 較線性探測，步長變?yōu)樵瓉矶畏?hash(key)+0, hash(key)+12, hash(key)+22
   • 雙重散列(Double hashing) 使用一組散列函數(shù) hash1(key), hash2(key), hash3(key)... ...
   • 優(yōu)缺點：數(shù)據(jù)存儲在數(shù)組中，查詢快；不含指針，序列化容易實現(xiàn)；數(shù)組存儲內存利用率低；刪除數(shù)據(jù)麻煩；沖突代價高，裝載因子不能太大
   • 適用：適合數(shù)據(jù)量比較小，裝載因子小的時候，如Java中的ThreadLocalMap

用裝載因子表示空位多少
散列表的裝載因子 = 填入表中的元素個數(shù) / 散列表的長度

2. 鏈表法
   • 核心思想：每個“桶”或者“槽”對應一條鏈表，所有散列值相同的元素放到相同槽位對應的鏈表中
   • 時間復雜度：插入O(1)，查找刪除時間復雜度O(k)(鏈表長度k，理論上均勻散列函數(shù)k=n/m，m為槽點個數(shù))
   • 優(yōu)缺點：鏈表結點需要時創(chuàng)建，內存利用率高；裝載因子容忍度高；鏈表對較小數(shù)據(jù)因為要存儲指針比較耗內存；零散分布內存不友好
   • 適用：適合存儲大對象，大數(shù)據(jù)量散列表
   • 改良方案：將鏈表改為更高效的動態(tài)數(shù)據(jù)結構如跳表，紅黑樹，這樣即便都散列到一個桶內時間也不過O(logn)，即可避免散列碰撞攻擊

樹

樹(Tree) 里每個元素稱為節(jié)點，用來連線相鄰節(jié)點的關系叫父子關系，共有同一個父節(jié)點的節(jié)點間稱為兄弟節(jié)點，沒有父節(jié)點的節(jié)點稱為根節(jié)點，沒有子節(jié)點的節(jié)點稱為葉子節(jié)點；
節(jié)點的高度 = 節(jié)點到葉子邊數(shù)
節(jié)點深度 = 根節(jié)點到這個節(jié)點邊樹
節(jié)點層數(shù) = 節(jié)點的深度 + 1
樹的高度 = 根節(jié)點的高度

• 二叉樹(只有左右兩個子節(jié)點)
  滿二叉樹： 除葉子節(jié)點，每個節(jié)點都有左右兩個子節(jié)點
  完全二叉樹： 葉子節(jié)點都在最底下兩層；最后一層葉子節(jié)點都靠左排列；除底層外各層節(jié)點個數(shù)達到最大
  鏈式存儲法： 每個節(jié)點有三個字段分別存儲數(shù)據(jù)，指向左子節(jié)點的指針和指向右子節(jié)點的指針，較常用
  順序存儲法： 根節(jié)點位置i=1，左子節(jié)點2i=2，右子節(jié)點2i+1=3，類推；完全二叉樹運用順序存儲占用的是連續(xù)空間省內存，非完全二叉樹會浪費存儲空間；數(shù)組存儲方式不需要存儲額外的左右子節(jié)點指針，更省內存
• 二叉樹的遍歷
  前序遍歷： 節(jié)點->左子樹->右子樹
  中序遍歷： 左子樹->節(jié)點->右子樹
  后序遍歷： 左子樹->右子樹->節(jié)點
  時間復雜度： O(n)，因遍歷過程每個節(jié)點最多被訪問兩次，與節(jié)點個數(shù)n成正比
  代碼示例：

void preOrder(Node* root) {
  if (root == null) return;
  print root // 此處為偽代碼，表示打印 root 節(jié)點
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此處為偽代碼，表示打印 root 節(jié)點
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此處為偽代碼，表示打印 root 節(jié)點
}

• 二叉查找樹(Binary Search Tree)
  定義 樹中任意節(jié)點，左子樹中每個節(jié)點值小于這個節(jié)點值，右子樹每個節(jié)點的值都大于這個節(jié)點的值

  • 查找操作
    代碼實現(xiàn)：

public class BinarySearchTree {
  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

• 插入操作
  代碼實現(xiàn)：

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

• 刪除操作
  核心思想： 待刪除節(jié)點沒有子節(jié)點，則直接將父節(jié)點指向該節(jié)點的指針置null；待刪除節(jié)點只有一個子節(jié)點，則更新父節(jié)點指向刪除節(jié)點的指針，指向該子節(jié)點；待刪除節(jié)點有兩個節(jié)點，則找到該節(jié)點右子樹中最小節(jié)點，替換到要刪除的節(jié)點上
  代碼實現(xiàn)：

public void delete(int data) {
  Node p = tree; // p 指向要刪除的節(jié)點，初始化指向根節(jié)點
  Node pp = null; // pp 記錄的是 p 的父節(jié)點
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 沒有找到

  // 要刪除的節(jié)點有兩個子節(jié)點
  if (p.left != null && p.right != null) { // 查找右子樹中最小節(jié)點
    Node minP = p.right;
    Node minPP = p; // minPP 表示 minP 的父節(jié)點
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 將 minP 的數(shù)據(jù)替換到 p 中
    p = minP; // 下面就變成了刪除 minP 了
    pp = minPP;
  }

  // 刪除節(jié)點是葉子節(jié)點或者僅有一個子節(jié)點
  Node child; // p 的子節(jié)點
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 刪除的是根節(jié)點
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

• 重復數(shù)據(jù)處理辦法
  1. 通過鏈表和支持動態(tài)擴容的數(shù)組等數(shù)據(jù)結構把值存儲在同一個節(jié)點上
  2. 將相同數(shù)據(jù)插入右子樹

中序遍歷二叉查找樹，可以輸出有序數(shù)據(jù)序列，時間復雜度O(n)，非常高效

要點補充：遞歸

遞歸需滿足的三個條件

• 一個問題的解可分解為幾個子問題的解 （思考時假設子問題已解決，屏蔽遞歸細節(jié)）
• 這個問題與分解之后的子問題，除數(shù)據(jù)規(guī)模不同，求解思路完全一樣
• 存在遞歸終止條件

編寫遞歸代碼的關鍵點

• 寫出遞推公式
• 找到終止條件

n級臺階的走法：f(n) = f(n - 1) + f(n - 2)，終止條件為f(1) = 1, f(2) = 2
?int f(int n) {
??if (n == 1) return 1;
?? if (n == 2) return 2;
??return f(n - 1) + f(n - 2);
?}

遞歸代碼需警惕的點

• 堆棧溢出 ：遞歸求解數(shù)據(jù)規(guī)模較大，調用層次深一直壓入棧，有堆棧溢出的風險?？稍诖a中限制遞歸調用最大深度解決該問題(實際跟當前線程剩余?？臻g大小有關，深度較小適用)。
• 重復計算 ： 可通過一個數(shù)據(jù)結構（如散列表）保存已求解過的f(k)，調用時先檢查。
• 時間效率
• 空間開銷
• 臟數(shù)據(jù)造成的無限遞歸和遞歸環(huán)

參考：《數(shù)據(jù)結構與算法之美》王爭