線性表的鏈式存儲結構（十）

        我們之前學習了順序存儲結構線性表，雖然它很強大。但是存在一個不算是缺點的缺點：那便是在插入和刪除時。需要移動大量的元素。那么該如何解決這個問題呢？我們直接會想到的是在數據元素之間空出位置，那么在后面的插入時便會很方便。那么此時便會出現一個問題：究竟留出多少空間合適呢？有一個極端是我們需要插入的是 n 個元素。換而言之，這個空間需要預留無窮大，那么這個肯定是不現實的。

        此時便出現了我們本節要講的內容：鏈式存儲。我們來看看鏈式存儲的定義：為了表示每個數據元素與直接后繼元素之間的邏輯關系；數據元素除了存儲本身的信息外，還需要存儲直接后繼的信息。如下

        我們來看看鏈式存儲邏輯結構，它是基于鏈式存儲結構的線性表，每個結點都包含數據域和指針域。數據域是指粗出數據元素本身；而指針域是指存儲相鄰結點的地址。關系如下所示

        順序表指的是基于順序存儲結構的線性表，鏈表指的是基于鏈式存儲機構的線性表。鏈表分為三種：a> 單鏈表，即沒和結點只包含直接后繼的地址信息；b> 循環鏈表，即單鏈表中的最后一個結點的直接后繼為第一個結點；c> 雙向鏈表，即單鏈表中的結點包含治腳氣前驅和后繼的地址信息。

        下來我們來看看鏈表中的基本概念：A、頭結點。鏈表中的輔助結點，包含指向第一個數據元素的指針；B、數據結點。鏈表中代表數據元素的結點，表現形式為：（數據元素，地址）；C、尾結點。鏈表中的最后一個數據結點，包含的地址信息為空。那么單鏈表中的結點是怎樣進行定義的呢？如下

        我們來看看單鏈表中的內部結構，如下

        頭結點在單鏈表中的意義是：輔助數據元素的定位，方便插入和刪除操作；因此，頭結點不存在存儲實際的實際數據元素。那么在目標位置處是如何插入數據元素呢？1、從頭結點開始，通過 current 指針定位到目標位置；2、從堆空間申請新的 Node 結點；3、執行操作：node->value = e; node->next = current->next; current->next = node; 同理，在目標位置處刪除數據元素：1、從頭結點開始，通過 current 指針定位到目標位置；2、使用 toDel 指針指向需要刪除的結點；3、執行操作：toDel = current->next; current->next = toDel->next; delete toDel;

        通過今天對線性表的鏈式存儲結構的學習，總結如下：1、鏈表中的數據元素在物理內存中午相鄰關系；2、鏈表中的結點都包含數據域和指針域；3、頭結點用于輔助數據元素的定位，方便插入和刪除操作；4、插入和刪除操作需要保證鏈表的完整性。

        今天七夕情人節，祝大家七夕快樂！