鏈表

前言

new一個奶黃包：沒關系，這條路我陪你走到底

認識鏈表

單鏈表結構圖

帶頭單循環鏈表結構圖

雙向循環鏈表結構圖

帶頭雙向循環鏈表結構圖

鏈表特點

• 單鏈表在內存中，并不是連續存儲的（邏輯上連續）。

• 不支持隨機訪問

• 插入時只需要改變指針指向

• 沒有容量的概念

• 可以高效的在任意位置插入&&刪除

• 緩存利用率低

鏈表實現(帶頭雙向循環鏈表實現)

鏈表結構體

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

(1) 新建頭節點

LTNode* ListInit()//建立頭節點
{LTNode* phead = buyListNode(-1); //建立一個帶頭節點phead->next = phead;      phead->prev = phead;return phead;
}

(2) 建立新節點

LTNode* buyListNode(LTDataType x)//創建內存初始化數據  
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //if (newnode == NULL){perror("malloc fail");exit(-1);}// 初始化：注意所對的結構來初始化newnode->next = NULL;newnode->prev = NULL;newnode->data = x;return newnode;
}

(3)尾部插入節點

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = buyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

(4)刪除節點

void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;  //記錄上一個節點LTNode* tailmove =tail->prev;  //記錄上一個節點的上一個節點tailmove->next = phead;    phead->prev = tailmove;free(tail);
}

(5)頭部插入節點

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = buyListNode(x); LTNode* first = phead->next;newnode->next = first;first->prev = newnode;first->next = phead;phead->prev = first;
}

(6) 頭刪節點

void LTPopFront(LTNode* phead)
{assert(phead);  //判斷是否有頭節點assert(phead->next != NULL);  //判斷第一個節點是否存在LTNode* tail = phead->next;LTNode* tailmove = tail->next;tailmove->prev = phead;phead->next = tailmove;tailmove->next = phead;phead->prev = tailmove;free(tail);
}

(7) 尋找節點

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){//printf("找到了");return cur;//返回指針}cur=cur->next; //每次都走到下一個節點直到phead}//printf("找不到");return NULL;
}

(8) pos位置插入節點

void LTInsert(LTNode* pos, LTDataType x)//頭插尾插都可以調用這個函數 
{assert(pos);LTNode* newnode = buyListNode(x); //新建一個節點LTNode* prev = pos->prev;   //記錄pos位置的前一個節點newnode->next = pos;   //新節點的下一個節點就是pospos->prev = newnode;   //pos位置節點prve就鏈接后面newnode->prev = prev;prev->next = newnode;
}

(9) 刪除pos位置節點

void LTErase(LTNode* pos)  //刪除節點
{assert(pos);LTNode* prve = pos->prev;LTNode* next = pos->next;prve->next = next;next->prev = prve;free(pos);
}

(10) 打印鏈表

void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur!= phead){printf("-> %d ",cur->data );cur = cur->next;}}

測試用例

void test1()
{LTNode* ptail = ListInit();LTPushBack(ptail, 1);LTPushBack(ptail, 3);LTPushBack(ptail, 2);LTPushBack(ptail, 4);LTPushBack(ptail, 5);LTPopBack(ptail);LTPrint(ptail);
}