"""
单链表
. add(item)：链表头部添加元素
. is_empty()：链表是否为空
. length()：链表长度
. travel()：遍历整个链表
. append(item)：链表尾部添加元素
. insert(pos, item)：指定位置添加元素
. search(item)：查找节点是否存在
. remove(item)：删除节点 # 删除的最后的元素
. pop(): 删除最后一个元素
"""
class Node:
def init(self, item):
self.item = item # 值
self.next = None # 为了规定最后一个是None
# def __str__(self):
# return f'item:{self.item}'
class Link:
def init(self):
# 初始化一个空链表
self._head = None # ~=地址
def add(self, item):
node = Node(item) # node = 1 l.next = None l._head = 1 node = 2 l.next = 1 l._head = 2
node.next = self._head # a.next = None self._head = a.node b.next = a.node self._head = b.node
self._head = node # E10
# if self.next != None:
# print('self.next', self.next.item) # DD8
# print('self._head', self._head.item)
# print('self._head.next', self._head.next)
def is_empty(self):
return self._head == None
def length(self):
cur = self._head # 2
count = 0
while cur != None: #
# print(cur)
cur = cur.next
if cur != None:
# print('cur.item', cur.item)
pass
count += 1
return count # 因为这里需要多次使用,所以不方便print,而是返回值
def travel(self):
cur = self._head
for i in range(self.length()):
print(cur.item, end=' ')
cur = cur.next
print()
def append(self, item):
cur = self._head
pre = None
node = Node(item)
for i in range(self.length()):
pre = cur
cur = cur.next # 为什么cur = node 不行呢 per = cur 啊 ?
# pre的指向链 而不是 cur了 , 所以cur的指向链是下一个的指向链,不是地址node的
pre.next = node # 最后的Node()是写好了关联了None , 所以控制没添加之前的 最后一个就行了
def insert(self, pos, item):
if pos < 0 or pos > self.length():
print('insert插入的索引 超出范围了')
return
cur = self._head
pre = None
node = Node(item)
for i in range(pos):
pre = cur # 上一个
cur = cur.next # 现在的
pre.next = node # 之前的连接等于现在的节点
node.next = cur.next # 现在的下一个节点是之前的连接
# 现在的链表的
def remove(self, item):
pre = None
cur = self._head
if self._head == None:
return
if self._head.item == item:
self._head = cur.next
return
for i in range(self.length()):
if cur.item == item:
pre.next = cur.next
return
pre = cur
cur = cur.next # 现在的
print('链表中没有此值,无法删除')
def search(self, item):
pre = None
cur = self._head
find = False
for i in range(self.length()):
if cur.item == item:
find = True
pre = cur
cur = cur.next # 现在的
return find
def pop(self): # 删除最后一个
if self._head == None or self.length() == 1:
self._head = None
return
cur = self._head # 1
pre = None
for i in range(1, self.length()): # length = 5
pre = cur # 1, 2, 3 ,4
cur = cur.next # 2, 3, 4 ,5
pre.next = None # 4 后面没了! 也对, 不能循环5 次,就是没变化的
print(Node(2))
l = Link()
l.add(1)
l.add(2)
l.add(3)
l.add(4)
l.travel()
print(l.add(3))
print(l.is_empty())
l.travel()
print(l.length())
print(l.length())
print(l.length())
l.append(1)
l.append(2)
l.append(3)
l.append(4)
l.travel()
print(l.length())
l.insert(2, 6.5)
l.insert(-1, 6.5)
l.remove(9)
l.travel()
l.remove(9)
l.remove(9.4)
l.remove(3)
l.remove(1)
l.remove(6.5)
l.remove(4)
l.travel()
l.travel()
l.remove(4) # 测试,发现诸多问题, 比如,空了的话,给个判断条件,如果为空了直接返回
# 比如,删除成功了之后,return 跳出函数不要走别的逻辑了,而break 只是跳出当前循环,所以还是有差别的
# 基本都是基于for实现,但是实现的细节有所不同,需要测试处理.
l.pop()
l.pop()
l.pop()
l.pop()
l.pop()
l.travel()
print(l.search(2))
print(l.search(3))
for i in range(1, 5):
print(i)
'''
链表的逆置 : 不是,是有了,给他倒过来
'''
4 -> 3 -> 2 -> 1 -> None
4 <- 3 <- 2 <- 1 <- None
1 -> 2 -> 3 -> 4 -> None
node = Node(item) # 反过来
node.per = self._head
self._botton = node
反过来, a next -> b a <- b
class Node2:
def init(self, item):
self.item = item
self.prev = None
class Link2:
def init(self):
self._tail = None
def add(self, item):
cur = self._tail
while cur != None:
cur = cur.prev
node = Node(item) # 1 前面是2 2 前面是3 1 在最后那样 None -> 4 -> 3 -> 2 -> 1
node.prev = self._tail # 之前的是None 1 -> 2 -> 3 -> 4
self._tail = node # 尾 又等于了1, 2 , 3 # 1 之前的是None , 2之前的就化成了1 最后这个是最上面的值
# prev = None -> 1 -> 2 -> 3 -> 4
# tail 是最后添加的值
def is_empty(self):
return self._tail == None
def length(self):
cur = self._tail
count = 0
while cur != None:
count += 1
cur = cur.prev
return count
def travel(self):
cur = self._tail
for i in range(l2.length()):
print(cur.item, end=' ')
cur = cur.prev
l2 = Link2()
l2.add(1)
l2.add(2)
l2.add(3)
print(l2._tail.item)
print(l2.length())
l2.travel()