Python中有关链表的操作（经典面试内容）

超、凢脫俗 2022-05-20 09:11 183阅读 0赞

#### 1、创建一个链接 ####

node1 = Node("c",node3)
    或者
    node1 = Node("c",None)
    node1.next = node3

#### 2、用循环创建一个链表结构，并且访问其中的每一个节点 ####

class Node(object):
        def __init__(self, data, next=None):
            self.data = data
            self.next = next
    
    head = None
    for count in range(1,6):
        head = Node(count, head)
    while head != None:
        print(head.data)
        head = head.next

#### 3、遍历 ####

遍历使用一个临时的指针变量，这个变量先初始化为链表结构的head指针，然后控制一个循环。

probe = head
    while probe != None:
        probe = probe.next

#### 4、搜索 ####

有两个终止条件：

一、空链表，不再有要检查的数据。

二、目标项等于数据项，成功找到。

probe = head
    while probe != None and targetItem != probe.data:
        probe = probe.next
    if probe != None:
        print("target is found")
    else:
        print("target is not in this linked structure")

#### 5、访问链表中的第i（index）项 ####

probe = head
    while index > 0:
        probe = probe.next
        index -= 1
    print(probe.data)

#### 6、替换 ####

若目标项不存在，则返回False；否则替换相应的项，并返回True.

probe = head
    while probe != None and targetItem != probe.data:
        probe = probe.next
    if probe != None:
        probe.data = newItem
        return True
    else:
        return False

#### 7、在开始处插入 ####

head = Node(newItem, head)

#### 8、在末尾处插入 ####

在单链表末尾插入一项必须考虑两点：

一、head指针为None，此时，将head指针设置为新的节点

二、head不为None，此时代码将搜索最后一个节点，并将其next指针指向新的节点。

newNode = Node(newItem)
    if head is None:
        head = newItem
    else:
        probe = head
        while probe.next != None:
            probe = probe.next
        probe.next = newNode

#### 9、从开始处删除 ####

head = head.next

#### 10、从末尾删除 ####

需要考虑两种情况：

一、只有一个节点，head指针设置为None

二、在最后一个节点之前没有节点，只需要倒数第二个节点的next指向None即可。

if head.next is None:
        head = None
    else:
        probe = head
        while probe.next.next != None:
            probe = probe.next
        probe.next = None

#### 11、在任何位置插入 ####

需要考虑两种情况：

一、该节点的next指针为None。这意味着，i>=n，因此，应该将新的项放在链表结构的末尾。

二、该节点的next指针不为None，这意味着，0<i<n，因此需将新的项放在i-1和i之间。

if head is None or index <=0:
        head =Node(newItem, head)
    else:
        probe = head
        while index > 1 and probe.next != None:
            probe = probe.next
            index -= 1
        probe.next = Node(newItem, probe.next)

#### 12、在任意位置删除 ####

一、i<= 0——使用删除第一项的代码

二、0<i<n——搜索位于i-1位置的节点，删除其后面的节点

三、i>n——删除最后一个节点

if index <= 0 or head.next is None:
        head = head.next
    else:
        probe = head
        while index > 1 and probe.next.next != None:
            probe = probe.next
            index -= 1
        probe.next = probe.next.next

本文参考《数据结构（Python语言描述）》