數組
數組是一個線性表，存儲相同數據結構的連續的內存空間。
數組的優劣
一：優勢
隨機訪問時間複雜度為常數級別。
支持cpu緩存，訪問速度更加快速。（因為內存空間是連續的所以知道收地址的內存地址，cpu緩存就可以預讀整個數組的所有數據。）
一維數組的內存計算公式：a[i]address = base_address + （i-1）*data_type_size
二維數組的內存計算公式： address = base_address + ( i * n + j) * type_size
二劣勢 刪除慢 刪除一個數據需要進行數據搬移，是非常耗時的
優化 對刪除的數據進行標記，不刪除，當數組的存儲空間不足的時候，在進行一次整體的刪除操作，減少了搬移的次數（垃圾回收機制的標記清楚算法）
插入慢 插入數據的時候，數據搬移
優化 針對有序數組沒發優化
無序數組 插入的新數據都插入末尾
跟要插入的數據進行交換。
大小有限，警惕數組索引越界（java.lang.ArrayIndexOutOfBoundsException）
容器與數組的對比 優勢 容器最大的優勢就是1將數組的操作細節封裝了起來。2.支持動態擴容。
二：劣勢 容器不能存儲基本數據類型
數組效率高（知道數據大小的情況下）（底層開發數組的效率更高）
多維情況下，數組更加直觀
leetcode題目（移動零）：
class Solution {
//first solution
//1.just find non-zero data 2.finally fill of all zero data.3.index is non-zero data's count.
public void moveZeroes(int[] nums) {
int index = 0;
for(int num:nums){
if(num!=0){
nums[index++]=num;
}
}
while(index<nums.length>
nums[index++] = 0;
}
}
//second solution
//1.tow pointer ,first pointer is the first zero data's address,second pointer is the foreach count.
public void moveZeroesSecond(int[] nums){
//first pointer
int i = 0;
//second pointer
int j = 0;
for(; j< nums.length; j++){
//if nums[j] != 0 i++
if( nums[j] != 0 ) {
// exchage condition
if( i != j){
exchage(i,j,nums);
}
i++;
}
}
}
private void exchange(int[] nums, int i, int j) {
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
}
複製代碼鏈表
鏈表的分類：
單向鏈表
雙向鏈表
循環鏈表
靜態鏈表
鏈表的優劣：
優勢 刪除，插入快
劣勢 隨機訪問慢
頻繁的刪除插入容易產生內存碎片，造成頻繁的gc
鏈表實戰
1.鏈表環形檢測（leetcode）：
//給定一個鏈表，判斷鏈表中是否有環。
//
// 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。
//
//
//
// 示例 1：
//
// 輸入：head = [3,2,0,-4], pos = 1
//輸出：true
//解釋：鏈表中有一個環，其尾部連接到第二個節點。
//
//
//
//
// 示例 2：
//
// 輸入：head = [1,2], pos = 0
//輸出：true
//解釋：鏈表中
"/<nums.length>閱讀更多 用戶名被佔用了 的文章
