人生需要三种姿态：
对过去，要淡；
对现在，要惜；
对未来，要信。
如果担心现在才开始学某样东西
年纪已经太大的话
不妨这样想 ：就算因此放弃不学,年纪还是照样会变大的。
人生，任何时候开始都不晚，只要行动就有机会！
难点章节
程序员基本功： 写一大段代码基本不会出错，最怕的是逻辑混乱，逻辑混乱写什么都是错的；
总结：
- for循环在python中是在知道有限次数的情况下使用的；
- 锻炼自己的应该是 逻辑思维；分析代码的能力；思路不清晰，说明你不得法；
链表是每个程序员都应该知道的基本数据结构!
可分为两类：链表类（容器），元素类（里面提交合法的值）
1. 链表LinkedList
链表：是一种以线性顺序存储的数据结构，但并不要求按顺序存储。它由节点组成，每个节点除了储存自身数据外，还包含一个指向下一个节点的引用（或指针）。
打个比方：列表就好像火车，每一节车厢连在一起，如果你知道车头在哪里，大致就也能知道第8节车厢在哪。
而链表，就像是去往同个目的地的车队，有很多辆车，大家排着队行驶。虽是一个整体，但队伍的顺序是可以很容易调整的。
单链表
两个特例:(头和尾)我们会有一个 head 引用指向链表的开头，而链表的结尾，下一个节点则指向空值 None。
除了上图演示的单向链表外，还存在双向链表（每个节点还增加一个指向前一个节点的引用）和循环链表（最后一个节点的下一个节点会指向第一个节点）。
1.1 单向链表
链表中最简单的形式
每个节点包含两个域，一个元素域，一个链接域
链接指向链表中的下一个节点；最后一个节点的链接域指向一个空值
head 保存首地址；item 存储元素（数据）；next 指向下一个节点地址链表 VS 序列
序列：随机读取，使用下标
链表：增加指针域，空间开销偏大，使用更加灵活，如插入
1.2 双向链表
比单向链表复杂
每个节点有两个链接
一个指向前一个节点，当此节点为第一个节点时，指向空值另一个链接指向下一个节点，当此节点为最后一个节点时，指向空值
head 保存首地址，item 存储数据，next 指向下一节点地址，prev 指向上一结点地址
| 常用操作方法 | |
|---|---|
| is_empty() | 链表是否为空 |
| length() | 链表长度 |
| items() | 获取链表数据迭代器 |
| add(item) | 链表头部添加元素 |
| append(item) | 链表尾部添加元素 |
| insert(pos, item) | 指定位置添加元素 |
| remove(item) | 删除节点 |
| find(item) | 查找节点是否存在 |
链表的优点和缺点
- 链表相较顺序存储列表，最大的好处就是很容易往序列中添加和删除元素，单看插入和删除操作，最优可达到O(1)的复杂度
- 不需要连续的存储空间，且不需要预先知道数据集的大小。
- 链表没有顺序表随机读取的优点，同时增加了节点的指针域，增大了空间开销，但是对内存的使用相对更灵活。
| 操作 | 链表 | 顺序表 |
|---|---|---|
| 访问元素 | O(n) | O(1) |
| 头部插入/删除 | O(1) | O(n) |
| 尾部插入/删除 | O(n) | O(1) |
练习：1.用面向独享实现LinkedList链表
单向链表实现append、iternodes方法；
双向链表实现append、pop、insert、remove、iternodes方法；
单向链表
class Node:
def __init__(self,item,next=None):
self.item = item # 实例记录 数据部分；
self.next = next # 下一趟是谁？ 有：没有：None
def __repr__(self): # 观察数据；
return '< {} -->{}>'.format(self.item,self.next.item if self.next else 'None')
class LinkedList: # 链表
def __init__(self):
self.head = None # 头部结点；
self.tail = None # 尾部结点；
self.items = []
def append(self,item):
node = Node(item) # 创建结点对象
if self.head is None: # 空链表；
self.head = node
#self.tail = node
else: #非空链表；
self.tail.next = node
#self.tail = node
self.tail = node
return self
def iternodes(self):
current = self.head
while current:
yield current
current = current.next
ll = LinkedList()
ll.append(1)
ll.append(2).append(3)
for x in ll.iternodes():
print(x)
#------------------------------------------------
< 1 -->2>
< 2 -->3>
< 3 -->None>
class Node:
def __init__(self,item,next=None):
self.item = item # 实例记录 数据部分；
self.next = next # 下一趟是谁？ 有：没有：None
def __repr__(self): # 观察数据；
return '< {} -->{}>'.format(self.item,self.next.item if self.next else 'None')
class LinkedList: # 链表
def __init__(self):
self.head = None # 头部结点；
self.tail = None # 尾部结点；
self.items = []
def append(self,item):
node = Node(item) # 创建结点对象
if self.head is None: # 空链表；
self.head = node
#self.tail = node
else: #非空链表；
self.tail.next = node
#self.tail = node
self.tail = node
self.items.append(node)
return self
def get(self,index):
return self.items[index]
def iternodes(self):
# current = self.head
# while current:
# yield current
# current = current.next
#return iter(self.items)
yield from self.items
ll = LinkedList()
ll.append(1)
ll.append(2).append(3)
print(ll)
for x in ll.iternodes():
print(x)
#--------------------------------------------------
<__main__.LinkedList object at 0x000001A0115E4128>
< 1 -->2>
< 2 -->3>
< 3 -->None>
双向链表
双向链表实现 append,pop,insert,remove,iternodes 方法；
class Node: # 结点对象；
def __init__(self,item,prev=None,next=None):
self.item = item # 实例记录 数据部分；
self.next = next # 下一趟是谁？ 有：没有：None
self.prev = prev
def __repr__(self): # 观察数据；
return '< {} -->{}>'.format(
self.item,
self.next.item if self.next else 'None',
self.next.item if self.next else 'None')
class LinkedList: # 链表
def __init__(self):
self.head = None # 头部结点；
self.tail = None # 尾部结点；
self.items = []
def append(self,item):
node = Node(item) # 创建结点对象
if self.head is None: # 空链表；
self.head = node
#self.tail = node
else: #非空链表；
node.prev = self.tail
self.tail.next = node
#self.tail = node
self.tail = node # 更新尾部结点；
self.items.append(node)
return self
def insert(self,index,value):
if index < 0:
raise IndexError('Negative index erro {}'.format(index))
for i,node in enumerate(self.iternodes()):
if i == index:
current = node
break
else:
self.append(value)
return
# 找到了插入点和元素；
node = Node(value) # 待加入结点对象；
prev = current.prev
next = current.next
if index == 0:
# node.next = current
# current.prev = node
self.head = node
else:
# node.next = current
# current.prev = node
node.prev = prev
prev.next = node
node.next = current
current.prev = node
def pop(self): # 尾部移除
if self.tail is None: # 0元素
raise Exception('Empty')
node = self.tail
item = node,item
prev = node.prev
if prev is None: # 一个元素；
self.head = None
self.tail = None
else: # 2个元素，移除元素，只剩最后一个
prev.next = None
self.tail = prev
def remove(self,index):
if index < 0:
raise IndexError('Negative index erro {}'.format(index))
if self.head is None: # 0元素
raise Exception('Empty')
current = None
for i,node in enumerate(self.iternodes()):
if i == index:
current = node
break
else:
raise IndexError('wrong index')
# 找到了要移除的结点； current = node ;
prev = current.prev
next = current.next
# 分4种情况； just one;
if prev is None and next is None:
self.head = None
self.tail = None
elif prev is None: #不是一个元素，且头部移除
self.head = next
self.tail = None
elif next is None: #不是一个元素，且尾部移除
self.tail = prev
prev.next = None
else: # 不是一个元素，且中间移除
prev.next = next
next.prev = prev
def iternodes(self,reverse=False):
current = self.tail if reverse else self.head
while current:
yield current
current = current.next if not reverse else current.prev
ll = LinkedList()
ll.append(1)
ll.append(2).append(3)
ll.insert(0,0)
ll.insert(0,'abc')
ll.insert(1000,'end')
#print(ll.pop())
for x in ll.iternodes():
print(x)
#------------------------------
< abc -->0>
< 0 -->1>
< 1 -->2>
< 2 -->3>
< 3 -->end>
< end -->None>
