顺序表和链表

时间复杂度-  那一项在表达式里面权重最大
数据结构-   就是对基本数据(int float .. )的一种组织形式    容器就是数据的存放   {{}} O(1)效率最高
算法和数据结构之间的关系
    数据的不同组织形式会影响算法对数据进行相关操作的效率不同
timeit 平均耗时
    from timeit import Timer
    t  = Timer(‘func()‘,‘相关设置/from __main__ import func1()‘)   要是回调的话就不要参数二了 直接放函数
    t.timeit(1000)

计算机只能存储二进制数据  也就只能运算二进制数据
变量
    就可以表示计算机中的某一块内存空间
    内存空间会有2个默认属性:
        地址  16进制数表示
        大小(可以存怎样的数据量)  整数4字节  64位机8字节

引用  就是(变量)   存储的都是一块内存地址
指向  如果某一个引用/变量存储了某一块内存空间的地址之后,则表示该引用指向了该内存空间

不同的数据占用内存的大小:
    int 4byte
    char 1byte
     float 4
     double 8

顺序表
    集合中存储中的元素师有顺序的,顺序表的结构可以分为2种: 单数据类型/多数据类型
    python中的list tuple 就属于多类型的顺序表
    numpy array 就是单类型

单数据类型顺序表的内存图(内存连续开启)
    元素是连续存的
    顺序表变量的指向 存的 内存空间的首地址

多数据类型顺序表的内存图(内存非连续开启)  元组 列表
    想把数据存储到内存中,必须现在内存中开辟指定大小的内存空间(大小,地址:定位)
    如果一个引用指向了某一块内存空间,则表示该引用存储了该内存空间的地址

顺序表的弊端 -- 顺序表的结构需要预先知道数据的大小来申请连续的存储空间,而在进行扩充时候有需要进行数据的搬迁

单链表  -- 可以更加充分的利用计算机的内存空间,实现灵活的内存动态管理且进行扩充时候不需要进行数据搬迁

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是每一个结点（数据存储单元）里存放下一个结点的信息（即地址）

. is_empty()：链表是否为空

. length()：链表长度

. travel()：遍历整个链表

. add(item)：链表头部添加元素

. append(item)：链表尾部添加元素

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

. remove(item)：删除节点

. search(item)：查找节点是否存在

class Node():  #封装节点
    def __init__(self,item):
        self.item = item
        self.next = None
    def __str__(self):
        return self.item

class Link():  #封装链表
    def __init__(self):
        self._head = Node  #该属性永远指向第一个节点

    def isEmpty(self):
        return self._head == None
    def add(self,item):  #每次都在头部
        # 创建一个新节点对象
        node = Node(item)
        # 将节点插入到链表头部
        node.next = self._head
        self._head = node
    def travel(self): #遍历
        cur = self._head  #第一个节点
        while cur: #最后一个cur就是None

            print(cur.item)
            cur = cur.next

    def length(self):  #长度
        count = 0
        cur = self._head
        while cur:
            count+=1
            cur = cur.next
        return count

    def append(self,item):  #尾部添加
        cur = self._head
        pre = None
        node = Node(item)  # 新node
        # 当链表为空则新节点作为链表的第一个节点
        if self._head is None:
            self._head = node
            return
        # 链表非空对应的插入情况
        while cur:
            pre = cur #该节点前的一个节点
            cur = cur.next
        pre.next = node

    def insert(self,pos,item):
        cur = self._head
        pre = None
        node = Node(item)
        length = self.length()
        if pos > length: #追加
            self.append(item)
            return
        if pos <= 0: #第一项
            self.add(item)
            return
        # 正常处理
        for i in range(pos):
            pre = cur
            cur = cur.next
        pre.next = node
        node.next = cur

    def remove(self,item):
        cur = self._head
        pre = None
        # 如果删除的是第一个
        if  item == self._head:
            self._head = cur.next
            return
        # 正常 中间的
        while cur:
            if cur.item == item:
                pre.next = cur.next
                return
            else:
                pre = cur
                cur = cur.next

    def search(self,item):
        find = False
        cur = self._head
        while cur:
            if cur.item == item:
                find = True
                break
            cur = cur.next
        return find

link = Link()
link.add(10)
link.add(‘aa‘)
link.append(‘bobo‘)
link.append(‘bobo1‘)
link.insert(111,666)
# link.remove(‘aa‘)
link.travel()
print(link.length())
link.search(6669)