TOC
数据结构
这是一个概念，数据结构，数据结构是以某种方式(比如编号)组合起来的数据元素(如数字、字符串乃至其他数据结构)集合，说白了，数据结构就是数据如何在内存中组织，也就是数据的组织方式，在Python中最基本的数据结构为序列(swquence)，序列中每个元素都有编号，即其位置或索引，其中第一个元素的索引为0，第二个元素的索引为1，依此类推。在有些编程语言中，从1开始给序列中的元素编号，但从0开始指出相对于序列开头的偏移量。这显得更自然，同时可回绕到序列末尾，用负索引表示序列末尾元素的位置；
线性数据结构
列表向解释器申请内存的时候，就会直接问系统内核要一段连续的内存空间，比如要五个内存空间，那么如果过一段实际之后，列表要进行扩展，如果空间足够大的话，就会直接将原来这段连续的空间的后面再开辟一个与原内存空间的连续空间，如果空间不连续那么垃圾回收器就会对内存进行整理，整理出与之更大连续的空间，所以这就是列表高效的原因，快速的定位列表元素；
这就是列表的好处，也是它的坏处，因为如果要对内存的元素进行删除操作的话，那么这个列表内元素的内存地址就需要进行重新排列，删除列表中的第二个元素，或者向第二个元素之前插入一个元素，那么第二个元素后面的元素内存地址将依次向前调整，这就是列表性能最差的所在之出；
列表其实在C语言中，它就是数组，C语言不像Python和JAVA，它会动态的回收或者调整内存，所以C语言和C++用不好的话，那么内存中就会出现大量的内存碎片，如果大量的内存碎片出现之后，并没有某种算法对其进行调整，那么最后带来的结果就是，用着用着，当有需要问内存申请一端连续空间，存放100个元素的时候，结果会发现内存无法开辟出来，内存其实是还有的，只不过没有连续的空间，在Python或者Java中，通过垃圾回收机制，会不断的去规整内存，将连续的空内存编址放在一起，将已经申请的内存也放在一起；
单向链表
列表比较适合使用索引的方式去读取指定位置的元素，因为它是线性编址的，而链表最大的问题是，它在内存空间的表示上，不一定的连续的，如果出现连续的那也是巧了，链表它第一个元素可能编址为101，第二个元素可能编址为104，这就是链表，也就是说他们的元素并没有连续的排列，他们是散落的；
但是链表也是一个数据结构，它也是一种容器可以存放元素，链表最大的特点在于，知道了第一个元素的位置，才能知道第二个元素的位置，因为在第一个元素里面就持有第二元素在内存中的位置，但是知道了第一个元素，是无法知道第三个元素的，需要找到第一个元素，再找到第二个元素，最终才能找到第三个元素，这就是链表；
所以链表，并不能通过索引的方式寻找指定的元素，但是连标对于数据的修改或者新增是挺好的，不用再次重新排列元素在内存中的位置；
双向链表
双向链表和单向链表的区别是，双向链表，不仅知道上一个元素的位置，也知道下一个元素的位置，但是他们在内存中依旧是零散的，一样，它最大的优势是比较便于数据的增删的，效率比较高，频繁的进行数据增删时，使用链表比较合适；
队列
队列就是queue，队列差不多，只不过，它不允许进行在队列中间进行增删改查操作，遵循先进先出的原则，不允许插队，允许插队的是List，如果不能插队只能在头或者尾操作，这种就叫做queue队列；
栈
栈stack和队列相反，一样允许插队，它是先进后出的一种数据结构；
序列
序列是一种数据结构，其中元素带有编号(编号从0开始)，列表、字符串和元组都属于序列，其中列表是可变的，而元组和字符串是不可变的(一旦创建，内容就是固定的)，要访问序列的一部分，可以使用切片操作，切片需提供两个参数，起始位置和结束位置，要修改列表，可给其元素赋值，也可使用赋值语句给切片赋值；
Python内置来多种序列，序列就是被排成一列的对象，这样，每个元素不是在其他元素之前，就是在其他元素之后。这里，元素之间的顺序非常重要；
Python包含 6 中内建的序列，包括列表、元组、字符串、Unicode字符串、buffer对象和xrange对象；
并且，对于Python有几种操作适用于所有序列，包含索引、切片、相加、相乘和成员资格检查，另外，Python还提供来一些内置函数，可用于确定序列的长度以及找出序列中最大和最小的元素等；
序列相关函数
下列是Python内置的几个函数，可对所有序列进行操作，也是主要实现一些特殊的功能，比如最大值、最小值等；
max：返回序列中内最大的元素；
min：返回序列中最小的元素；
len：返回序列的长度；
cmp：比较两个序列的元素；
list：将元组、数字、字符串等数据类型转换为列表，并且还可以初始化一个空列表；
tuple：将列表、数字、字符串等数据类型转换为元组，并且还可以初始化一个空元组；
序列基本运算
对于序列来讲，也可以进行基本的序列运算，比如使用加法运算符，来进行序列拼接，使用乘法运算，来进行对序列的组装，使用成员资格运算，来检查特定的值是否包含在序列中，可以使用In运算符，它检查是否满足指定的条件，并返回相应的值，满足时返回True，不满足时返回False，这样的运算符称之为布尔运算符；
# 加法运算
print('123'+'456') # '123456'
# 乘法运算
print('123'*3) # '123123123' 相当于三个一样的序列进行相加
# 成员资格运算
name="caichangen"
print("e" in name) # True
print("x" in name ) # False
列表(可变数据类型)
列表是一段线性数据结构的数据，线性数据结构就是连续的，就像是内存可以划分成一个一个连续的小格子，这个小格子会进行编址，这个编织就像房间排号一样，比如第一个小格子是101，第二个102，第三个是103，但是我们的数据结构它并不一定是使用这种连续的编址来使用内存的，如果定义了一个101，紧接着使用了一个103的地址，那么这个在空间上就是不连续的；
Python列表
Python的List其实就是C语言的数组，只不过被Python包装了，因为Python也是C语言底层写的，只不过它是包装出来的，增强了很多功能，所以Python中的列表，本质也就是C语言的数组，列表内的个体，我们称之为元素，所以列表就是由若干个元素组成的集合，元素可以是任何对象，只要是合法的值，都可以存储进来，它就是一个容器，不同类型的对象都可以往里面放；
列表也是可以扩张的，也就是说容器的体积不够了，还可以随意扩展，也可以是不同类型的，并且列表内的元素是有序的，它不是无序，它是没有进行排序的，只不过他们是在内存中是的地址是相连的；
前面的例子使用了大量的列表来进行演示，但对于列表和元组以及字符串的不同之处在于，元组和字符串是不可变的，而列表是可以随意增删的，另外列表还有很多特有的方法；
列表初始化
列表常见的初始化操作有多种，比如[]、list()都可以初始化出一个空列表，并且列表的元素可以是所有合法的对象，可以是一个字符串，也可以是一个类；
>>> []
[]
>>> list()
[]
>>> ["cce",1,str,(1,2),[12,3]]
['cce', 1, <class 'str'>, (1, 2), [12, 3]]
- 注意：
可将任何序列，作为list的参数，而不仅仅是字符串
列表索引
列表也是有索引的，也称之为下标，索引其实就是元素排列的一个编号，下标默认从0开始，即索引为0就是第一个元素，并且，它还支持一种负索引的方式，默认从-1开始，通过索引我们可以直接找到这个元素，用这种方式定位元素，速度是非常快的；
lst = [1, 2, 3, 4]
print(lst[0]) # 1
print(lst[-1]) # 4
列表操作
对于列表执行所有的标准序列操作，如索引、切片、拼接和相乘，但列表但有趣之处在于它是可以修改的，本章主要一些修改列表的方式，如元素赋值、删除元素、切片赋值以及使用列表的方法；
修改列表
修改列表很容易，只需要使用普通赋值语句即可，但不是使用类似于x=2这样但赋值语句，而是使用索引表示法将指定位置的元素赋值，如x[2]=2；
x = [1, 2, 3]
x[0] = 2 # 将列表x里面索引为0的元素的值修改为2
print(x) # [2, 2, 3]
- 注意：
不能给不存在的元素赋值，因此如果列表的长度为2，几句不能给索引为100的元素赋值，如果要这样做，那列表的长度最少101
删除元素
从列表中删除元素，值需要del语句即可；
x = [1, 2, 3]
del x[1] # 使用del语句，删除索引为1的元素
print(x) # [1, 3]
切片赋值
切片是一项及其强大的功能，而能够给切片赋值让这项能力显得更加强大；
x = ["cce", "caichangen", "cfj"]
print(x[1:]) # ['caichangen', 'cfj']
x[1:] = list("12")
print(x) # ['cce', '1', '2']
可以看到，可以通过切片的方式同时给多个元素赋值，可能会觉得这并没什么大不了的，前面说过，不能给不存在的元素赋值，但是其实通过切片赋值是有一个特性的，可将切片出来的数据替换为长度与其不同的序列，增大原有列表的长度；
x = [1, 2, 3]
x[:] = [4, 5, 6, 7, 8]
print(x) # [4, 5, 6, 7, 8] 可以看到，列表的长度发生了变化
同时，切片赋值还可以在不替换现有数据的情况下插入新的元素，需要注意的是第一个元素的位置所在的位置就是原列表切片的第一个索引号的位置；
x = [1, 2, 3, 7]
x[-1:0] = [4, 5, 6] # 4的位置为原列表-1的位置，5和6紧随其后，原-1后面的元素也将在元素6之后
print(x) # [1, 2, 3, 4, 5, 6, 7]
由上面切片赋值，可以变通一下，利用切片赋值，将原列表的元素进行削减，其实它就相当于del语句的效果；
x = [1, 2, 3, 4]
x[1:3] = [] # 实现将原数组指定切片索引元素删除
print(x) # [1, 4]
列表方法
方法是与对象(列表、数、字符串等)联系紧密的函数，换一种说法，方法即类里面实现特定功能的函数称之为方法，通常调用方法的语法为 object_name.method(arguments)；
列表为Python原生的数据类型的实现类，该类存在很多实现特定功能的方法，每个方法都有其特定的功能，那么对于列表类的方法，有如下几种；
append：将一个对象，或者一个序列追加到列表的末尾；
clear：可实现清空列表的所有元素，那么最后的结果就是[]，引用计数减1；
copy：copy可实现列表复制，直接将内存的数据copy一份，这是深拷贝，和原列表完全隔离，其实也并非完全隔离，仅限于一层 ，第二层则是浅拷贝，比如列表里面包含了一个列表，那对于里层这个列表则是浅拷贝；
count：使用count方法可以统计指定元素在列表中出现的次数；
extend：该方法可以扩展列表，可以将多个值附加到列表到末尾，需要知道的是，extend只支持可迭代数据类型，比如常见的列表、元组、字符串等，可能看起来像列表相加，其实不然，列表相加返回的是一个新的序列，而extend则是在原有列表的基础之上扩展元素；
index：该方法可以在列表中从左到右查找指定元素并且是第一次出现的索引号；
insert：该方法用于将一个字符或者一个序列插入列表，需要注意的是，insert需要给定两个形参，第一个是插入的索引位置，第二个参数是插入的数据，效率及其低下；
pop：pop方法可以从列表中删除一个元素(删除的元素为最后一个元素)，并返回这一元素，并且POP方法实现一种常见的数据结构 栈(stack) ，栈就像一叠盘子，可以从上面添加盘子也可以在上面取走盘子最后盘子最先取走，实现后进先出，push和pop是大家普遍接受的两种栈操作(取走和加入)，Python的列表没有提供push但是可以使用append代替，使用pop(0)和append实现栈的思路，当然也可使用insert(0,val)和pop来实现；
remove：使用remove方法可删除指定的元素；
reverse：使用reverse方法可以按相反的顺序排列列表中的元素；
sort：sort方法就是将列表中的元素按照ASCII码进行排序，并将排序的结果赋值给原列表，需要传递两个参数，key和reverse，key为必给项，因为列表里面的元素可以是多种类型的，数字也无法直接和字符串排序，所以可以使用key=int表示，在正式排序之间将元素转换成int类型进行比较，继而进行排序，当然，它并不会修改元素本身，只是用来比较，排序默认是升序的，使用reverse可以将排序之后的结果转成降序；
时间复杂度
可以看到，我们的列表有很多方法，需要注意两个方法，index和count，他们都存在一个很大的问题，他们用起来相当简单，以count为例，它在查找指定数字出现过几次的时候，必须将这个列表从左到右所有的元素全部遍历一遍，假设我们有一个列表，里面有十亿个元素，那么如果我们对它使用count的时候，Python就对将这十亿个元素全部遍历一遍，一个一个查，这是一种非常低效的方式；
十亿个元素，需要比对十亿次，十千万个元素要比较十千万次，这种数据如果有n个元素，那这种比较的效率就称为O(n)，因为我们有n个元素，我们就得遍历所有的元素，有几个元素就得遍历几下，那就是n，有n个元素就得遍历n次，所以这种时间复杂度就称为O(n)；
这种时间复杂度是非常糟糕的方式，随着N的规模扩大，效率会急剧下降，有一百万个就得遍历一百万个，有一千万个就得遍历一千万个；
其实我们如果使用索引取值，对于列表来讲，就是最好的，比如lst[100]，这个时间复杂度为O(1)，一下就找到了，用索引方式，只需要一下就找到了，找到这个列表在内存中的起始位置，偏移100个就找到了；
再看insert方法，效率及其低下，因为它是插入数据，它一旦在一个指定的元素后面插入元素，如果后面还有元素的话，那么后面的元素得依次向后挪动，所以insert这种方法，能少用则少用，比如insert(0,1)，在索引为0的前面插入一个元素1，这种效率的最低的，原列表的所有元素全部得向后挪动；
深浅拷贝
拷贝也是有深浅之说的，在Python中，对象赋值实际上是对象的引用。当创建一个对象，然后把它赋给另一个变量的时候，默认情况下是浅拷贝的，什么叫浅拷贝呢，比如[1,[2,3],4]，这么一个列表，当我们拷贝的时候，默认只会对1和4拷贝出来，并且开辟一段新的内存空间存储，而[2,3]呢，并不是这样，而是将这个对象的内存地址拷贝了一遍，因为[1,[2,3],4]本身就是一个列表容器，它默认只拷贝第一层，而容器内部好包裹一个容器的时候，在默认情况下不会深入到这个容器里面将里面的元素拷贝，所以这就称之为浅拷贝；
这样带来的问题是，当[1,[2,3],4]这个列表里面的[2,3]发生修改时，拷贝出来的对象，和原对象会同时进行修改；
那么对于深拷贝，[1,[2,3],4]这样的一个列表，会深入进去将容器内部的容器也进行一次拷贝，利用一个新的内存空间进行存储；
# 浅拷贝
import copy
l1=[1,2,[1,2],3]
l2=copy.copy(l1)
l2[2][0]=3
print(l1) # [1, 2, [3, 2], 3]
print(l2) # [1, 2, [3, 2], 3]
# 扩展一
lst1=[1,2,3]
lst2=[lst1]*2 # 使用乘法，如果使用了引用对象，实际上就是浅拷贝；
for l in lst2:
print(id(l))
# 4379047304
# 4379047304
# 扩展二
l1=list(range(10))
l2=l1
print(id(l1),id(l2))
# 深拷贝
import copy
l1=[1,2,[1,2],3]
l2=copy.deepcopy(l1)
l2[2][0]=3
print(l1) # [1, 2, [1, 2], 3]
print(l2) # [1, 2, [3, 2], 3]
浅拷贝重点
对于浅拷贝是一个非常重要的情况，需要着重注意，当我们有一个序列，序列里面包含了一个其他序列的时候，如果我们使用乘法，使得其外层序列进行扩展的时候，其实就是对里层序列进行了浅拷贝，带来的结果就是，当我们修改其中一个元素，所有的元素会一起跟着变化，因为乘法实际就是浅拷贝；
tup=([1,2],)*2
tup[0][0]=100
print(tup) # ([100, 2], [100, 2])
- 注意：
对于这个例子，虽然tup元祖内部的列表内元素可以进行修改，但是列表本身是不可以修改的，比如tup[0]=100这样是不行的；
