2．2線性表

　　線性表的邏輯結構是由n個數據元素組成的一個有限序列。線性表中所包含元素的個數叫線性表的長度．它是可變的．可同線性表中增加或刪除元素。線性表包括順序表、鏈表、散列表和串等。

1、線性鏈表
　　線性鏈表也稱為單鏈表，其每個一節點中只包含一個指針域。對鏈表進行插人、刪除運算時只需改變節點中指針域的值。
　　（1） 在指針一P后插人指針9的關鍵運算步驟：        
q ↑. link：＝P↑．link：
        p ↑. link：＝q；
　　（２）刪除指針P后繼節點q的關鍵運算步驟：
        q：＝p↑ . link；
        p↑. link：＝q↑．link；
　　（3）在第一個節點（或稱頭節點）前插人一個指針P的關鍵運算步驟：
        p↑. link：＝head；
          head：二P；
　　（４）刪除表中頭節點的關鍵運算步驟：
        head：＝head↑ . link：

 2、雙鏈表
　　在雙鏈表中，每個節點中設置有兩個指針域，分別用以指向其前驅節點和后繼節點。rlink指向節點的后繼，llink指向節點的前驅，這樣的結構方便向后和向前查找。
　　（l）若要在雙鏈表中刪除指針P所指的節點時，只需修改其前驅的rlink字段和后繼的Mink字段，步驟如下：
        p↑ . llink↑. rlink：＝p↑. rlink；
        P↑T．rlink↑. llink：＝P↑．llink；
　　 (2)如果要在指針P后面插人指針q所指的新節點，只需修改P指針所指節點的rlink字段和原來后繼均Ilink字段，并重新設置q所指節點的Mink和rlink值，步驟如下：
        q ↑. Mink：＝P：
        q↑．rlink：＝P↑．rlink;
        P↑．rlink r. Rink：＝q；
        p↑．rlink：＝q;
 
3、可利用空間表
 
　　可利用空間表的作用是管理可用于鏈表插人和刪除的節點，當鏈表插人需要一個新節點時，就從可利用空間表中刪除第一個節點，用這個節點去做鏈表插人；當從鏈表中刪除一個節點時，就把這個節點插人到可利用空間表的第一個節點前面。