緩存策略
1，F(xiàn)IFO（first in first out）先進先出
2夫壁，LFU（least frequently used）最少使用策略
3江滨，LRU（least recently used）最近最少使用策略
數(shù)組鏈表區(qū)別
數(shù)組
內(nèi)存連續(xù)
鏈表
內(nèi)存不連續(xù)
鏈表分類
單鏈表
雙向鏈表
循環(huán)鏈表
雙向循環(huán)鏈表
執(zhí)行較慢的程序
可以通過空間換時間來進行優(yōu)化
消耗過多內(nèi)存的程序油坝，可以通過時間換空間來降低內(nèi)存的消耗
鏈表數(shù)據(jù)使用
數(shù)據(jù)缺點大小固定，一經(jīng)聲明就要占用整塊的連續(xù)內(nèi)存空間
java中ArrayList使用動態(tài)擴容镇匀，但擴容時把原數(shù)組拷貝到擴充后的數(shù)組中是非常耗時的
如果對于代碼對內(nèi)存使用非痴赵澹苛刻就需要使用數(shù)組，因為鏈表每個結點指針都會占用內(nèi)存
對鏈表進行頻繁插入汗侵、刪除會導致頻繁內(nèi)存申請和釋放幸缕，容易造成內(nèi)存碎屏，java中也可能導致頻繁GC
LRU緩存淘汰算法
基于有序單鏈表事項LRU算法
維護一個有序單鏈表晰韵，越靠近鏈表尾部的結點是越早訪問的发乔。當有一個新的數(shù)據(jù)被訪問是，我們從鏈表頭開始順序遍歷鏈表
1雪猪，如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中栏尚，我們遍歷得到這個數(shù)據(jù)對應的結點，并將其從原來的位置刪除只恨，然后在插入到鏈表的頭部
2译仗，如果此數(shù)據(jù)沒有在緩存鏈表中，分為兩種情況
- 如果此時緩存未滿官觅，則將此結點直接插入到鏈表頭部
- 如果此時緩存滿了纵菌，則鏈表尾結點刪除，將新數(shù)據(jù)結點插入到鏈表的頭部
寫鏈表
寫鏈表技巧
1休涤，理解指針或引用的含義
將某個變量賦值給指針咱圆，實際上就是將這個變量的地址賦值給指針，或者返過來說功氨，指針中存儲了這個變量的內(nèi)存地址序苏，指向了這個變量，通過指針就能找到這個變量
2捷凄，警惕指針丟失和內(nèi)存泄露
3忱详，利用哨兵簡化實現(xiàn)難度
帶頭結點鏈表
//在數(shù)組a中,查找key,返回key所在的位置
int find(char* a,int n,char key){
if (a == NULL || n <= 0){
return -1;
}
int i =0;
while (i < n){
if (a[i] == key){
return i;
}
++i;
}
return -1;
}
//在數(shù)組a中,查找key,返回key所在的位置
int find2(char* a,int n,char key){
if (a == NULL || n <= 0){
return -1;
}
if (a[n -1] == key){
return n -1;
}
char tmp = a[n-1];
a[n-1] = key;
int i =0;
while (a[i] != key){
++i;
}
a[n-1] = tmp;
if (i == n-1){
return -1;
} else {
return i;
}
}
對比兩段代碼，在字符a很長時跺涤，第二段代碼更快匈睁，我們通過一個哨兵a[n-1]=key管钳，成功省略掉了一個比較語句
4，重點留意邊界條件處理
- 如果鏈表為空時软舌，代碼是否能正常工作
- 如果鏈表只包含一個結點，代碼是否能正常工作
- 如果鏈表只包含兩個結點牛曹，代碼是否能正常工作
- 代碼邏輯在處理頭結點和尾結點時佛点，是否能正常工作
5，舉例畫圖黎比，輔助思考
6超营，多練多寫沒有捷徑
創(chuàng)建鏈表頭插法，尾插法
LinkedList createListByHead(){
int arr[] = {4,5,6,7,8,89,9,2,2,34};
LinkedList head = malloc(sizeof(Node));
head->next =NULL;
for(int i = 0;i < 10;i++){
Node *p = malloc(sizeof(Node));
p->value=arr[i];
p->next = head->next;
head->next = p;
}
return head;
}
LinkedList createListByTail(){
int arr[] = {4,5,6,7,8,89,9,2,2,34};
LinkedList head = malloc(sizeof(Node));
head->next =NULL;
LinkedList p = head;
for(int i = 0;i < 10;i++){
Node *q = malloc(sizeof(Node));
q->value=arr[i];
q->next=NULL;
p->next = q;
p=p->next;
}
return head;
}
單鏈表反轉
//不帶頭結點單鏈表反轉
LinkedList reverseList(Node* head){
if (head == NULL){
return NULL;
}
if (head->next == NULL){
return head;
}
Node *root = head;
Node *pre = NULL;
Node *next = NULL;
while (root->next!= NULL){
next=root->next;
root->next=pre;
pre=root;
root=next;
}
root->next=pre;
return next;
}
鏈表中環(huán)檢測
int isCircle(Node* head){
Node* fast=head;
Node* slow=head;
while (fast != NULL && slow != NULL){
fast = fast->next;
slow = slow->next;
if (fast != NULL){
fast = fast->next;
}
if (slow != NULL && slow == fast){
return 1;
}
}
return 0;
}
兩個有序鏈表合并
LinkedList mergeList(Node* first,Node* second){
if (first ==NULL && second ==NULL){
return NULL;
} else if (first ==NULL){
return second;
} else if (second ==NULL){
return first;
}
Node* p = NULL;
Node* head = NULL;
while (first!=NULL && second!=NULL){
if (first->value <= second->value){
if (head == NULL){
head = first;
p = first;
} else {
p->next = first;
p = p->next;
}
first = first->next;
} else {
if (head == NULL){
head = second;
p = second;
} else {
p->next = second;
p = p->next;
}
second = second->next;
}
}
if (first!=NULL){
p->next = first;
}
if (second!=NULL){
p->next = second;
}
return head;
}
刪除鏈表倒數(shù)第n個結點
LinkedList deleteElementFromTail(Node* head,int i){
if (head==NULL || i < 0){
return NULL;
}
Node* fast = head;
Node* low = head;
Node* pre = NULL;
while (i -1 >0){
if (fast->next != NULL){
fast = fast->next;
} else {
return head;
}
i--;
}
while (fast->next != NULL){
fast = fast->next;
pre = low;
low = low->next;
}
if (low == head){
head = head->next;
free(pre);
} else {
pre->next = pre->next->next;
free(low);
}
return head;
}
求鏈表的中間結點
LinkedList findMiddleOfList(Node* head){
if (head == NULL || head->next == NULL || head->next->next ==NULL){
return head;
}
Node* fast = head;
Node* low = head;
while (fast->next !=NULL){
fast = fast->next->next;
low = low->next;
}
return low;
}
