摘要：線性表是最基本的數據結構之一，在實際程序中應用非常廣泛，它還經常被用作更復雜的數據結構的實現基礎。鏈表之單鏈表線性表的定義，它是一些元素的序列，維持著元素之間的一種線性關系。

線性表學習筆記，python語言描述-2019-1-14

在程序中，經常需要將一組（通常是同為某個類型的）數據元素作為整體管理和使用，需要創建這種元素組，用變量記錄它們，傳進傳出函數等。一組數據中包含的元素個數可能發生變化（可以增加或刪除元素）。

對于這種需求，最簡單的解決方案便是將這樣一組元素看成一個序列，用元素在序列里的位置和順序，表示實際應用中的某種有意義的信息，或者表示數據之間的某種關系。

這樣的一組序列元素的組織形式，我們可以將其抽象為線性表。一個線性表是某類元素的一個集合，還記錄著元素之間的一種順序關系。線性表是最基本的數據結構之一，在實際程序中應用非常廣泛，它還經常被用作更復雜的數據結構的實現基礎。

根據線性表的實際存儲方式，分為兩種實現模型：

順序表，將元素順序地存放在一塊連續的存儲區里，元素間的順序關系由它們的存儲順序自然表示。
鏈表，將元素存放在通過鏈接構造起來的一系列存儲塊中。

2.1、順序表的基本形式

圖a表示的是順序表的基本形式，數據元素本身連續存儲，每個元素所占的存儲單元大小固定相同，元素的下標是其邏輯地址，而元素存儲的物理地址（實際內存地址）可以通過存儲區的起始地址Loc (e0)加上邏輯地址（第i個元素）與存儲單元大小（c）的乘積計算而得，即：

Loc(ei) = Loc(e0) + c*i

故，訪問指定元素時無需從頭遍歷，通過計算便可獲得對應地址，其時間復雜度為O(1)。

如果元素的大小不統一，則須采用圖b的元素外置的形式，將實際數據元素另行存儲，而順序表中各單元位置保存對應元素的地址信息（即鏈接）。由于每個鏈接所需的存儲量相同，通過上述公式，可以計算出元素鏈接的存儲位置，而后順著鏈接找到實際存儲的數據元素。注意，圖b中的c不再是數據元素的大小，而是存儲一個鏈接地址所需的存儲量，這個量通常很小。

圖b這樣的順序表也被稱為對實際數據的索引，這是最簡單的索引結構。

2.2、順序表的基本實現
順序表的基本實現方式：表中元素順序存放在一片足夠大的連續存儲區里，首元素存入存儲區的開始位置，其余元素依次順序存放。元素之間的邏輯順序關系通過元素在存儲區的物理地址表示。

順序表最常見的一種基本實現方式是一個表里保存的元素類型相同，因此存儲每個表元素所需的存儲量相同，可以在表里等距安排相同大小的存儲位置。如下圖，一個順序表，存放的元素是整型的數據類型，整型在32位的操作系統中，一個整型數字占用內存的空間大小是4Byte,因此，內存中連續存放幾個整型數字，每個存放元素的空間的地址值之間是等距。其中Li變量指向的通常是順序表的表頭元素的地址值，也就是0x23。

線性表的定義，它是一些元素的序列，維持著元素之間的一種線性關系。實現線性表的基本需要是：

能夠找到表中的首元素

從表中的任一元素出發，都能找到它的下一個元素

實現它除了連續存儲的順序表之外，鏈表也能做到。

鏈表是用鏈接關系顯示表示元素之間的順序關系，基本實現方式如下:

把表中的元素分別存儲在一批獨立的存儲塊里

保證從組成表結構中的任一結點可找到與其相關的下一個結點

在前一結點用鏈接的方式顯示地記錄與下一結點的關聯。

單鏈表

單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式，它的每個節點包含兩個域，一個信息域（元素域）和一個鏈接域。這個鏈接指向鏈表中的下一個節點，而最后一個節點的鏈接域則指向一個空值。

表元素域elem用來存放具體的數據。

鏈接域next用來存放下一個節點的位置（python中的標識）

變量p指向鏈表的頭節點（首節點）的位置，從p出發能找到表中的任意節點。

而表示一條鏈表的結束，只需要將最后一個結點的鏈接域設置為None。
節點的實現

一個鏈表的最基本組成是一個結點，一個結點的實現如下：

class SingleNode(object):
    """單鏈表的結點"""
    def __init__(self,item):
        # _item存放數據元素
        self.item = item
        # _next是下一個節點的標識
        self.next = None

單鏈表的操作

is_empty() 鏈表是否為空

length() 鏈表長度

travel() 遍歷整個鏈表

add(item) 鏈表頭部添加元素

append(item) 鏈表尾部添加元素

insert(pos, item) 指定位置添加元素

remove(item) 刪除節點

search(item) 查找節點是否存在

python中單鏈表的實現

class SingleLinkList(object):
    """單鏈表"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        """判斷鏈表是否為空"""
        return self._head == None

    def length(self):
        """鏈表長度"""
        # cur初始時指向頭節點
        cur = self._head
        count = 0
        # 尾節點指向None，當未到達尾部時
        while cur != None:
            count += 1
            # 將cur后移一個節點
            cur = cur.next
        return count

    def travel(self):
        """遍歷鏈表"""
        cur = self._head
        while cur != None:
            print cur.item,
            cur = cur.next
        print ""