單鏈接的整表創(chuàng)建

 經(jīng)常寫swift寫的沒有寫分號的習(xí)慣了~如果有看到的人見諒哈

• 頭插法
  *L = (LinkList)malloc(sizeof(Node)) (*L)->next = NULL for(int i = 0;i<n;i++){ p = (LinkList)malloc(sizeof(Node)) p->next = rand()%100 +1 p ->next = (*L)->next; (*L)->next = p }
• 尾插法(外部一個指針記錄當(dāng)前最后一個元素的位置。不斷更新最后一個元素)
  r = *L for(int i =0 ;i<n;i++){ p = (Node*)malloc(sizeof(Node)) p->data = 1 p ->next = r r = p } r->next = NULL

單鏈表的整表刪除

• 聲明 p,q,
• 將第一個節(jié)點賦值給p
• 循環(huán) q記錄p—>next,釋放p,p =q
  最后使頭節(jié)點的指針域為NULL

靜態(tài)鏈表

在刪除和刪除操作的時候只需要修改游標，不需要移動元素，從而改進了順序存儲結(jié)構(gòu)中插入和刪除需要移動大量元素的缺點

缺點：

• 沒有解決連續(xù)分配帶來的表長難以確定的問題
• 失去了順序存儲結(jié)構(gòu) 隨機存取的特性

靜態(tài)鏈表是為了 沒有指針的高級語言設(shè)計的一種實現(xiàn)單鏈接能力的方法

循環(huán)鏈表

單鏈表中終端結(jié)點的指針端由空指針改為指向頭結(jié)點，就使整個單鏈表形成了一個環(huán)。這種頭尾相連的結(jié)構(gòu)稱為循環(huán)鏈表。

兩個循環(huán)鏈表 合并成一個循環(huán)鏈表

//記錄rearA的next的指向
p = rearA->next;

//rearA的末尾指向rearB的第一個結(jié)點。不是頭結(jié)點

rearA->next = rearB->next->next;

q = rearB->next;

rearB->next = p ;

free(q);

雙向鏈表

雙向鏈表 是在單鏈表的每個結(jié)點中，再設(shè)置一個指向其前驅(qū)結(jié)點的指針域

單向鏈表可以存在循環(huán)鏈表。那么雙向鏈表也可以存在循環(huán)鏈表。

雙向鏈表的插入操作

• 改變插入元素的前驅(qū)和后繼
• 改變后繼的前驅(qū)
• 改變前驅(qū)的后繼

s->prefix = p;

s->next = p->next;

p->next->prefix = s;

p->next = s

雙向循環(huán)鏈表的刪除操作

• p->prefix->next = p->next
• p->next->prefix = p->prefix

總結(jié)

雙向鏈表對于單鏈表而言要復(fù)雜，因為多了prefix指針，對于插入和刪除時候要格外小心。