一、数组

    数组对应的英文是array，是有限个相同类型的变量所组成的有序集合，数组中的每一个变量称为元素。数组是最简单、最常用的数据结构。

数组存储格式：

 在Python语言中，并没有直接使用数组这个概念，而是使用列表(list）和元组( tuple）这两种集合，它们本质上都是对数组的封装。其中，列表是一个动态可扩展的数组，支持任意地添加、删除、修改元素;而元组是一个不可变集合，一旦创建就不再支持修改。

 数据结构的操作无非是增、删、改、查4种情况！

二、数组的基本操作

 1、读取元素

print(ll[3])

 2、更新元素

ll[5]=100

print(ll[5])

可知： 数组读取元素和更新元素的时间复杂度都是O（1)。
 

 3、添加元素

    插入元素有3种情况：

1. 尾部插入
2. 中间插入
3. 超范围插入

 （1）尾部插入，是最简单的情况，直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作。

 

（2）中间插入，稍微复杂一些。由于数组的每一个元素都有其固定下标，所以不得不首先把插入位置及后面的元素向后移动，有个空位置，再把要插入的元素放到对应的数组位置上。

class MyArray:'''初始化'''def __init__(self, capcity):self.arrs = [None] * capcity  # 数组self.size = 0  # 大小'''添加'''def add(self, index, value):# 判断是否超出范围if index < 0 or index >= self.size:raise Exception('数组下标越界！')# 将数据往后移动,直到index这个位置为止for i in range(self.size - 1, index - 1, -1):self.arrs[i + 1] = self.arrs[i]# 插入新数据self.arrs[index] = value# 个数self.size += 1'''显示'''def show(self):for i in range(self.size):print(self.arrs[i], end=',')

if __name__ == '__main__':# 创建对象my = MyArray(4)#在第一个位置添加数据my.add(0, 8)my.add(0, 10)my.add(0, 20)my.add(0, 2)# IndexError: list assignment index out of range# my.add(0,15)#显示数据my.show()

（1） 索引正常范围

 

 （2）索引超出范围

 （3）如现在有一个长度为6的数组，已经装满了元素，这时还想插入一个新元素。

   解决方法：  可以创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素统统复制过去，这样就实现了数组的扩容。

 #创建一个新数组，其容量扩大旧数组2倍，再把原数组拷贝到新数组中def resize(self):self.arrnews=[None]*len(self.arrs)*2#旧数组的数据拷贝到新数组中for i in range(self.size):self.arrnews[i]=self.arrs[i]#再把新数组给旧数组self.arrs=self.arrnews'''添加'''def add(self, index, value):# 判断是否超出范围if index < 0 or index > self.size:raise Exception('数组下标越界！')#如果超出范围，就扩容if self.size>=len(self.arrs):self.resize()# 将数据往后移动,直到index这个位置为止for i in range(self.size - 1, index - 1, -1):self.arrs[i + 1] = self.arrs[i]# 插入新数据self.arrs[index] = value# 个数self.size += 1

if __name__ == '__main__':# 创建对象my = MyArray(6)#在第一个位置添加数据my.add(0, 8)my.add(0, 10)my.add(0, 20)my.add(0, 2)my.add(0, 7)my.add(0, 3)# IndexError: list assignment index out of range# my.add(100,200)for i in range(30,41):my.add(0,i)#显示数据my.show()

（1） 数组大小超出范围，直接扩容2倍

（2）索引超出范围

 4、删除元素

        数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪动1位。

 '''删除数据'''def remove(self,index):if index<0 or index>self.size:raise Exception('数组下标越界！')#从右往左移动，直到indxfor i in range(index,self.size):self.arrs[i]=self.arrs[i+1]#个数减少self.size-=1

if __name__ == '__main__':# 创建对象my = MyArray(6)#在第一个位置添加数据my.add(0, 8)my.add(0, 10)my.add(0, 20)my.add(0, 2)my.add(0, 7)my.add(0, 3)# IndexError: list assignment index out of range# my.add(100,200)for i in range(30,41):my.add(0,i)#显示数据my.show()my.remove(3)# my.remove(23)my.show()

 数组拥有非常高效的随机访问能力优势，数组的劣势体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。

总的来说，数组所适合的是读操作多、写操作少的场景。

三、链表

链表（linked list〉是一种在物理上非连续、非顺序的数据结构，由若干节点(node)所组成。

(1) 单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。

(2) 双向链表比单向链表稍微复杂一些，它的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。

数组在内存中的存储方式是顺序存储，而链表在内存中的存储方式则是随机存储。 

数组的内存分配方式

链表的内存分配方式
 

四、链表的基本操作

1、查找节点

     从头节点开始找第3个节点

  

class Node:  #新节点def __init__(self,data):self.data=dataself.next=Noneclass MyLinkedList:'''初始化 大小，头部，尾部'''def __init__(self):self.size=0self.head=Noneself.tail=None'''根据索引查找数据'''def get(self,index):if index<0 or index>self.size:raise  Exception('超出链表节点范围！')p=self.headfor i in range(index):p=p.nextreturn p

2、更新节点

     从头节点开始找第2个节点进行修改

3、添加节点

与数组类似，在链表中插入节点时，同样分为3种情况:

1. 尾部插入
2. 头部插入
3. 中间插入

• 尾部插入

最后一个节点的next指针指向新插入的节点

• 头部插入

1. 把新节点的next指针指向原先的头节点。
2. 把新节点变为链表的头节点。

• 中间插入

1. 新节点的next指针指向插入位置的节点。
2. 插入位置前置节点的next指针，指向新节点。

   

  '''添加新节点'''def insert(self,data,index):if index < 0 or index > self.size:raise Exception('超出链表节点范围！')#获取节点对象node=Node(data)#空链表if self.size==0:self.head=nodeself.tail=node#插入头部elif index==0:node.next=self.head  #将新节点指向原先的头节点self.head=node  #新节点变为链表的头节点#插入尾部elif self.size==index:self.tail.next=node #尾节点指向新节点self.tail=node   #新节点变为链表的尾节点#插入中间else:prev_node=self.get(index-1) #获取前一个节点node.next=prev_node.next  #新节点指向插入位置的节点prev_node.next=node  #前置节点指向新节点self.size+=1

if __name__ == '__main__':my= MyLinkedList()for i in range(5):my.insert(20+i,i)#my.insert(100,10)my.show()

4、删除节点

链表的删除操作同样分为3种情况:

1. 尾部删除
2. 头部删除
3. 中间删除
    

1. 尾部删除

      2.头部删除

     3.中间删除

 

 '''删除节点'''def remove(self, index):if index < 0 or index > self.size:raise Exception('超出链表节点范围！')#删除头节点if index==0:del_node=self.head  #删除头节点self.head=self.head.next #指向头节点next成为头节点#删除尾节点elif index==self.size-1:prev_node = self.get(index - 1) #获取前一个节点del_node = prev_node.next  #删除前个节点nextprev_node.next=None  #前一个节点为空self.tail=prev_node  #尾节点指向前节点#删除中间节点else:prev_node=self.get(index-1)  #获取前节点next_node=prev_node.next.next   #获取前节点的下一个节点del_node=prev_node.next #删除节点prev_node.next=next_node #前节点指向下个节点self.size-=1return del_node'''显示'''def show(self):# 头节点p=self.head#循环节点是否为空while p is not None:print(p.data)  #打印节点p=p.next   #指向下一个节点指针nextprint('*'*30)

if __name__ == '__main__':my= MyLinkedList()for i in range(5):my.insert(20+i,i)my.show()my.remove(3)#my.remove(30)my.show()

五、数组VS链表

   总之： 数组在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些。链表的优势在于能够灵活地进行插入和删除操作，如果需要频繁插入、删除元素，用链表更合适一些。