欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

<学习笔记>链表(二)遍历+空+长度+尾部添加节点+节点查询+删除+定向插入(2020.7.25)

程序员文章站 2022-03-03 21:28:43
3.2 链表的遍历思路如下图:3.3 链表空思路:根据head是否为空,就可以知道链表是否为空3.4 链表长度思路:循环写入计数器做累加即可3.4 链表尾部插入节点思路:走到最后节点,让最后一个节点的next等于新加入的node即可特殊情况:链表为空则前面直接为0报错,需要进行判断......

3.2 链表的遍历

思路如下图:<学习笔记>链表(二)遍历+空+长度+尾部添加节点+节点查询+删除+定向插入(2020.7.25)

3.3 链表空

思路:根据head是否为空,就可以知道链表是否为空

3.4 链表长度

思路:循环写入计数器做累加即可

3.5 链表尾部插入节点

思路:走到最后节点,让最后一个节点的next等于新加入的node即可
<学习笔记>链表(二)遍历+空+长度+尾部添加节点+节点查询+删除+定向插入(2020.7.25)
特殊情况:链表为空则前面直接为0报错,需要进行判断

3.6 链表节点查询

思路:遍历所有节点并返回True or False。

3.7 链表定向插入

思路:假如向位置2插入节点,首先想到创建新节点,然后插入的新节点是在原位置1之后和原位置2之前。不用考虑向位置0添加节点,因为有add方法。
<学习笔记>链表(二)遍历+空+长度+尾部添加节点+节点查询+删除+定向插入(2020.7.25)

3.7 链表删除指定元素

思路:删除指定元素与定向插入思路基本一致,但是要注意一点,就是第一个节点的删除是个特例要单独写,判断第一个节点是否是要删除的那个,如果是那么self._head = cur.next。如果不是那么就进行下面的遍历,找到要删除的元素之后,让pre.next = cur.next即可。
<学习笔记>链表(二)遍历+空+长度+尾部添加节点+节点查询+删除+定向插入(2020.7.25)
链表代码如下:


# 节点
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