python数据结构-基本数据类型

参考来源 https://ceshiren.com/t/topic/27698

Python3标准数据类型

1.分类

1.基本数据类型

  • Number数字:int整数、浮点数float
  • string字符串
  • bool布尔类型

2.复合数据类型

  • List 列表
  • Tuple 元组
  • Dictionary 字典
  • Set 集合

3.空类型

  • None

2.不同特性分类:

  • 不可变数据(4个):Number、bool、string、tuple
  • 可变数据(3个):list 、dictionary、 set
  • 元素唯一:set
  • 有序数据sequence: string、tuple 、list

3.数据类型转换

来源

3.1自动转换/隐式类型转换

程序在执行过程中自动完成,将数据精度转换为数据精度的类型。

n = 10 + 3.14
print(n, type(n))
# 输出:13.14 <class 'float'>
n = False + 1
print(n)
print(type(n))
#输出: 1
#      <class 'int'>

3.2强制转换/显式类型转换

需要在代码中使用类型函数来转换。
转换函数如下:

  • int(x):将 x 转换为整数。如果 x 是一个字符串,那么它必须是一个表示整数的字符串,否则将会抛出异常。

  • float(x):将 x 转换为浮点数。如果 x 是一个字符串,那么它必须是一个表示浮点数的字符串,否则将会抛出异常。

  • complex(x):将 x 转换为复数。如果 x 是一个字符串,那么它必须是一个表示复数的字符串,否则将会抛出异常。

  • bool(x):将 x 转换为布尔值。如果 x 是一个空对象0空字符串空列表空元组空字典 或者 False ,那么将返回 False ,否则将返回 True

  • str(x):将 x 转换为字符串。如果 x 是一个对象,那么将会调用该对象的 str() 方法,将其转换为字符串。

  • chr(x): 将一个整数转换为一个字符。虽然结果是一个字符,但其本质依然是一个字符串类型。

注意:如果在强制类型转换时,传递的转换数据不合法导致无法转换,那么将会抛出异常。


4.公用方法

针对有序数据sequence: string、tuple 、list

4.1索引
4.2切片操作
切片操作,索引超出列表长度也不会报错,只会获得空列表

list_num = [8,3,1,0,2,5,4,2]
print(list_num[9:])
输出结果是: [ ]

应用:在一个长度为n的列表里的所有数字都在0到n-1的范围内。 列表中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出列表中第一个重复的数字。

def find_firstSameNum(list_num:list):
    for i  in range(len(list_num)-1):
        if list_num[i] in list_num[i+1:]:
            return list_num[i]

4.3拼接
+
*
4.通用方法

  • len(sequence)
  • max(sequence)
  • min(sequence)
  • enumerate(sequence)
# 求最大最小值的两种方法
方式1:
max_value=max(num_list)
min_value=min(num_list)
方式2:
order_list=sorted(num_list)
max_value=order_list[-1]
min_value=order_list[0]

5.高级用法

5.1.map高阶函数
针对可迭代对象(列表、元组、字典)每个元素进行操作——相当于for循环对每个元素做了转换操作
map(int,list)
map函数说明


一、字符串

