链表
-
相对于顺序表，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理且进行扩充时不需要进行数据搬迁。
-
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是每一个结点（数据存储单元）里存放下一个结点的信息（即地址）
构造一个链表
. is_empty()：链表是否为空
. length()：链表长度
. travel()：遍历整个链表
. add(item)：链表头部添加元素
. append(item)：链表尾部添加元素
. insert(pos, item)：指定位置添加元素
. remove(item)：删除节点
. search(item)：查找节点是否存在
class Node(): #节点的封装
def __init__(self,item):
self.item = item #节点存储的传来的数据
self.next = None #节点的指向，指向下一个节点（对象）
#链表的封装
class Link():
def __init__(self):#构建一个空链表
self._head = None #head永远指向链表中第一个节点。None表示空链表，还没有节点
#从头部添加数据（节点）
def add(self,item):
#每次都实例化一个新的节点对象
nd = Node(item)
nd.next =self._head
self._head = nd #将_head指向当前新节点
def travel(self):
#cur 指向了第一个节点
cur = self._head
while cur:
print(cur.item)
cur = cur.next #重新赋值第一个节点的next指向的下一个节点对象
def isEmpty(self):
return self._head == None
def length(self):#返回链表中节点的个数
cur = self._head
count = 0
while cur:
count += 1
cur = cur.next
return count
def append(self,item): #向链表尾部添加节点
nd = Node(item)
#如果链表为空
if self._head == None:
self._head = nd
#链表不为空
pre = None #设置pre是指向cur前面的一个节点。因为最后一个节点的next是none.
#none无法在next，只有找到最后一个对象，在next赋值新的节点对象
cur = self._head
while cur:
pre = cur
cur = cur.next
pre.next = nd
#当while循环结束的时候，pre就指向了链表中最后一个节点
def search(self,item):#查找item对应的节点是否存在
cur = self._head
find = False
while cur:
if cur.item == item:
find = True
break
else:
cur = cur.next
return find
def insert(self,post,item):#将item对应的节点插入到post指定的位置中
nd = Node(item)
cur = self._head
pre = None
#插入位置为0的情况
if post == 0:
nd.next = self._head
self._head = nd
return
#插入位置为非0的情况
for i in range(post):
pre = cur
cur = cur.next
pre.next = nd
nd.next = cur
def remove(self,item): #将item对应的节点删除
cur = self._head
pre = None
if self._head.item == item: #删除的节点是第一个节点。需要该链表指向
self._head = cur.next
return
else:
while cur:
if cur.item == item:
pre.next = cur.next
break
else:
pre = cur
cur =cur.next
l = Link()
l.add(1)
l.add(2)
l.add(3)
l.insert(0,5)
l.remove(3)
l.travel()
#
5
2
1
#补充def add(self,item):这个方法中，每次调用都会创建变量名为node这个对象，但是为什么重名不影响，因为他是局部变量。
局部命名空间是在函数被调用时创建的，函数参数会立即填入该命名空间。在函数执行完毕之后，局部命名空间就会被销毁，随之变量名也被垃圾回收机制收回。但是之前赋值的都是指向对象的空间地址而已。毫不影响
#再补充局部命名空间的问题。当你在局部使用全部变量可以， 但是如果你要修改全局变量得看你是什么数据类型。例如 全局定义a = 1 函数中 a= a+1 不可以报错 UnboundLocalError，因为a是不可变数据类型。当a =[1,2,3]
函数中 a.append(4) 修改了全局a中的内容是可以的
#总结：对于不可变类型的全局变量来说，因其指向的数据不能修改，所以不使用global时无法修改全局变量。
对于可变类型的全局变量来说，因其指向的数据可以修改，所以不使用global时也可修改全局变量。
链表倒置
def overturn(self):
if self._head == None:
return
cur = self._head
pre = None
cur1 = cur.next
while cur:
if cur1 !=None:
cur.next = pre
pre = cur
cur = cur1
cur1 = cur1.next
if cur1 == None:
cur.next = pre
break
self._head = cur
- 想法，定义三个变量.cur,pre,cur 用来相互转换。
- 下图是写链表倒置的逻辑图（自己画的有点丑）
