算法之链表【Python实现】

我不是女神ヾ 2023-09-29 19:31 15阅读 0赞

单链表又称单向链表，顾名思义它只有一个方向。单链表每个节点包含两个域：

*  信息域：又称元素域，存储数据用
 *  链接域：指向下一个节点地址，最后一个节点链接域指向 `None`
 *  变量 `p` 指向链表的头节点（首节点）的位置，从 `p` 出发能找到表中的任意节点

![f83c700ca7a03b0514501ca0444ad32e.png][]

class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
    
    
    class SingleListList:
        def __init__(self):
            self.__head = None  # 头节点
    
        def is_empty(self):
            return self.__head == None
    
        def length(self):
            cur = self.__head  # 游标
            count = 0
    
            # 尾节点指向 None，当不为 None 时说明还没到尾部
            while cur != None:
                count += 1
                cur = cur.next  # 游标移动
    
            return count
    
        def travel(self):
            """
            循环遍历
            :return:
            """
            cur = self.__head
            while cur != None:
                print(cur.val, end=" ")
                cur = cur.next  # 指针（或游标）不断向后移动
    
    
        def append(self, item):
            """
            尾部添加元素
            :param item:
            :return:
            """
            node = ListNode(item)  # 先创建一个保存item值的节点
    
            # 若链表为空，将 p 指向新节点
            if self.is_empty():
                self.__head = node
            else:
                # 若不为空，则找到尾部，将尾节点的next指向新节点
                cur = self.__head
                while cur.next != None:
                    cur = cur.next
    
                cur.next = node
    
        def search(self, item):
            cur = self.__head
            while cur != None:
                if cur.val == item:
                    return True
                cur = cur.next
            return False
    
        
    if __name__ == '__main__':
        ll = SingleListList()
        ll.add(1)
        ll.add(2)
        print(f"长度：{
          ll.length()}")
        ll.append(3)
        ll.append(4)
        ll.travel()
    
        print(ll.search(5))
        ll.add(5)
        ll.remove(5)
        print(f"长度：{
          ll.length()}")
    
        ll.insert(1, 6)
        ll.travel()

**头部添加元素**

![1f3200fd842398d5c0e2b7ee50424333.png][]

def add(self, item):
        """
        头部添加元素
        :param item:
        :return:
         """
        node = ListNode(item)  # 先创建一个保存item值的节点
        # 新节点的 next 链接域指向头结点 p
        node.next = self.__head
    
        # 头结点 p 指向新节点
        self.__head = node

--------------------

**指定位置插入**

![feae7c801579bb7cc1821e7566087a62.png][]

def insert(self, pos, item):
            """
            指定位置添加元素
            :param pos:
            :param item:
            :return:
            """
            if pos <= 0:
                # 在第一个元素之前，则执行 add
                self.add(item)
            elif pos > (self.length() - 1):
                # pos 大于长度，则 append
                self.append(item)
            else:
                # 指定位置插入
                node = ListNode(item)
                count = 0
                pre = self.__head   # pre 指向指定位置 pos 的前一个位置 pos-1，初始从头结点到指定位置
    
                while count < (pos - 1):
                    count += 1
                    pre = pre.next
    
                # 先将新节点的 next 指向插入位置的节点
                node.next = pre.next
    
                # 将插入位置的前一个节点的 next  指向新节点
                pre.next = node

--------------------

**删除节点**

![b28671488aaed66d23d913a1d1886b77.png][]

def remove(self, item):
        """
            删除节点
            :param item:
            :return:
            """
        cur = self.__head
        pre = None  # 虚拟头结点
    
        while cur != None:
            if cur.val == item:
                # 如果第一个就是删除的节点
                if not pre:
                    self.__head = cur.next  # 将头指针指向头节点的后一个节点
                    else:
                        # 将删除位置前一个节点的next指向删除位置的后一个节点
                        pre.next = cur.next
                        break
                else:
                    pre = cur
                    cur = cur.next

> 总结

*  节点移动：当前节点（游标）指向下一个节点，`cur = cur.next`
 *  删除节点：当前节点的前一个节点的 `next` 执行当前节点的后一个节点 `pre.next = cur.next`

[f83c700ca7a03b0514501ca0444ad32e.png]: https://img-blog.csdnimg.cn/img_convert/f83c700ca7a03b0514501ca0444ad32e.png
[1f3200fd842398d5c0e2b7ee50424333.png]: https://img-blog.csdnimg.cn/img_convert/1f3200fd842398d5c0e2b7ee50424333.png
[feae7c801579bb7cc1821e7566087a62.png]: https://img-blog.csdnimg.cn/img_convert/feae7c801579bb7cc1821e7566087a62.png
[b28671488aaed66d23d913a1d1886b77.png]: https://img-blog.csdnimg.cn/img_convert/b28671488aaed66d23d913a1d1886b77.png