数据结构之链表python版

链表：链表是一种非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于栈和队列，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)
**

链表图示.png

python代码实现如下：

# coding:utf-8

class Node(object):
    def __init__(self, val):
        self.val=val  #节点值
        self.next = None #指向下一个节点

class SignalLink(object):
    """
    单链表：每个节点包含连个域，一个信息域和一个链接域，链接域指向下一个节点，最后一个链接域指向空值
    """

    def __init__(self, node=None):
        self._head = node#指定首节点

    def is_empty(self):
        """
        判断链表为空
        """
        return self._head==None

    def length(self):
        """
        链表长度
        """
        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:#有下一个元素
                cur = cur.next #遍历到最后一个元素
            cur.next = node

    def insert(self, idx, item):
        """
        在指定位置添加元素（在第二个位置插入，即索引为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):#碰到执行索引退出循环
                index += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node


    def delete(self, item):
        """
        删除节点
        """
        cur = self._head
        pre = None
        while cur:
            if cur.val == item:
                if cur == self._head:#头结点，直接指向下一个节点
                    self._head = cur.next
                else:
                    pre.next = cur.next #当前节点上一节点指向下一节点
                break
            else:
                pre = cur
                cur = cur.next



    def search(self, item):
        """
        查询节点是否存在
        """
        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()