数据结构之单链表的插入和删除节点

上文介绍了单链表的几种创建方法，本文介绍另外两种操作：单链表插入节点和删除节点。需要特别注意的是插入操作的顺序问题。

代码示例

1、创建链表

class Node():

    def __init__(self, item, next=None):
        self.item = item
        self.next = next


def create_link_tail(lst):
    head = tail = Node(lst[0])
    for elem in lst[1:]:
        node = Node(elem)
        tail.next = node
        tail = node
    return head

def print_link(head):
    node = head
    while node:
        print(node.item, end=' ')
        node = node.next

head = create_link_tail([1, 2, 3])
print_link(head)

2、插入节点

def insert_link(head, idx, elem):
    cur_node = Node(elem)
    # 0号位置单独处理
    if idx == 0:
        cur_node.next = head
        head = cur_node
    else:
        node = head
        i = 0
        while node:
            if i == idx - 1:
                # 注意顺序
                cur_node.next = node.next
                node.next = cur_node
            i += 1
            node = node.next
    return head


head = insert_link(head, 0, 4)
head = insert_link(head, 1, 5)
print_link(head)

3、删除节点

def delete_link(head, idx):
    if head.next == None:
        print('empty link')
        return None
    elif idx == 0:
        head = head.next
    else:
        node = head
        i = 0
        while node:
            if i == idx - 1:
                node.next = node.next.next
                break
            i += 1
            node = node.next
    return head

head = delete_link(head, 0)
head = delete_link(head, 2)
print_link(head)