[数据结构与算法]py单链表头插法与尾插法实现(含代码测试)

本博文源于《程序设计竞赛入门》，主要针对单链表头插法和尾插法的思想进行理解与代码演示。

一、实验原题–请实现单链表的头插法与尾插法

实验输入：输入创建链表节点个数，并分别输入其中的Data，最后输出
实验输入输出

Input:
3 2 5 3

Output:
2 5 3
3 5 2

实现效果:

二、头插法实现原理及代码

2.1 头插法思想

头插法的含义是指，新节点链接到头结点之后，第一个数据结点之前，所得链表为逆序链表。

• 建立一个空链表，仅包含一个头结点由头指针head指向，其数据域为-1，指针域为空值。
• 将新结点由指针p指向，并把结点链接到第一个数据结点
• 重复第二步，直到所有数据结点都插入到链表中。

2.2 头插法代码

def createByFront(a):
    head = Node(-1)
    for i in range(len(a)):
        p = Node(a[i])
        p.next = head.next
        head.next = p
    return head

2.3 尾插法思想

尾插法就是将新结点接到尾之后，所得链表称为顺序链表。

• 建立一个空链表，仅包含一个头结点由头指针head指向，其数据域为-1，指针域为None，同时该结点用一个尾指针tail指向

• 将申请新结点由指针p指向并链接到尾指针tail所指结点之后

• 把指针p指向的新结点置为新的尾结点

2.4 尾插法代码

def createByTail(a):
    head = Node(-1)
    tail = head
    for i in range(len(a)):
        p = Node(a[i])
        tail.next = p
        tail = p
    return head

三、完整代码

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

def createByTail(a):
    head = Node(-1)
    tail = head
    for i in range(len(a)):
        p = Node(a[i])
        tail.next = p
        tail = p
    return head



def createByFront(a):
    head = Node(-1)
    for i in range(len(a)):
        p = Node(a[i])
        p.next = head.next
        head.next = p
    return head


def output(head):
    p = head.next
    while p!= None:
        if p!=head.next:
            print(' ',end='')
        print(p.data,end='')

        p = p.next
    print()


if __name__ == '__main__':
    a = list(map(int,input().split()))
    n = a[0]
    a = a[1:]
    h = createByTail(a)
    output(h)
    h = createByFront(a)
    output(h)

四、总结与反思

在头插法与尾插法中，头插法讲究的是将新结点连接在头结点之后，第一个数据点之前。逆序输出。尾插法讲究的是链接到尾结点之后，所得链表称为顺序链表。因此，紧扣住定义，将代码多次演练即可掌握，实在是不可多得的好文章。