前言

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

链表是面试考察的一个重要部分，下面就介绍如何使用python定义一个单链表。

1. 定义一个节点类

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

2. 新建一个单链表的类

class SingleLink():
    def __init__(self):
        self.head = None # head 与 tail 都是Node类型的节点
        self.tail = None
        self.length = 0
        return

	# 链表是否为空
    def is_empty(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()