【數據結構】單鏈表的建立——頭插法與尾插法。

單鏈表的建立

當我們準備采用單鏈表的形式來實現線性表，那么第一步我們需要考慮到的就是單鏈表的建立，也就是初始化的過程。而由于鏈表是一個動態的結構，它不需要預先分配空間，因此生成鏈表的過程是一個結點“逐個插入”的過程，而結點插入的位置是我們可以選擇的，所以按照結點插入的位置可以將單鏈表的建立方法分為頭插法和尾插法。

①頭插法

該算法的官方描述為∶從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭結點之后。

這里的重點就是：每次生成的新結點都是要與頭結點相連接的，每個新結點都插在了原來第一個節點的前面。通過這種方法建立的鏈表是后來居前的，也就是鏈表是逆序的。因此，當有題目讓我們實現線性表的逆序表示，就應該首先考慮頭插法。

圖示為：

其中，指針H始終指向頭結點，指針s指向新結點。①表示初始化空表②表示申請新結點并賦值③表示插入第一個結點④表示插入第二個結點（④-1和④-2代表了先后順序）。整個圖示過程展現了頭插法的基本原理。

對應的算法為：

②尾插法

該算法的官方描述為∶從一個空表開始，重復讀入數據，生成新結點將讀入數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表尾結點之后。

這里的重點就是：生成的一個新結點是直接插入當前單鏈表的尾端，也就是讓原來最后一個結點指向該新結點。這也是鏈表長度增長的一種最基本的方式。后來居后，生成的鏈表是順序的。

圖示為：

其中指針H始終指向頭結點，指針s指向新結點，指針r始終指向單鏈表的表尾。①表示初始化空表②表示申請新結點并賦值③表示插入第一個結點④表示插入第二個結點（④-1和④-2代表了先后順序）

整個圖示過程展現了尾插法的基本原理。

對應的算法為：

分析完頭插法和尾插法，又到了辨析兩者時間復雜度的經典問題。

頭插法：

每個節點：只需要移動一下它本身和頭指針的指向即可，不需要移動其他的元素，實際也和其他的元素沒有關系，所以單個節點的時間復雜度是O（n）。

整個鏈表：設單鏈表的總長度為n，在一個已有N個元素的單鏈表中插入元素，如果插入位置為x那么需要找到它的前驅才可以插入，最壞時間復雜度為O（n），時間復雜度也為O（n）

尾插法：

每個節點：只需要移動一下它本身和尾指針的指向即可，不需要移動其他的元素，實際也和其他的元素沒有關系，所以單個節點的時間復雜度是O（1）。

整個鏈表：設單鏈表的總長度為n，在一個已有N個元素的單鏈表中插入元素，如果插入位置為x那么需要找到它的前驅才可以插入，最壞時間復雜度為O（n），時間復雜度也為O（n）。

思維導圖：