使用python定义单链表

朱雀 2022-09-09 11:53 139阅读 0赞

# 前言 #

*  文章来源：CSDN@LawsonAbs
 *  使用python定义一个单链表

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

class Node:
        def __init__(self,data):
            self.data = data # 数据
            self.next = None; # 下一个节点
            return 
        
        # 对下面这个函数还是有点儿疑问
        def has_value(self,value):
            if self.data == value:
                return True
            else:
                return False
    
    # 新建一个单链表的类
    class singlelink():
        def __init__(self):
            self.head = None # head 与 tail 都是Node类型的节点
            self.tail = None
            self.length = 0
            return
    	# 链表是否为空
        def isempty(self):
            return self.length == 0
        
        def add_node(self,item):
            if not isinstance(item,Node): # 如果不是Node型对象，那么就直接实例化一下
                item = Node(item)
            if self.head is None: # 如果当前这个链表没有头，那么设置为头
                self.head  = item
                self.tail = item; #头尾都是这个
            else: 
                self.tail.next = item
                self.tail = item # 始终记录tail 
            self.length += 1
            return 
    
        def insert_node(self,index,data):
            if self.isempty():
                print("this link is empty")
                return 
            if index < 0 or index >= self.length:
                print("error:out of index")
                return 
            item = Node(data)
            if index == 0:
                item.next = self.head
                self.head  = item
                self.length += 1
                return 
            j = 0   
            node = self.head
            prev = self.head
            while node.next and j < index:
                prev = node
                node = node.next
                j+=1
            if j==index:
                item._next = node
                prev._next = item
                self.length += 1
    
    
        def print_link(self):
            current_node = self.head
            while current_node is not None:
                print(current_node.data,end=' ')
                current_node = current_node.next
            return
    
    # 定义几个实例
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    
    # 定义一个单链表
    link = singlelink()
    
    # 将得到的实例放到链表中，链表中存储的是节点
    for node in [n1,n2,n3,n4]:
        link.add_node(node)
    # 调用链表的方法输出其中的值
    link.print_link()