数据结构指数据对象中数据元素之间的关系
Python 给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构叫做 Python 的内置数据结构，比如列表、元组、字典。而有些数据组织方式，Python 系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式称之为 Python 的扩展数据结构，比如栈，队列等.
线性表：一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一。
根据线性表的实际存储方式，分为两种实现模型：顺序表和链表。Python 中的 list 和 tuple 两种类型采用了顺序表的实现技术。
顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理，常见的有单向链表和双向链表。
在 Python 的官方实现中，list 实现采用了如下的策略：在建立空表（或者很小的表）时，系统分配一块能容纳 8 个元素的存储区；在执行插入操作（insert 或 append）时，如果元素存储区满就换一块 4 倍大的存储区。但如果此时的表已经很大（目前的阀值为 50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。
单链表:
class Node():
'''单链表节点类'''
def __init__(self,elem):
self.elem = elem
self.next = None
class SLink():
def __init__(self,node=None):
if node is None:
self.__head = node
else:
self.__head = Node(node)
def is_empty(self):
return self.__head==None
def length(self):
count = 0
curNode = self.__head
while curNode != None:
count+=1
# self.__head = curNode.next
curNode = curNode.next
return count
#遍历
def travel(self):
curNode = self.__head
while curNode !=None:
print(curNode.elem,end=' ')
curNode= curNode.next
print()
#查找
def find(self,item):
node = Node(item)
curNode = self.__head
while curNode !=None:
if curNode.elem == node.elem:
return True
self.__head = curNode.next
curNode = curNode.next
return False
#头部添加
def add(self,item):
node = Node(item)
if self.__head == None:
self.__head=node
else:
curNode = self.__head
self.__head = node
node.next = curNode
#尾部插入
def append(self,item):
node = Node(item)
if self.__head == None:
self.__head = node
else:
curNode = self.__head
while curNode.next is not None:
curNode = curNode.next
curNode.next = node
#指定位置插入
def insert(self,num,