两段Python链表实现代码辨析：哪种符合标准单向链表结构？

你有两段单向链表实现代码，运行后得到不同输出，想确认哪种符合标准单向链表结构（Head指向首节点，依次到尾节点指向Null，且认为6应成为新的头节点），以下是具体分析：

第一段代码：尾插法实现 #

链表实现代码 #

class node :
 def __init__(self,data=None):
    self.data = data  # Assign data
    self.next = None  # Initialize
class linked_list :
 def __init__(self):
    self.head = node()
 def append(self,data):
    new_node = node(data)
    cur = self.head
    while cur.next!= None :
         cur = cur.next
    cur.next = new_node
 def display(self):
    elements = []
    cur_node = self.head
    while cur_node.next !=None:
        cur_node = cur_node.next
        elements.append(cur_node.data)
    print(elements)

调用示例 #

mylist = linked_list() #initialize linked list
mylist.append(3) #appending elements
mylist.append(4) #appending elements
mylist.append(5) #appending elements
mylist.append(6) #appending elements
mylist.display() #calling display 

运行输出 #

[3,4,5,6]

第二段代码：头插法实现 #

链表实现代码 #

class linkedListNode :
 def __init__(self,data= None):
    self.data = data
    self.nextNode = None
class linkedList:
 def __init__(self):
    self.head = linkedListNode()
 def addNode(self,data):
    newNode = linkedListNode(data)
    if not self.head :
        self.head = newNode
    else :
        newNode.nextNode = self.head
        self.head = newNode
 def displayList(self):
    elements = []
    cursor = self.head
    while cursor.nextNode!=None:
        elements.append(cursor.data)
        cursor = cursor.nextNode
    return elements

调用示例 #

mylist = linkedList()
mylist.addNode(3)  
mylist.addNode(4)   
mylist.addNode(5)  
mylist.addNode(6)  
myLinkedListElements = mylist.displayList() 
print(myLinkedListElements)

运行输出 #

[6,5,4,3]

分析与结论 #

两种实现都是合法的单向链表结构，核心区别在于插入策略：

• 第一段采用尾插法：每次将新节点添加到链表尾部，最终链表结构为：哑头节点 -> 3 -> 4 -> 5 -> 6 -> Null，输出顺序与插入顺序一致，适合需要保留插入顺序的场景。
• 第二段采用头插法：每次将新节点设为新的头节点，最终链表结构为：6（头节点） -> 5 -> 4 -> 3 -> 哑节点 -> Null，输出顺序与插入顺序相反，完全符合你“6成为新头节点”的需求。

标准单向链表并没有强制要求插入方式，只要满足“节点依次指向，尾节点指向Null”的结构即可。如果你需要新节点成为头节点，第二段的头插法实现就是符合要求的选择。

内容的提问来源于stack exchange，提问作者Neelanjoy B