<学习笔记>链表(二)遍历+空+长度+尾部添加节点+节点查询+删除+定向插入(2020.7.25)
程序员文章站
2022-03-03 21:28:43
3.2 链表的遍历思路如下图:3.3 链表空思路:根据head是否为空,就可以知道链表是否为空3.4 链表长度思路:循环写入计数器做累加即可3.4 链表尾部插入节点思路:走到最后节点,让最后一个节点的next等于新加入的node即可特殊情况:链表为空则前面直接为0报错,需要进行判断......
3.2 链表的遍历
思路如下图:
3.3 链表空
思路:根据head是否为空,就可以知道链表是否为空
3.4 链表长度
思路:循环写入计数器做累加即可
3.5 链表尾部插入节点
思路:走到最后节点,让最后一个节点的next等于新加入的node即可
特殊情况:链表为空则前面直接为0报错,需要进行判断
3.6 链表节点查询
思路:遍历所有节点并返回True or False。
3.7 链表定向插入
思路:假如向位置2插入节点,首先想到创建新节点,然后插入的新节点是在原位置1之后和原位置2之前。不用考虑向位置0添加节点,因为有add方法。
3.7 链表删除指定元素
思路:删除指定元素与定向插入思路基本一致,但是要注意一点,就是第一个节点的删除是个特例要单独写,判断第一个节点是否是要删除的那个,如果是那么self._head = cur.next。如果不是那么就进行下面的遍历,找到要删除的元素之后,让pre.next = cur.next即可。
链表代码如下:
# 节点
class Node():
def __init__(self, item):
self.items = item # 存储当前节点数据
self.next = None # 下一个节点信息(地址) 刚开始没有next
# 链表
class Link():
def __init__(self):
self._head = None # 初始化一个空链表 head用于记录第一个节点的地址
# 向链表的头部添加元素
def add(self, item):
# 创建一个新的节点
node = Node(item)
# 让新加入的节点next地址 == _head连接原来的节点地址,使新节点next得到连接
node.next = self._head
# node ==> 变量 ==> 内存空间地址
self._head = node
# 这一部分一直在改变指向,如果一个引用或者变量表示某一内存空间地址
# 那么这个引用或变量就指向了内存空间
def travel(self):
# _head在链表创建好之后一定是不可边得
cur = self._head
while cur:
print(cur.items)
cur = cur.next
def isEmpty(self):
return self._head == None
def size(self):
cur = self._head
count = 0
while cur:
count += 1
cur = cur.next
return count
def append(self, item):
node = Node(item)
# 特殊情况:链表为空则前面直接为0报错,在此判断
if self._head == None:
self._head = node
return
cur = self._head
pre = None # 第一个节点之前肯定为None
while cur:
pre = cur # 这样我们就可以取到none之前的节点了
cur = cur.next
# 当cur.next=None时候 不能直接赋给新加入的节点即不能循环结束后cur.next=node应该是前一个
pre.next = node
def search(self, item):
cur = self._head
find = False
while cur:
if cur.items == item:
find = True
break
cur = cur.next
return find
def insert(self, pos, item):
node = Node(item)
cur = self._head
pre = None
for i in range(pos):
pre = cur
cur = cur.next
pre.next = node
node.next = cur
def remove(self, item):
cur = self._head
pre = None
# 特例删除第一个节点
if cur.items == item:
self._head = cur.next
return
while cur:
pre = cur
cur = cur.next
if cur.items == item:
pre.next = cur.next
return
link = Link()
link.add(3)
link.add(9)
link.add(5)
link.append(9)
link.insert(4, 2)
link.remove(9)
link.travel()
print(link.isEmpty())
print(link.size())
print(link.search(1))
本文地址:https://blog.csdn.net/qq_45363979/article/details/107562864