一、單鏈表基礎概念講解

上一張我們分析了順序表，可以看出順序表的好處有以下幾點：
1、順序表在查找某個元素時比較簡單；順序表可以直接通過下標的方式就可以訪問到了這個元素
2、順序表在插入到末尾，或者刪除末尾元素也是比較簡單的；這個時候也可以直接通過下標的方式直接訪問到這個元素；
但是順序表野有自己的缺點，如下：
1、順序表在插入到中間某個位置時，是比較困難的；因為后面的元素需要挨個的移動；
2、同理，順序表在刪除中間某個位置的元素是，也是比較困難的；后面的元素也是要挨個移動到前面；
那么問題的關鍵就在這個地方了：
1、如果我們不是頻繁的往中間去插元素或者去刪除元素；我們知識在最后插入元素；或者主要的操作是遍歷和查找元素的話，我們用順序表，無疑是最快的；
那么，如果，那么我們就引入了鏈表的操作；
所謂的鏈表，就是每一個節(jié)點都是在存儲上不連續(xù)的；都是可以通過上一個節(jié)點去訪問到的；那么這其中有一個問題就是；如果在鏈表的最后面插入時候，就會存在需要遍歷整個鏈表才能訪問到最后一個元素的問題；所以我們?yōu)榱私鉀Q這樣的問題；我們直接定義出尾指針，來記錄出最后一個節(jié)點；
綜上：
我們可以看出鏈表的有點在于插入和刪除；缺點是在查找某個元素時候，比較麻煩，需要遍歷到這個元素才能把這個位置的內容取出；

二、單鏈表基本操作

1、單鏈表準備數據

什么是單鏈表；我們用圖來表示以下：

image.png

我們的每個元素都是這樣的；有自己的數據域，和一個指向下一個節(jié)點的指針閾；
所以我們這樣來操作：

//結點
typedef struct Node {
    int data;
    Node * next;
}Node;
//創(chuàng)建列表
typedef struct ListMine {
    Node *head;
    Node *tail;
    int  length;
}ListMine;

2、單鏈表創(chuàng)建和析構

//創(chuàng)建空鏈表
void createList(ListMine* SL)
{
    SL->head = SL->tail = NULL;
    SL->length = 0;
}
void distroyList(ListMine* SL)
{
    Node* cur = SL->head;
    while (cur != NULL)
    {
        Node* tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    free(SL);
}

3、單鏈表插入和刪除

圖示：
1、插入操作：

image.png

2、刪除操作：

image.png

//插入結點
bool insert(ListMine*SL, int i, int data)
{
    Node *p = SL->head; //0
    if (i > SL->length)
    {
        cout << "insert location error" << endl;
        return false;
    }
    Node *n = (Node*)calloc(1,sizeof(Node)); //分配新內存；
    n->data = data;
    n->next = NULL;
    if (i == 0)
    {
        SL->head = SL->tail = n;
        SL->length += 1;
        return true;
    }
    //之所以單獨抽出來，是因為這樣可以增快最后插入的時間
    //這就是為了告訴自己，尾指針的作用
    //后面如果有棧和隊列的操作的時候，就會明白這個的重要性了
    if (i == SL->length)
    {
        SL->tail->next = n;
        SL->tail = n;
        SL->length ++;
        return true;
    }
    //后面這就是重要的一般插入的問題了
    int j = 0;
    while (j < i - 1 && p->next)
    {
        p = p->next;
        ++j;
    }
    n->next = p->next;
    p->next = n;
    SL->length++;
    return true;
}
//刪除結點
bool del(ListMine*SL, int i)
{
    Node *p = SL->head; //0
    int j = 0;//0
    while (j < i-1 && p->next)
    {
        p = p->next;
        ++j;
    }
    Node *willfree = p->next;
    p->next = p->next->next;
    delete willfree;  //釋放內存
    return true;
}

3、main函數驗證

///主函數///
int main() {
    ListMine* SL = (ListMine*)calloc(1, sizeof(ListMine));
    createList(SL);
    int i = 0;
    for (; i < 10; i++)
    {
        insert(SL, i, i);

    }
    del(SL, 7);
    Node*cur = SL->head;
    while (cur!= NULL)
    {
        cout << "the data is " << cur->data << endl;
        cur = cur->next;
    }
    distroyList(SL);
}

運行結果如下：

image.png