所有字符串操作,都不会影响原字符串本身,每次操作后都会得到一个新字符串。
A.统计查找类
1.长度
len(str) 字符串长度
2. 统计个数
count(str,start,end) 返回str在string里面出现的次数 [start,end) 语法string.count(str,start,end)
3.查找索引
(1)index(sub,start,end) 检测 sub 是否包含在 string 中,如果 start 和 end 指定范围,则检查是否包含在指定范围内,如果是返回开始的索引值,否则抛出一个异常 ValueError: substring not found
(2)rindex(sub,start,end) 作用同index(),查子串从右侧查,如果是返回开始的索引值,否则抛出一个异常 (3)find(sub,start,end) 如果是返回开始的索引值,否则返回-1
(4)rfind(sub,start,end) 同find() 从右侧查
4.替换replace(old,new,max) 把 string 中的 old 替换成 new,如果 max 指定,则替换不超过 max 次
B.字符串去除空白
1.去除左右两侧指定’字符’ strip(chars) 无参数去除两边空格
2.lstrip(chars) 去除左侧指定字符
3.rstrip(chars) 去除右侧指定字符
C.字符串分割
1.以sep分割maxsplit次 split(sep,maxsplit) sep是分隔符,结果是列表
2.以换行符分割 splitlines()使用换行符\n分割
print("a\nb\nc".splitlines())# ['a', 'b', 'c']
D.字符串连接
1.居中,总长度width,不足部分fillchar填充 center(width,fillchar) 返回一个原字符串居中
2.左对齐 ljust(width,fillchar)
3.右对齐rjust(width,fillchar)
E.字符串对齐
1.居中,总长度width,不足部分fillchar填充 center(width,fillchar) 返回一个原字符串居中
2.左对齐 ljust(width,fillchar)
3.右对齐rjust(width,fillchar)
F.字符串判断类
1.以xx开头startwith(prefix,start,end) 检查字符串是否以prefix开头,是返回true,否则返回false
2.以xx结尾endwith(suffix,start,end) 检查字符串是否以suffix结尾,是返回true,否则返回false
3.全是字母 isalpha()
4.全是数字 isdigit()
5.全是字母、数字 isalnum()
6.只包含空格 isspace()
7.有字母且全是大写 isupper()
8.有字母且全是小写 islower()
G.字符串转换
1.字符串首字符大写,其他转小写 caplitalize()
2.每个单词首字母大写,其他转小写 title() 标题化
3.全部字母转大写 upper()
4.全部字母转小写 lower()

H.编码解码类
字符集:ASCII字符集、GB2312字符集、BIG5字符集、 GB18030字符集、Unicode字符集等
1.编码encode(encoding) 使用encoding指定的字符集,对string进行编码,转换为二进制字符串
print(“abc123”.encode(“gbk”))# b’abc123’
print(“你好”.encode(“gbk”))# b’\xc4\xe3\xba\xc3’
print(“abc123”.encode(“utf-8”))# b’abc123’
print(“你好”.encode(“u8”))# b’\xe4\xbd\xa0\xe5\xa5\xbd’
2.解码decode(encoding)使用encoding指定的字符集,对string(二进制字符串)进行编码,转换为字符串对象
s1 = b’\xc4\xe3\xba\xc3’
s2 = b’\xe4\xbd\xa0\xe5\xa5\xbd’
print(s1.decode(“gbk”))# 你好 --print(“你好”.encode(“gbk”))# b’\xc4\xe3\xba\xc3’
print(s2.decode(“utf-8”))# 你好
print(s1.decode(“gbk”))# 你好
print(s2.decode(“u8”))# 你好 --print(“你好”.encode(“u8”))# b’\xe4\xbd\xa0\xe5\xa5\xbd’


二、列表

特点:有序 可变 异构(可存储不同数据)
构造方法:list()

1.增加元素

  • append(value) 列表后追加元素
  • extend(iterable) 将一个可迭代对象元素依次加到列表最后
  • insert(index,value) 插入指定位置,原有元素后移。若超过下标,则插入到列表最后。

2.删除操作

  • del list[index] 删除指定位置元素,索引超出范围报错
  • remove(value) 删除指定元素(第一个匹配的),索引超出范围报错
  • pop(index) 删除指定下标元素(默认删除最后一个),索引超出范围报错
  • clear()清空列表

3.查找

  • count(value) 统计value出现次数
  • index(value,start,end) 查找value第一次出现的下标位置,不存在报错

4.排序

  • sort(key,reverse) 默认升序,reverse=True逆序,key指定排序规则 list.sort() 针对原列表进行操作
  • sorted(iterable,reverse) 针对可迭代对象进行排序(不止列表) sorted(iterable,reverse) 返回一个新列表
  • reverse
    反向列表元素,把列表元素只做简单的前后调换顺序(不是从大到小或者从小到大)
    默认是false
    list.reverse()

例子

list1 = [1,2,4,3]
list2 = sorted(list1) # list1顺序不变,list2是排序的
operation = [[0, 2], [1, 5], [0, 9], [2, 15]]
result = sorted(operation,key = lambda x:x[1],reverse=True) 
#key以lamda引出排序key,x是列表operation 元素,x[1]是元素下的第二个子元素,以x[1]排序

