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

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