在链式存储结构上设计直接插入排序算法

链式存储结构上的直接插入排序算法可以使用以下步骤：

1. 创建一个新的链表，作为排序后的结果存储。

2. 遍历原始链表中的每个节点，将它插入到新链表中的正确位置。

3. 对于每个节点，从新链表的头节点开始遍历，直到找到它应该插入的位置。在遍历过程中，比较节点的值和当前节点的值，如果当前节点的值大于该节点的值，则将该节点插入到当前节点的前面。

4. 如果遍历到了新链表的末尾，说明该节点是最大的节点，将其插入到新链表的末尾。

5. 遍历完成后，新链表就是排好序的链表。

以下是代码实现：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insertion_sort(head):
    if not head or not head.next:
        return head

    new_head = Node(head.data)
    cur = head.next

    while cur:
        if cur.data < new_head.data:
            new_node = Node(cur.data)
            new_node.next = new_head
            new_head = new_node
        else:
            inner_cur = new_head
            while inner_cur.next and inner_cur.next.data < cur.data:
                inner_cur = inner_cur.next
            new_node = Node(cur.data)
            new_node.next = inner_cur.next
            inner_cur.next = new_node

        cur = cur.next

    return new_head

这个算法的时间复杂度为O(n^2)，因为它需要对每个节点进行遍历，并且需要将节点插入到新链表中的正确位置。然而，它的空间复杂度为O(n)，因为它需要创建一个新的链表来存储排序后的结果。