1.概述1.1資料結構
資料結構(data structure)是計算機儲存、組織資料的方式。資料結構是指相互之間存在一種或多種特定關係的資料元素的集合。一句話解釋：存資料的，而且是在記憶體中存！
1.2演算法演算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。一句話描述：演算法是一種解決特定問題的思路。
1.3時間複雜度int sum(int n){ int s=0; //t int i=1; //t for(;i<=n;i++){ //t*n s=s+i; //t*n } return s; //t}上例中，時間複雜度為O(n)，也就是程式碼執行時間隨著資料規模的增加而增長 。
int sum(int n){ int s=0; int i=1; int j=1; for(;i<=n;i++){// n j=1; for(;j<=n;j++){ //n*n s=s+i+j; //n*n } } return s;}上例中T(n)=O(n*n)，也就是程式碼執行時間隨著資料規模的增加而平方增長,即：上例中的時間複雜度為O(n2) .
計算時間複雜度的技巧:
· 計算迴圈執行次數最多的程式碼
· 總複雜度=量級最大的複雜度
常見的時間複雜度：
· O(1) ：程式碼的執行不隨著資料規模(n)的增加而增加，比如:SDS、字典、跳躍表等
· O(logn)、O(nlogn) ：
i = 1;while(i <= n){ i = i * 2;// 執行最多}· 2^x=n,x=log2n,忽略係數，logn,如果將該程式碼執行n遍 ,時間複雜度記錄為:T(n)=O(n*logn），即O(nlogn) ,比如快速排序、歸併排序的時間複雜度都是O(nlogn)
· O(m+n) ：
for(;i<=m;i++){s1=s1+i; // 執行最多} for(;j<=n;j++){s2=s2+j; //執行最多}· m和n是程式碼的兩個資料規模，而且不能確定誰更大，此時程式碼的複雜度為兩段時間複雜度之和,這種應該也可以算作一種特殊的O(n)
· O(m*n) ：
for(;i<=m;i++){// m j=1; for(;j<=n;j++){ //m*n s=s+i+j; //m*n }}· 根據乘法法則程式碼的複雜度為兩段時間複雜度之積，即T(n)=O(mn)，記作：O(mn)當m==n時,為O() .
2.資料結構和演算法基礎2.1線性表2.1.1 陣列陣列（Array）是有限個相同型別的變數所組成的有序集合，陣列中的每一個變數被稱為元素。陣列是最為簡單、最為常用的資料結構。
儲存原理：陣列用一組連續的記憶體空間來儲存一組具有相同型別的資料。
陣列可以根據下標隨機訪問資料，比如int[]陣列，int是4位元組 ，a[i]address=a[0]address+i*4 ，瞬間定址到對應的地址。由此公式也可以看出陣列下標要從0開始，如果是1開始，公式還得再減去1個數（4）。也就是說第一個元素是不需要偏移量的。
陣列的操作
· 讀取元素：根據下標讀取元素的方式叫作隨機讀取 例如 int n=nums[2]
· 更新元素：nums[3]= 10; 注意陣列下標越界
· 插入元素
· 尾部插入：在資料的實際元素數量小於陣列長度的情況下，直接把插入的元素放在陣列尾部的空閒位置
· 中間插入：在資料的實際元素數量小於陣列長度的情況下 ，由於陣列的每一個元素都有其固定下標，所以首先把插入位置及後面的元素向後移動，騰出地方，再把要插入的元素放到對應的陣列位置上
·
· 超範圍插入：陣列元素已經存滿了，此時再進行插入，就需要對陣列擴容了。
·
時間複雜度
讀取和更新都是隨機訪問，時間複雜度O(1)
插入涉及擴容、移動元素等操作，時間複雜度是O(n)
優缺點
優點：非常高效的隨機訪問能力，下標隨機訪問
應用：陣列是基礎的資料結構，應用太廣泛了，ArrayList、Redis、訊息佇列等等。
2.1.2 連結串列概念
連結串列（linked list）是一種在物理上非連續、非順序的資料結構，由若干節點（node）所組成。連結串列中資料元素的邏輯順序是透過連結串列中的指標連結次序實現，每個結點包括兩個部分：一個是儲存資料元素的資料域，另一個是儲存下一個結點地址的指標域。常見的連結串列包括：單鏈表，雙向連結串列，迴圈連結串列。
· 單鏈表
· 單向連結串列的每一個節點又包含兩部分，一部分是存放資料的變數data，另一部分是指向下一個節點的指標next
·
public class Node { int id; String name; //下一個節點 Node next;}· 雙向連結串列
· 雙向連結串列的每一個節點除了擁有data和next指標，還擁有指向前置節點的prev指標。
·
public class Node2 { int id; String name; //下一個節點 Node2 next; //上一個節點 Node2 prev;}· 迴圈連結串列
· 連結串列的尾節點指向頭節點形成一個環，稱為迴圈連結串列。
·
儲存結構：連結串列的每一個節點分佈在記憶體的不同位置，依靠next指標關聯起來。這樣可以靈活有效地利用零散的碎片空間。
連結串列操作
· 查詢節點：在查詢元素時，連結串列只能從頭節點開始向後一個一個節點逐一查詢。
·
· 更新節點：找到要更新的節點，然後把舊資料替換成新資料
·
· 插入節點
· 尾部插入：把最後一個節點的next指標指向新插入的節點即可
·
· 頭部插入：把新節點的next指標指向原先的頭節點 ，把新節點變為連結串列的頭節點
·
· 中間插入：新節點的next指標，指向插入位置的節點，插入位置前置節點的next指標，指向新節點
· 只要記憶體空間允許，能夠插入連結串列的元素是無限的，不需要像陣列那樣考慮擴容的問題
·
·
時間複雜度
查詢節點O(n)，只能從head開始一個一個往下找。
插入節點O(1),不包括查詢部分
更新節點O(1),不包括查詢部分
優缺點
劣勢：查詢效率低，不能隨機訪問
應用：連結串列的應用也非常廣泛，比如樹、圖、Redis的列表、LRU演算法實現、訊息佇列等
2.1.3 陣列 Vs 連結串列陣列優勢：快速定位，對於讀操作多於寫操作的場景來說，陣列更適合一些
陣列和連結串列是線性資料儲存的物理儲存結構：即順序儲存和鏈式儲存
2.1.4 棧棧（stack）是一種線性資料結構，棧中的元素只能先入後出（First In Last Out，簡稱FILO）。最早進入的元素存放的位置叫作棧底（bottom），最後進入的元素存放的位置叫作棧頂 （top）。
儲存原理
棧既可以用陣列來實現，也可以用連結串列來實現。
陣列實現方式：又叫做順序棧或者靜態棧。
連結串列實現：又叫鏈式棧或者動態棧。
棧的操作
入棧（push）：就是把新元素放入棧中，只允許從棧頂一側放入元素，新元素的位置將會成為新的棧頂
出棧（pop）:就是把元素從棧中彈出，只有棧頂元素才允許出棧，出棧元素的前一個元素將會成為新的棧頂
演示程式碼：
基於陣列實現的棧：
package com.david.line.stack;/** * 基於陣列實現的棧 */public class ArrayStack { private int[] nums; // 陣列資料 private int count; // 棧中元素個數 // 初始化陣列，申請一個大小為n的陣列空間 public ArrayStack(int n) { this.nums = new int[n]; this.count = 0; } // 入棧操作 public boolean push(int n) { // 陣列空間不夠了，直接返回false，入棧失敗。暫時不考慮擴容 // nums.len*2 arraycopy if (count >= nums.length) return false; // 將item放到下標為count的位置，並且count加一 nums[count] = n; count++; return true; } // 出棧操作 public int pop() { // 棧為空，則直接返回0 if (count == 0) return 0; // 返回下標為count-1的陣列元素，並且棧中元素個數count減一 int n = nums[count-1]; count--; return n; }}基於連結串列實現的棧：
package com.david.line.stack;public class LineStack { int size; Node head; //頭節點 /** * 初始化 */ public LineStack() { head = null; size = 0; } /** * 入棧 * @param node */ public void push(Node node) { //head if (size == 0) { head = node; }else {//非head //head node.next = head; head = node; } size++; } /** * 出棧，直接返回 * @return */ public Node pop() { if (size > 0) { Node oldHead = head; head = head.next; size--; return oldHead; } else { return null; } }}class Node { int value; Node next; public Node(int value) { this.value = value; }}時間複雜度：出棧的時間複雜度是O(1),入棧連結串列是O(1),陣列連結串列如果不擴容時間複雜度是O(1),擴容是O(N).
應用：
1. 函式引數呼叫，每進入一個函式，就會將臨時變數作為一個棧入棧，當被呼叫函式執行完成，返回之後，將這個函式對應的棧幀出棧。
1. 瀏覽器的後退功能
2.1.5 佇列佇列（queue）是一種線性資料結構，佇列中的元素只能先入先出（First In First Out，簡稱 FIFO）。佇列的出口端叫作隊頭（front），佇列的入口端叫作隊尾（rear）。
儲存原理：佇列這種資料結構既可以用陣列來實現，也可以用連結串列來實現
陣列實現
用陣列實現時，為了入隊操作的方便，把隊尾位置規定為最後入隊元素的下一個位置。用陣列實現的佇列叫作順序佇列。
連結串列實現
用連結串列實現的佇列叫作鏈式佇列，注意佇列的進出方向和連結串列的指向是相反的。
佇列操作
入隊（enqueue）把新元素放入佇列中，只允許在隊尾的位置放入元素，新元素的下一個位置將會成為新的隊尾。
出隊（dequeue）:把元素移出佇列，只允許在隊頭一側移出元素，出隊元素的後一個元素將會成為新的隊頭
程式碼演示：
基於陣列的佇列：
package com.david.line.queue;/** * 基於陣列實現的佇列 */public class ArrayQueue { // 陣列：items，陣列大小：n int[] nums; // head表示隊頭下標，tail表示隊尾下標 int head = 0; int tail = 0; /** * 初始化申請一個大小為capacity的陣列 */ public ArrayQueue(int size) { nums = new int[size]; } /** * 入隊 * @param n 資料 * @return */ public boolean enqueue(int n) { // 如果tail == nums.length 表示佇列已經滿了，暫時不考慮擴容 if (tail == nums.length) return false; nums[tail] = n; ++tail; return true; } /** * 出隊 * @return 返回出隊資料 */ public int dequeue() { // 如果head == tail 表示佇列為空 if (head == tail) return 0; int ret = nums[head]; ++head; return ret; }}基於連結串列的佇列：
package com.david.line.queue;public class LinkedQueue { Node head; //隊頭 Node tail; //隊尾 int size; /** * 入隊 * @param node */ public void enqueue(Node node) { if (tail == null) { head = node; tail = node; } else { tail.next = node; tail = node; } size++; } /** * 出隊 * @return */ public Node dequeue (){ if (head == null) return null; Node h = head; //將拉取的節點的下一個節點變成新的表頭 head = head.next; //把舊的表頭的下一個節點指向設定為null，讓gc回收 h.next = null; //佇列為空 if (head == null) tail = null; size--; return h; }}class Node { int value; Node next; public Node(int value) { this.value = value; }}