Python链表学习

链表对象的建立和循环输入输出

# 建立一个链表的类
class student:
    def __init__(self):
        self.name = ''
        self.next = None

# 首先建立一个头指针
head = student()
head.name = 'head' 

# 新建一个操作指针
ptr = head

# 新建若干个项，放在链表中
for i in range(5):
    ll = student()
    ll.name = str(input("loop {} of {}, please input names:".format(i+1,5)))
    ptr.next = ll
    ptr = ptr.next

依次输入如下：

loop 1 of 5, please input names:zhang yi
loop 2 of 5, please input names:zhou er
loop 3 of 5, please input names:shang san
loop 4 of 5, please input names:li si
loop 5 of 5, please input names:wang wu

# 打印链表
ptr = head
while ptr!= None:
    print(ptr.name)
    ptr = ptr.next

输入如下

head
zhang yi
zhou er
zhang san
li si
wang wu

在链表中插入一个节点

# 插入节点，首先需要查找，利用一个循环进行查找
# 在zhang yi 前面插入一个节点叫zero，在指定的Node前面插入newNode
def insertLinkList(insertedLinkList,newNode,Node):
#     首先要查找newNode的上一个节点
    head = insertedLinkList
    ptr = head
    while True:
        # 如果是在头结点上
        if insertedLinkList==None:
            # 直接放上去
            insertedLinkList = newNode
        else:
            if ptr.next.name== Node.name:
                # 说明找到了，用几个状态记录下来
                before = ptr
                current = ptr.next
                # 插入操作（改变链接）
                newNode.next = current
                before.next = newNode
                print("Ok")
                # 注意操作完毕之后要退出循环
                break
            else:
                ptr = ptr.next

# 执行插入                
newNode = student()
newNode.name = 'zero'
insertedLinkList = head
Node = head.next
insertLinkList(head,newNode,Node)    

# 打印输出观察
ptr = head
while ptr!= None:
    print(ptr.name)
    ptr = ptr.next

在显示OK之后，链表里面的内容变为：

head
zero
zhang yi
zhou er
zhang san
li si
wang wu

在链表中删除一个节点

# 删除节点
# 把刚才加入的节点删除掉
def deleteLinkList(toBeDeletedLinkList,toBeDeletedNode):
    head = toBeDeletedLinkList
    ptr = head
    while True:
        if ptr.next.name==toBeDeletedNode.name:
            before = ptr
            current = ptr.next
            after = ptr.next.next
            before.next = after
            print("Ok")
            break
        else:
            ptr = ptr.next

# 执行删除操作            
toBeDeletedNode = student()
toBeDeletedNode.name = 'zero'
deleteLinkList(head,toBeDeletedNode)

# 打印输出观察
ptr = head
while ptr!= None:
    print(ptr.name)
    ptr = ptr.next

可以发现zero又被删掉了

head
zhang yi
zhou er
zhang san
li si
wang wu

链表翻转

首先需要建立3个指针，ptr指向当前，before是之前，last是更之前，3个指针同时前进，然后用新的before指向last完成翻转，最后需要传回before！before是翻转之后的头结点。

# 链表翻转
def invertLinkList(toBeInvertedLinkList):
    head = toBeInvertedLinkList
    before = None
    ptr = head
    while ptr!=None:
        last = before
        before = ptr
        ptr = ptr.next
        before.next = last
    return before

head = invertLinkList(head)
# 打印输出观察
ptr = head
while ptr!= None:
    print(ptr.name)
    ptr = ptr.next

wang wu
li si
zhang san
zhou er
zhang yi
head