5.列表用途

  • 存储一组相关的数据:列表是一种有序的数据结构,可以用于存储一组相关的数据,如学生的成绩、员工的信息、商品的价格等。通过将相关的数据放入列表中,可以方便地进行统一的管理和处理。
  • 数据的容器:列表提供了便捷的操作方法,可以进行遍历、搜索、插入和删除等操作。通过索引,可以访问列表中的特定元素;通过遍历,可以逐个处理列表中的元素;通过方法,可以在列表中插入新元素、删除指定元素等。
  • 算法和数据结构中的应用:列表是一种重要的数据结构,广泛应用于算法和数据结构的实现中。例如,列表可以用于实现栈(Stack)、队列(Queue)、链表(LinkedList)等数据结构,还可以用于排序算法、搜索算法等的实现。

三、元组

特点:有序 不可变 异构(可存储不同数据)
构造方法:tuple(x) ,参数是可迭代对象(列表、元组、字符串)
元组定义:

  • 空元组=()
  • 只有一个元素的元组=(x,)

变量赋多个值得到的也是元组——python组包操作

t = 1,"hello"
print(t)# (1,"hello")

列表和元组区别
1.相同点
• 都是有序,可迭代数据结构
• 元组和列表都是异构的,可存放不同类型数据
2.不同点
• 元组不可变,不可增删改
• 列表可变
• 内存占用:由于元组与列表内部的实现机制不同,在相同元素和个数的情况下,元组占用内存空间更小。

四、字典

python3.7之后是有序的,可变,异构,key唯一且不可变
(使用旧版本的Python,可以考虑使用collections.OrderedDict来实现有序字典的功能)
字典定义 :{} key-value形式
构造方法:

d1 = dict(one=1, two=2, three=3) # {'one': 1, 'two': 2, 'three': 3}---给键赋值
d2 = dict([('two', 2), ('one', 1), ('three', 3)]) # {'two': 2, 'one': 1, 'three': 3}--键值对组成元组-列表数据
d3 = dict((('two', 2), ('one', 1), ('three', 3))) # {'two': 2, 'one': 1, 'three': 3}---键值对组成元组-元组数据
d7 = dict({'one': 1, 'three': 3}, two=2) # {'one': 1, 'three': 3, 'two': 2}--多种形式复合使用

A.字典获取类操作
1.获取字典值
(1)dict(key) 使用key获取对应值,key不存在会报错
(2)get(key, default) key不存在会给个默认值,不会报错

