本文不涉及链表概念的详细讲解,而着重利用 python 实现链表,在其中穿插代码讲解。本文主要实现单向链表单向循环链表双向链表

其它数据结构:栈和队列二叉树

目录

  • 节点
  • 单向链表
  • 构造链表
  • 是否为空
  • 遍历链表
  • 获取长度
  • 插入元素
  • 尾部插入
  • 头部插入
  • 中间插入
  • 查找节点
  • 删除节点
  • 使用单向链表
  • 单向循环链表
  • 构造链表
  • 是否为空
  • 遍历链表
  • 链表长度
  • 插入元素
  • 尾部插入
  • 头部插入
  • 中间插入
  • 查找节点
  • 删除节点
  • 使用单向循环链表
  • 双向链表
  • 构造链表
  • 是否为空
  • 遍历链表
  • 获取长度
  • 插入元素
  • 尾部插入
  • 头部插入
  • 中间插入
  • 查找节点
  • 删除节点
  • 使用双向链表
  • 链表有多个节点,第一个节点称为头节点,最后一个节点称为尾节点。中间节点的前一个节点称为前驱节点,后一个节点称为后继节点。每个链表都有一个 head 指针,指向这个链表的头节点。链表可以获取其长度,也可以增加或删除节点,遍历节点。

    节点

    链表有若干个节点串联而成。对于单向链表而言,每个节点有两个区域,分别存放数据和后继节点。

    class Node():
        """节点,保存数据和后继节点"""
        def __init__(self, elem):
            self.elem = elem
            self.next = None
    

    在双向链表中,每个节点不仅指向后继节点,还可以指向前驱节点,因此节点中还有有个区域存放前驱节点。

    class Node():
        """双向链表节点"""
        def __init__(self, item):
            self.elem = item
            self.next = None
            self.pre = None
    

    单向链表

    单向链表只能从第一个节点开始向后搜索,直到最后一个结点。

    构造链表

    每个链表均有一个 head 值指向头节点;如果是空链表,则指向 None

    class Linklist():
        def __init__(self, node=None):
            self.__head = node
    

    是否为空

    如果 head 值指向 None,则说明是个空链表。

    def is_empty(self):
        """判断链表是否为空"""
        return self.__head == None
    

    遍历链表

    指针 cur 从指向头节点开始,沿着每个节点的 next 值指向后继节点,直至尾节点 next 指向 None

    def travel(self):
        """遍历链表"""
        cur = self.__head
    
        while cur != None:
            print(cur.elem)
            cur = cur.next
    

    获取长度

    要知道链表的长度就要遍历一遍链表,并记录下节点个数。

    def length(self):
        """返回链表长度"""
        cur = self.__head
        
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count
    

    插入元素

    尾部插入

    在尾部插入新的节点,只需要把最后一个节点的 next 区域改为新插入的节点,新插入节点的 next 区域指向 None

    def append(self, item):
        """尾部添加"""
        node = Node(item)   # 创建节点
    
        # 当链表为空时
        if self.is_empty():
            self.__head = node
        else:
            # 找到尾节点
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            
            # 指向新节点
            cur.next = node
    

    这里只需要传入值,在函数内构造节点。

    头部插入

    要在链表头部添加元素,则需要让 head 指向这个新节点,让新节点的 next 指向原有的头节点。

    def add(self, item):
        """在链表头部添加"""
        node = Node(item)
    
        node.next = self.__head
        self.__head = node
    

    中间插入

    指定新节点插入位置,让前驱节点的 next 指向新节点,让新节点的 next 指向原有节点的后继节点。

    def insert(self, pos, item):
        """在指定位置插入节点"""
        # 如果 pos < 0,则认为在头部插入
        if pos <= 0:
            self.add(item)
            # 如果 pos > length,则认为在尾部插入
        elif pos > self.length() - 1:
            self.append(item)
        else:
            pre = self.__head
            # 找到指定位置
            count = 0
            while count < pos - 1:
                count += 1
                pre = pre.next
    
            # 插入节点
            node = Node(item)
            node.next = pre.next
            pre.next = node
    

    查找节点

    输入一个数据,判断这个数据是否在链表之中,同样需要遍历链表。

    def search(self, item):
        """查找节点是否存在"""
        cur = self.__head
    
        while cur == None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
    
        return False
    

    删除节点

    给定一个值,从链表中删除第一个出现这个值的节点。找到即将删除节点的前驱节点,让其的 next 设置为要删除节点的后继节点。

    def remove(self, item):
        """删除节点"""
        cur = self.__head
    
        # 如果删除的节点是头节点
        if cur.elem == item:
            self.__head = cur.next
        else:
        	# 找到删除节点的前驱节点
            while cur.next.elem != item:
                cur = cur.next
    		cur.next = cur.next.next
    

    使用单向链表

    main 方法中对上述方法进行测试。

    if __name__ == '__main__':
        ll = Linklist()
        print(ll.is_empty())
        print(ll.length())
    
        ll.append(100)
        print(ll.is_empty())
        print(ll.length())
    
        ll.append(200)
        ll.append(300)
        print(ll.length())
        ll.travel()
    
        ll.add(-100)
        ll.travel()
    
        ll.insert(-1, -666)
        ll.insert(2, 123)
        ll.insert(10, 12345)
        ll.travel()
    
        print(ll.search(888))
        print(ll.search(123))
        
        ll.remove(-666)
        ll.travel()
        ll.remove(12345)
        ll.travel()
        ll.remove(123)
        ll.travel()
    

    单向循环链表

    单向循环链表与单链表十分相似,只不过单向循环链表的尾节点可以指向头节点,而不是指向 None

    构造链表

    在单向循环链表构造时,如果传入了一个节点,则该节点的 next 指向自己。

    class Cycle_Linklist():
        def __init__(self, node=None):
            """单向循环链表构造"""
            self.__head = node
            if node:
                node.next = node
    

    是否为空

    判断链表是否为空与单向链表相同,不再赘述。

    遍历链表

    单向循环链表中尾节点的 next 不再指向 None,而是指向头节点,遍历停止条件为指向头节点,单独考虑链表为空的情况。

    def travel(self):
        """遍历链表"""
        cur = self.__head
    
        if self.is_empty():
            print()
        else:
            while cur.next != self.__head:
                print(cur.elem, end=' ')
                cur = cur.next
            print(cur.elem)
    

    注意不要漏掉尾节点。

    链表长度

    计算链表长度同样需要遍历链表。

    def length(self):
        """返回链表长度"""
        cur = self.__head
    
        if self.is_empty():
            return 0
    
        count = 1
        while cur.next != self.__head:
            count += 1
            cur = cur.next
    
        return count
    

    插入元素

    尾部插入

    让原有的尾节点指向新节点,并让新节点的 next 指向头节点。

    def append(self, item):
        """尾部添加"""
        node = Node(item)   # 创建节点
    
        # 当链表为空时
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            # 找到尾节点
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            
            # 指向新节点
            cur.next = node
            node.next = self.__head
    

    头部插入

    从头部插入新节点,需要将 __head 指向新插入节点,同时把尾节点的 next 插入新节点,并把新节点的 next 指向原来的头节点。

    def add(self, item):
        """在链表头部添加"""
        node = Node(item)
    
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            # 找到尾节点
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
    
            cur.next = node
            node.next = self.__head
            self.__head = node
    

    中间插入

    在中间插入的情况与单向链表相同,不再赘述。

    查找节点

    查找节点同样需要遍历链表。

    def search(self, item):
        """查找节点是否存在"""
        cur = self.__head
    
        if self.is_empty():
            return False
    
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        if cur.elem == item:
            return True
    
        return False
    

    删除节点

    如果删除的节点不是头节点,则与单向链表相同;如果是头节点,则还需要把尾节点的 next 指向第二个节点。

    def remove(self, item):
        """删除节点"""
        cur = self.__head
    
        # 如果删除的节点是头节点
        if cur.elem == item:
            # 遍历找到最后一个节点
            tail = cur
            while tail.next != self.__head:
                tail = tail.next
            tail.next = cur.next
            self.__head = cur.next
        else:
            # 找到删除节点的前驱节点
            while cur.next.elem != item:
                cur = cur.next
            cur.next = cur.next.next
    

    使用单向循环链表

    单向循环链表的测试与单向链表相同,不再赘述。

    双向链表

    在双向链表中,每个节点不仅指向后继节点,还可以指向前驱节点。

    构造链表

    双向循环链表的初始化与单向链表相同,不再赘述。

    是否为空

    双向循环链表判断为空与单向链表相同,不再赘述。

    遍历链表

    双向链表的遍历可以按照单向链表遍历思路,不再赘述。

    获取长度

    获取双向链表的长度也可以按照单向链表遍历思路,不再赘述。

    插入元素

    尾部插入

    在尾部插入新节点,需要把新节点的 pre 指向原来链表的尾节点。

    def append(self, item):
        """尾部添加"""
        node = Node(item)   # 创建节点
    
        # 当链表为空时
        if self.is_empty():
            self.__head = node
        else:
            # 找到尾节点
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            
            cur.next = node
            node.pre = cur
    

    头部插入

    在头部插入新节点时,让新节点的 next 区域指向原来链表的头节点,原来链表的头节点指向新节点,head 也指向新节点。

    def add(self, item):
        """在链表头部添加"""
        node = Node(item)
    
        self.__head.pre = node
        node.next = self.__head
        self.__head = node
    

    中间插入

    除了进行单向链表的插入过程之外,还需要修改节点的 pre

    def insert(self, pos, item):
        """在指定位置插入节点"""
        # 如果 pos < 0,则认为在头部插入
        if pos <= 0:
            self.add(item)
            # 如果 pos > length,则认为在尾部插入
        elif pos > self.length() - 1:
            self.append(item)
        else:
            cur = self.__head
            # 找到指定位置
            count = 0
            while count < pos - 1:
                count += 1
                cur = cur.next
    
            # 插入节点
            node = Node(item)
            node.next = cur.next
            node.pre = cur
            cur.next = node
            node.next.pre = node
    

    查找节点

    双向链表查找元素与单向链表相同,不再赘述。

    删除节点

    不仅要修改删除节点的前驱节点的 next,单独考虑删除的节点是尾节点的情况,还要修改删除节点的后继节点的 pre

    def remove(self, item):
        """删除节点"""
        cur = self.__head
    
        # 如果删除的节点是头节点
        if cur.elem == item:
            self.__head = cur.next
            cur.next.pre = None
        else:
            # 找到删除节点的前驱节点
            while cur.next.elem != item:
                cur = cur.next
            
            # 如果要删除的节点不是尾节点
            if cur.next.next != None:
                cur.next.next.pre = cur
            cur.next = cur.next.next
    

    使用双向链表

    使用方法与单向链表相同,不再赘述。

    来源:笨蛋程序员

    物联沃分享整理
    物联沃-IOTWORD物联网 » python 实现链表

    发表评论