鏈表：鏈表是一種非連續(xù)据沈、非順序的存儲(chǔ)結(jié)構(gòu)哟沫，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成锌介，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成嗜诀。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域孔祸。 相比于棧和隊(duì)列隆敢，操作復(fù)雜。由于不必須按順序存儲(chǔ)崔慧，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度拂蝎，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間惶室，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)
**

鏈表圖示.png

python代碼實(shí)現(xiàn)如下：

# coding:utf-8

class Node(object):
    def __init__(self, val):
        self.val=val  #節(jié)點(diǎn)值
        self.next = None #指向下一個(gè)節(jié)點(diǎn)

class SignalLink(object):
    """
    單鏈表：每個(gè)節(jié)點(diǎn)包含連個(gè)域温自，一個(gè)信息域和一個(gè)鏈接域，鏈接域指向下一個(gè)節(jié)點(diǎn)皇钞，最后一個(gè)鏈接域指向空值
    """

    def __init__(self, node=None):
        self._head = node#指定首節(jié)點(diǎn)

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

    def length(self):
        """
        鏈表長(zhǎng)度
        """
        count = 0
        cur = self._head
        while cur:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """
        遍歷鏈表
        """
        cur = self._head
        while cur:
            print(cur.val)
            cur = cur.next

    def add(self, val):
        """
        鏈表頭部添加元素
        """
        node = Node(val)
        node.next = self._head
        self._head = node

    def append(self, val):
        """
        鏈表尾部添加元素
        """
        node = Node(val)
        if self.is_empty():#空
            self._head = node
        else:
            cur = self._head
            while cur.next:#有下一個(gè)元素
                cur = cur.next #遍歷到最后一個(gè)元素
            cur.next = node

    def insert(self, idx, item):
        """
        在指定位置添加元素（在第二個(gè)位置插入悼泌，即索引為1）
        """
        cur = self._head
        index = 0
        if idx <= 0:
            self.add(item)
        elif idx >= (self.length()-1):
            self.append(item)
        else:
            pre = self._head
            index = 0
            while index < (idx-1):#碰到執(zhí)行索引退出循環(huán)
                index += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node


    def delete(self, item):
        """
        刪除節(jié)點(diǎn)
        """
        cur = self._head
        pre = None
        while cur:
            if cur.val == item:
                if cur == self._head:#頭結(jié)點(diǎn)，直接指向下一個(gè)節(jié)點(diǎn)
                    self._head = cur.next
                else:
                    pre.next = cur.next #當(dāng)前節(jié)點(diǎn)上一節(jié)點(diǎn)指向下一節(jié)點(diǎn)
                break
            else:
                pre = cur
                cur = cur.next



    def search(self, item):
        """
        查詢節(jié)點(diǎn)是否存在
        """
        cur = self._head
        while cur:
            if cur.val == item:
                return True
            cur = cur.next
        return False

if __name__ == '__main__':
    sl = SignalLink()
    sl.append(1)
    sl.append(2)
    sl.append(3)
    print(sl.length())
    sl.travel()
    print(sl.search(1))
    print(sl.search(5))
    sl.delete(3)
    sl.travel()
    print(sl.insert(1,100))
    sl.travel()