新动态：python 数组和链表

【资料图】

import timen = 500list_1 = []for i in range(1, n+1):    list_1.append(i)position = 200value = 'x'# 方法1start = time.perf_counter()list_1.append(list_1[n-1])# [1,2,3,4,5]-->[1,2,3,4,5,5]for i in range(n, position-1, -1):    # 全部右移动  如果需要在位置[2]插入  [1,2,3,4,5,5]-->[1,2,3,3,4,5]    list_1[i] = list_1[i-1]list_1[position] = valueprint(time.perf_counter()-start)   # 2*10^-5print(list_1)# 使用内置函数操作# start_2 = time.perf_counter()# list_1.insert(position-1, value)# print(time.perf_counter()-start_2)  # 8*10^-7# 显然使用内置函数时插入时使用的时间大大减少# 海盗问题# 64个人被海盗劫持 围成一个圈1-64 依次报数 每个报数11的就会被枪决 有32个倒霉蛋会被枪决 哪些位置的倒霉蛋会被枪毙def pirates(total, out, end):    # 初始化数据    result = []  # 结果数组    index = 0  # 索引    number = 0  # 报数计数    inside_count = total  # 剩余圈内元素    circle = [1]*total  # 初始化数组 在圈内的状态为1    while inside_count > end:  # 只要圈内人数大于end人数就执行        number += circle[index]  # 报数等于圈内的索引        if number == out:  # 如果报数等于出去的数字            result.append(index+1)  # 在结果中添加索引+1            inside_count -= 1  # 圈内的人数-1            number = 0  # 重新初始化数字        index = (index+1) % total        # 当索引index加1后，通过对总数total取模，可以得到在循环数组中的下一个位置。        # 例如，如果index是2，total是3，那么(2 + 1) % 3的结果是0，就回到了数组的起始位置    return resultprint(pirates(64, 11, 32))

# 数组是顺序存储结构的线性表 链表数据结构同样是一种线性表 是链式储存结构 以连续和不连续的储存单元储存数据# 链表# 1.单向链表 每个数据节点 包括一个数据和一个指针 指针指向下一个数据列表# 2.循环链表 循环列表就是在单向链表的基础上  最后一个数据节点指向第一个数据节点# 3.双向链表 双向列表就是在单向链表的基础上  每个数据节点增加了一个指向前一个数据节点的指针# 例子# 创建数据节点对象class Node:    def __init__(self, data=None):        self.data = data  # 数据        # self.next表示指向链表中下一个节点的指针。在链表中，每个节点都有一个指向下一个节点的指针，        # 这就是使得链表能够在其中添加、删除节点和遍历节点的关键所在。当我们向链表中添加新节点时，        # 将当前节点的next指针指向新节点，从而将其添加到链表中。        # 同样地，当我们遍历链表时，我们可以使用next指针来移动到链表中的下一个节点，并执行我们需要的操作        self.next = Noneclass LinkedList:    # 初始化链表 链表头 链长度    def __init__(self):        self.head = None    # 给链表添加数据 在尾部添加数据    def append(self, data):        new_node = Node(data)        # 如果链表没有表头 则把添加的数据作为表头        if self.head is None:            self.head = new_node            return        curr_node = self.head        # 链表中添加新节点的功能。它首先将curr_node设置为链表的头节点，        # 然后在链表中找到最后一个节点，最后将新节点添加到链表的末尾。        while curr_node.next is not None:            # 当前节点的指针移动到链表中的下一个节点            curr_node = curr_node.next        curr_node.next = new_node    def append_head(self, data):        new_node = Node(data)        new_node.next = self.head        self.head = new_node    def display(self):        curr_node = self.head        while curr_node is not None:            print(curr_node.data)            curr_node = curr_node.next    def delete_at_head(self):        if self.head is not None:            self.head = self.head.next    def delete_at_tail(self):        prev = self.head        curr = self.head.next        while curr.next is not None:            prev = curr            curr = curr.next        prev.next = Nonedef test_linked_list():    linked_list = LinkedList()    linked_list.append("嘉然")    linked_list.append("星瞳")    linked_list.append("露米")    linked_list.append("向晚")    linked_list.append("贝拉")    linked_list.append_head("龙姬")    linked_list.append_head("永恒")    linked_list.delete_at_tail()    linked_list.delete_at_head()    linked_list.display()test_linked_list()