stu = {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing'}
print(stu.get("name"))# Tom
print(stu.get("hobby"))# None
print(stu.get("hobby","无数据"))# 无数据
print(stu["hobby"])# KeyError: 'hobby'

2.获取所有键 keys()
用来获取字典中所有的 key, 保存到一个列表中,并以 dict_keys 类型返回;

stu = {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing'}
ks = stu.keys()
print(ks)# dict_keys(['name', 'age', 'gender', 'address'])
print(type(ks))# <class 'dict_keys'>

for k in ks:
    print(stu[k])
"""
Tom
23
male
BeiJing
"""

3.获取所有值 values()
用来获取字典中所有的value, 保存到一个列表 中,并以 dict_values 类型返回;
4.获取所有条目 items()
用来获取字典中所有的键值对,每一个元素键值对都以一个元组保存 ,将所有元素元组保存到一个列表中,并以 dict_items 类型返回;

stu = {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing'}
ks = stu.items()
print(ks)# dict_items([('name', 'Tom'), ('age', 23), ('gender', 'male'), ('address', 'BeiJing')])

for k in ks:
    print(k)
"""
('name', 'Tom')
('age', 23)
('gender', 'male')
('address', 'BeiJing')
"""
for k in ks:
    print(k[0])
"""
name
age
gender
address
"""

B.字典元素添加与修改
1.dict(key)=valueb根据key更新值
当给一个key赋值时,如果key在当前字典中不存在,则是添加数据;
如果key存在,则对当前key所对应的值进行修改更新
2.setdefault(key,default) 给一个不存在的key添加一个默认值并将该键值对保存到字典中。
在一些场景下,字典的key存在,但是该key却没有对应的值,此时,就可以使用该方法,为当前的key添加一个默认值。比如服务端要保存客户端发起请求时携带的请求头中的信息。

stu = {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing'}
stu.setdefault("hobby1")# {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing', 'hobby1': None}
print(stu)
stu.setdefault("hobby2", "无")# {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing', 'hobby1': None, 'hobby2': '无'}
print(stu)
stu.setdefault("name","newname")# {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing', 'hobby1': None, 'hobby2': '无'}
print(stu)

3.fromkeys(keys,val) 用于创建一个新字典,以序列 keys 中元素做字典的键,value 为字典所有键对应的初始值,默认为None 。
该方法是一个静态方法,需要使用字典类型名 dict 调用。 该方法如果给定 keys 参数,则所有的key对应值都为默认值 None ,如果给定 val值,则所有key对应的值为 val。

ks = ("name", "age", "gender")
s1 = dict.fromkeys(ks)# {'name': None, 'age': None, 'gender': None} --值的默认是None
print(s1)
s2 = dict.fromkeys(ks,"无")# {'name': '无', 'age': '无', 'gender': '无'} --每个的值都是val
print(s2)
s3 = dict.fromkeys(ks,('tome','18','mela'))# {'name': ('tome', '18', 'mela'), 'age': ('tome', '18', 'mela'), 'gender': ('tome', '18', 'mela')} --每个的值都是val
print(s3)

4.update(d/iterable) 使用参数中的数据更新当前字典。
该方法的参数可以接收一个字典(大多数的使用方式),也可以接收一个可迭代对象(列表、元组),如果参数数据中的key在当前字典中存在,则使用新值更新字典中的键值对,如果参数数据中的key在当前字内中不存在,则将键值对添加到当前字典中。

# 更新目标数据是一个字典
stu = {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing'}
newStu = {"name":"Jack","hobby":"eat"}
stu.update(newStu)# {'name': 'Jack', 'age': 23, 'gender': 'male', 'address': 'BeiJing', 'hobby': 'eat'}
print(stu)
# 更新目标数据是一个可迭代对象
stu = {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing'}
newStu = (("name","Rose"),["hobby","play"])
stu.update(newStu)
print(stu)

C.字典元素的删除
1.del 通过key删除元素

stu = {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing'}
print(stu)
# 删除元素
del stu['age']
print(stu)

2.popitem() 用来获取并删除字典中的最后一个键值对,返回一个元组,如果字典为空时,则抛出一个错误;

stu = {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing'}
v = stu.popitem()
print(v) # ('address', 'BeiJing')
print(stu)# {'name': 'Tom', 'age': 23, 'gender': 'male'}

3.pop(key) 用于获取并删除字典中指定key对应的键值对。如果指定的key不存在,则抛出错误;

stu = {'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'BeiJing'}
v = stu.pop("name")# Tom
print(v) # Tom
print(stu) # {'age': 23, 'gender': 'male', 'address': 'BeiJing'}
v1 = stu.pop('hobby') # KeyError: 'hobby'

4.clear() 清空字典中所有的键值对元素;

字典的应用场景

  • 字典适用于存储具有相关性的数据,如用户信息、学生成绩等。每个键值对表示一个独立的数据项,通过键来关联对应的值。
  • 字典提供了快速查找和访问数据的能力,通过键可以直接定位对应的值,而不需要遍历整个字典。这使得字典在需要根据特定键快速获取对应值的场景下非常有用。
  • 字典作为数据的容器,提供了丰富的操作方法,可以方便地进行遍历、搜索、插入和删除操作。可以通过循环遍历字典的键或值,通过键进行搜索和更新数据,通过键值对的添加和删除来动态修改字典的内容。这种灵活性使得字典成为处理各种数据结构的重要工具。

五、集合

无序 不重复 异构
什么是集合

  • 集合是一种数据类型,用于存储多个元素,并确保元素的唯一性。
  • 集合中的元素是无序的,不可通过索引或切片进行访问。
  • 集合的主要特点是元素不重复,相同的元素在集合中只会出现一次。
  • 我们可以使用大括号 {} 或 set() 函数来定义和创建集合。
  • 集合提供了各种集合运算,如并集(两个集合中的所有元素)、交集(两个集合中共有的元素)、差集(第一个集合中存在而第二个集合中不存在的元素)等操作。

集合的创建

  • 不能使用 {} 创建一个空集合,因为此种方式创建的类型为字典。
    • 使用{val,val,val…}创建集合;
    • 使用set(iterable)创建集合;
    • 使用集合推导式创建集合;
# 不能使用花括号 {} 来定义一个空集合
s1 = set()
s2 = {}
print(type(s1)) # <class 'set'>
print(type(s2)) # <class 'dict'>

# 使用花括号 {},在内部添加元素,用逗号 , 分隔
my_set = {1, 2, 3, 4, '5'}
print(my_set) # {1, 2, 3, 4, '5'} --顺序为创建的顺序
print(type(my_set)) # <class 'set'>

A.添加操作
1.add(ele) 向集合最后添加一个元素,如果元素已存在则原集合保持不变;
2.update(interable) 更新集合
在最后添加来自 interable中的所有元素,interable是一个可迭代对象,如果数据在集合中存在则不更新。注意:集合是无序的,添加元素的顺序貌似有点规律,但是这个规律不重要;

s = {1, 2, 3}
s.update((4,5,6))
print(s)# {1, 2, 3, 4, 5, 6} --元组
s.update([5,6,7])
print(s)# {1, 2, 3, 4, 5, 6, 7} --列表
s.update({6,7,8,9,10,11,'A'})
print(s)# {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 'A'} --集合
s.update("abc")
print(s)# {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 'b', 'a', 'A', 'c'} --字符串

B.删除操作
1.pop() 从集合中移除并返回任意一个元素,如果集合为空,则抛出错误;
2.remove(elem) 从集合中移除指定元素 elem,返回None。 如果 elem 不存在于集合中则抛出错误。
3.discard(elem) 如果元素 elem 存在于集合中则将其移除,返回None,如果elem不存在,则什么也不做;
4.clear() 清空集合;

在一个长度为n的列表里的所有数字都在0到n-1的范围内。 列表中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出列表中第一个重复的数字。
def find_duplicate(nums):

def find_duplicate(nums):
    """
    在一个长度为n的列表里找出第一个重复的数字
    :param nums: 列表
    :return: 第一个重复的数字,如果没有重复数字则返回-1
    """
    if not nums:
        return -1
    
    n = len(nums)
    for i in range(n):
        while nums[i] != i:
            if nums[i] == nums[nums[i]]:
                return nums[i]
            # 交换nums[i]和nums[nums[i]]
            temp = nums[i]
            nums[i] = nums[temp]
            nums[temp] = temp
    
    return -1

补充:
1.index()
list.index(value),返回元素值(第一个)在列表中索引

def sou(s,w):
    words_list = s.split()
    for word in words_list:
        if word.startswith(w):
            return  words_list.index(word)+1

题目来自

老师代码-回溯

"""
    check a single-linked list whether a palindrome
"""

import sys
# 引用当前文件夹下的single_linked_list
sys.path.append('singly_linked_list')
from singly_linked_list import SinglyLinkedList

def reverse(head):
    reverse_head = None
    while head:
        next = head._next
        head._next = reverse_head
        reverse_head = head
        head = next

    return reverse_head

def is_palindrome(l):
    l.print_all()
    slow = l._head
    fast = l._head
    position = 0
    while fast and fast._next:
        slow = slow._next
        fast = fast._next._next
        position += 1

    reverse_node = reverse(slow)
    head_node = l._head
    is_palin = True
    while (head_node and reverse_node):
        if (head_node.data == reverse_node.data):
            head_node = head_node._next
            reverse_node = reverse_node._next
        else:
            is_palin = False
            break

    return is_palin

if __name__ == '__main__':
    # the result should be False, True, True, True, True
    test_str_arr = ['ab', 'aa', 'aba', 'abba', 'abcba']
    for str in test_str_arr:
        l = SinglyLinkedList()
        for i in str:
            l.insert_value_to_head(i)

        print(is_palindrome(l))

自己

# coding:utf-8
# todo:链表实现LRU(最近最少使用策略)——缓存淘汰策略
'''

我的思路是这样的:我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。
1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中,又可以分为两种情况:
如果此时缓存未满,则将此结点直接插入到链表的头部;
如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。这样我们就用链表实现了一个 LRU 缓存,是不是很简单?
'''

#todo:回文字符串
'''
如何判断一个字符串是否是回文字符串的问题,我想你应该听过,我们今天的题目就是基于这个问题的改造版本。
如果字符串是通过单链表来存储的,那该如何来判断是一个回文串呢?你有什么好的解决思路呢?相应的时间空间复杂度又是多少呢?
'''

class SinglyLinkedList:
    class Node:
        def __init__(self,value):
            self.data = value
            self.next = None


    def __init__(self):
        self.head = None


    # 在头节点前插入一个新节点
    def insert_to_head(self,value):
        new_node = self.Node(value)
        # 链表无元素
        if self.head  is None:
            self.head = new_node
        else:
            # 链表有值,即为头部也有值
            # 需要把新的节点作为新的头节点,旧的头节点作为普通节点,即为新节点的后继节点
            new_node.next = self.head
            self.head = new_node
        return new_node


    #在尾节点插入新节点
    def insert_tail(self, value):
        if self.head is None:
            self.insert_to_head(value)
            return
        q = self.head
        # 寻找尾部节点
        while q.next is not None:
            q = q.next
        new_node = self.Node(value)
        q.next =  new_node



    # 在某节点后插入新节点
    def insert_after(self,node,value):
        if node is None:
            return
        new_node = self.Node(value)
        # 原node后边的节点先赋值给新node的next指针
        new_node.next = node.next
        # 原节点的next指针指向新节点
        node.next = new_node


    def insert_before(self,node,value):
        if self.head is None:
            self.insert_to_head(value)
            return
        q = self.head
        # 遍历出要插入节点前的节点node的前节点
        while q.next is not None and q.next != node:
            q = q.next
        # 找到了前节点,新节点连接前后
        if q.next == node:
            new_node = self.Node(value)
            new_node.next = node
            q.next = new_node


    def  find_by_value(self,value):
        if self.head is None:
            return
        q = self.head
        while q is not None and q.data != value :
            q = q.next
        if q is None:
            return
        return q

    def delete_by_value(self,value):
        if self.head is None:
            return
        q = self.head
        #记录前一个节点
        pre_node = None
        while q is not None and q.data != value:
            pre_node = q
            q = q.next
        # 链表中没有等于这个值的节点
        if q is None:
            return False
        # head的值value
        if pre_node is None:
            self.head = self.head.next
        else:
            pre_node.next = q.next
        return True

    def print_all(self):
        if self.head is None:
            return
        q = self.head
        while q is not None:
            print(q.data)
            q = q.next



def test_link():
    link = SinglyLinkedList()
    data = [1, 2, 5, 3, 1]
    for i in data:
        link.insert_tail(i)
    link.insert_to_head(99)
    # 打印内容为 99 1 2 5 3 1
    link.print_all()
    link.delete_by_value(2)
    assert not link.delete_by_value(999)
    assert link.delete_by_value(99)
    # 打印内容为 1 5 3 1
    link.print_all()
    assert link.find_by_value(2) is None
    new_node = link.find_by_value(3)
    link.insert_after(new_node, 10)
    assert link.find_by_value(3).next.data == 10
    link.insert_before(new_node, 30)
    assert link.find_by_value(5).next.data == 30

# 快慢指针找链表中间值
'''
若字符串长度是奇数,那么返回的节点就是中间的节点
若字符串长度是偶数,那么返回的节点就是中间的位置的前一个节点
'''
# def  get_mid(first:SinglyLinkedList.Node)->SinglyLinkedList.Node:
#     fast = first
#     slow = first
#     while fast.next and  fast.next.next :
#         fast = fast.next.next
#         slow = slow.next
#     return slow


def  get_mid(first):
    fast = first
    slow = first
    while fast.next and  fast.next.next :
        fast = fast.next.next
        slow = slow.next
    return slow

# 链表反转
def reverse_linklist(head):
    pre = None
    cur = head
    while cur:
        # 先把head后的节点找到
        next_node = cur.next
        # 之后把head指向None(后边的节点就不是None了,就是前节点)
        cur.next = pre
        # 把当前的节点head作为反转节点的前节点
        pre = cur
        # 把临时指针指向下一个节点
        cur = next_node
    return pre





# 检查是否是回溯字符串
def backTrackingStr(str_b,first):
    fast = first
    slow = first
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next
    # todo:为啥reverse_linklist()参数不是slow.next
    # slow是中间节点,链表反转的参数就是找到的中间值(和链表的长度是奇偶无关)
    reverse_head =reverse_linklist(slow)
    head = first
    is_palin = True
    while head and reverse_head:
        if reverse_head.data == head.data:
            head = head.next
            reverse_head = reverse_head.next
        else:
            is_palin = False
            break
    return  is_palin



if __name__ == '__main__':
    # test_link()
    # 初始化数据,放入链表
    link_str = SinglyLinkedList()
    str1 = '3213'
    str_head = link_str.insert_to_head(str1[0]) # 记录头指针作为找中点函数的入参
    for i in str1[1:]:
        link_str.insert_tail(i)
    # link_str.print_all()
    # todo:找链表中间值
    mid_node = get_mid(str_head)
    print(backTrackingStr(link_str,str_head))

老师-LRU

# Definition for singly-linked list.
class DbListNode(object):
    def __init__(self, x, y):
        self.key = x
        self.val = y
        self.next = None
        self.prev = None


class LRUCache:
    '''
    leet code: 146
        运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。
        它应该支持以下操作: 获取数据 get 和 写入数据 put 。
        获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
        写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。
            当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间
    哈希表+双向链表
    哈希表: 查询 O(1)
    双向链表: 有序, 增删操作 O(1)
    Author: Ben
    '''

    def __init__(self, capacity: int):
        self.cap = capacity
        self.hkeys = {}
        # self.top和self.tail作为哨兵节点, 避免越界
        self.top = DbListNode(None, -1)
        self.tail = DbListNode(None, -1)
        self.top.next = self.tail
        self.tail.prev = self.top

    def get(self, key: int) -> int:

        if key in self.hkeys.keys():
            # 更新结点顺序
            cur = self.hkeys[key]
            # 跳出原位置
            cur.next.prev = cur.prev
            cur.prev.next = cur.next
            # 最近用过的置于链表首部
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur

            return self.hkeys[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hkeys.keys():
            cur = self.hkeys[key]
            cur.val = value
            # 跳出原位置
            cur.prev.next = cur.next
            cur.next.prev = cur.prev

            # 最近用过的置于链表首部
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur
        else:
            # 增加新结点至首部
            cur = DbListNode(key, value)
            self.hkeys[key] = cur
            # 最近用过的置于链表首部
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur
            if len(self.hkeys.keys()) > self.cap:
                self.hkeys.pop(self.tail.prev.key)
                # 去掉原尾结点
                self.tail.prev.prev.next = self.tail
                self.tail.prev = self.tail.prev.prev

    def __repr__(self):
        vals = []
        p = self.top.next
        while p.next:
            vals.append(str(p.val))
            p = p.next
        return '->'.join(vals)


if __name__ == '__main__':
    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    print(cache)
    cache.get(1)  # 返回  1
    cache.put(3, 3)  # 该操作会使得密钥 2 作废
    print(cache)
    cache.get(2)  # 返回 -1 (未找到)
    cache.put(4, 4)  # 该操作会使得密钥 1 作废
    print(cache)
    cache.get(1)  # 返回 -1 (未找到)
    cache.get(3)  # 返回  3
    print(cache)
    cache.get(4)  # 返回  4
    print(cache)