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

python 实现单向链表和双向链表

程序员文章站 2023-01-05 20:55:46
1. 单向链表的实现详细的链表讲解请参考:https://blog.csdn.net/weixin_42881588/article/details/107085047# 单向链表的实现# 链表节点class Node:# 构造函数# 通过传入数据构造新节点# 默认下一链接域为空,none def __init__(self, elem): self._elem = elem self._next = None# 链表类class SLin...

1. 单向链表的实现

详细的链表讲解请参考:https://blog.csdn.net/weixin_42881588/article/details/107086000

# 单向链表的实现

# 链表节点
class Node:
	# 构造函数
	# 通过传入数据构造新节点
	# 默认下一链接域为空,none
    def __init__(self, elem):
        self._elem = elem
        self._next = None

# 链表类
class SLink:
    # 创建空链表
	# 将链表头置为空,none
    def __init__(self):
        self._head = None
    
	# 判空
    def is_empty(self):
		# 根据初始化判断链表头是否为空即可
        return self._head == None
    
	# 遍历显示
    def show(self):
		# 获取第一个链表节点
        cur = self._head
		# 若节点为空时结束遍历
        while cur != None:
            print(cur._elem)
			# 将当前的节点后移一位
            cur = cur._next

    # 插入链表首部
    def add(self, elem):
        # 创建新结点
        tmp = Node(elem)
        # 新结点插入首部
        tmp._next = self._head
        # 更改链表首结点
        self._head = tmp

    # 删除链表中元素
    def delete(self, data):
        # 两个变量存放遍历时前后两个元素结点
        cur, pre = self._head, None
		# 查找标志位found
        found = False
        while not found and (cur != None):          
            if cur._elem == data:
                # 找到数据
				# 更改标志位found
                found = True
                if pre == None:
                    # 该节点是首结点
					# 更改链表头部,指向第二个节点
                    self._head = cur._next
					# 将要删除节点的下一链接域置空
                    cur._next = None
                else:
                    # 该节点是中间节点或尾结点
					# 将前一节点的下一链接域指向当前节点的下一节点
                    pre._next = cur._next
					# 将要删除节点的下一链接域置空
                    cur._next = None

            else:
                # 未找到数据
                # 遍历时结点指向
                pre = cur
                cur = cur._next
    # 长度
    def len(self):
        cur, num = self._head, 0
        while cur != None:
            num += 1
            cur = cur._next
        return num


# 自测 
if __name__ == "__main__":
    # 创建自己的链表
    mylink = SLink()
    # 插入数据
    mylink.add('Mary')
    mylink.add('Amy')
    mylink.add('Bob')
    mylink.show()
    print('-'*8)
    # 删除数据
    mylink.delete('Bob')
    mylink.show()
    print('-'*8)
    mylink.delete('Mary')
    mylink.show()
    print('-'*8)
    # 获取长度
    mylink.add('Marco')
    mylink.add('Sofi')
    mylink.delete('Amy')
    mylink.show()
    print('-'*8)
    print(mylink.len())

python 实现单向链表和双向链表
2. 双向链表的实现

# 双向链表的实现

# 链表节点
class Node:
	# 构造函数
	# 通过传入数据值构建链表节点
	# 默认前一链接域为空,none
	# 默认下一链接域为空,none
    def __init__(self, elem):
        self._elem = elem
        self._next = None
        self._prev = None

# 链表类
class DLink:
    # 创建空链表
    def __init__(self):
		# 将链表头部置空,none
        self._head = None

    # 判空
    def is_empty(self):
		# 判断链表头部是否为空即可
        return self._head == None

    # 遍历显示(从前到后遍历)
    def show(self):
		# 获取链表首节点
        cur = self._head
		# 若当前节点为空时结束遍历
        while cur != None:
            print(cur._elem)
			# 将当前节点后移一位
            cur = cur._next

    # 插入链表首部
    def add(self, elem):
        # 创建新结点
        tmp = Node(elem)
        if self.is_empty():
            # 空链表
            self._head = tmp
        else:
            # 非空链表
            cur = self._head
            tmp._next = cur
            cur._prev = tmp
            self._head = tmp
    # 删除链表中元素
    def delete(self, data):
        # 三个变量存放遍历时前中后元素结点
        cur, pre = self._head, None
        found = False
        while not found and (cur != None):          
            net = cur._next
            if cur._elem == data:
                found = True
                # 找到数据
                if pre == None:
                    # 该节点是首结点       
                    self._head = net
                    cur._next = None
                    net._prev = None                    
                elif net == None:
                    # 该结点是尾结点
                    cur._prev = None
                    pre._next = None
                else:
                    # 该节点是中间节点
                    pre._next = net
                    net._prev = pre
                    cur._next = None
                    cur._prev = None
            else:
                # 未找到数据
                # 遍历时结点指向
                pre = cur
                cur = cur._next

    # 长度
    def len(self):
        cur, num = self._head, 0
        while cur != None:
            num += 1
            cur = cur._next
        return num


# 自测 
if __name__ == "__main__":
    # 创建自己的链表
    mylink = DLink()
    # 插入数据
    mylink.add('Mary')
    mylink.add('Amy')
    mylink.add('Bob')
    mylink.show()
    print('-'*8)
    # 删除数据
    mylink.delete('Bob')
    mylink.show()
    print('-'*8)
    mylink.delete('Mary')
    mylink.show()
    print('-'*8)
    # 获取长度
    mylink.add('Marco')
    mylink.add('Sofi')
    mylink.delete('Amy')
    mylink.show()
    print('-'*8)
    print(mylink.len())

python 实现单向链表和双向链表

本文地址:https://blog.csdn.net/weixin_42881588/article/details/107086065