Python 链表实现：基本操作与复杂度分析

这段代码实现了一个链表的基本操作，包括判空、建表、求长度、展示链表、查找位置、删除节点和插入节点等功能。

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


class LinkList(object):
    def __init__(self):
        self.head = Node()

    def empty(self):
        '判空'
        if self.head.next is None:
            return True
        else:
            return False

    def create(self, data=None):
        '头插法建表'
        node = Node(data)
        if self.length() >= 1:
            node.next = self.head.next
            self.head.next = node
        else:
            self.head.next = node

    def length(self):
        '求链表长度'
        p = self.head.next
        cnt = 0
        while p is not None:
            cnt += 1
            p = p.next
        return cnt

    def display(self):
        '展示链表'
        p = self.head.next
        while p is not None:
            print(p.data, end='  ')
            p = p.next

    def locating(self, data=None):
        '查找位置'
        p = self.head.next
        cnt = 0
        while p is not None:
            cnt += 1
            if data == p.data:
                return cnt
            p = p.next
        else:
            print('此人不在表内。')

    def delete(self, data=None):
        '删除结点'
        p = self.head
        while p is not None:
            if p.next.data == data:
                name = data
                p.next = p.next.next
                return name
            p = p.next
        else:
            print('此人不在表内。')

    def insert(self, data1=None, data2=None):
        '插入节点'
        node = Node(data2)
        p = self.head.next
        while p is not None:
            if p.data == data1:
                node.next = p.next
                p.next = node
                print('{}已插入{}后。'.format(data2, data1))
            p = p.next


L = LinkList()
name = input("输入人名(输入quit代表结束输入)：\n")
while not name == 'quit':
    L.create(name)
    name = input()

# 1
print('（1）学生姓名：', end='')
L.display()
print('学生人数：', L.length())

# 2
print('（2）宿舍长位置：', L.locating('尚焱'))

# 3
print('(3)')
L.insert('尚焱', '王晨鉴')
print(L.delete('尚焱'), '已删除。')
print('现在在这两个宿舍的学生：', end='')
L.display()

代码的时间复杂度如下：

• empty()：O(1)
• create()：O(1)
• length()：O(n)
• display()：O(n)
• locating()：O(n)
• delete()：O(n)
• insert()：O(n)

其中，n为链表的长度。

代码的空间复杂度为O(n)，其中n为链表的长度。因为需要存储链表中的每个节点的数据和指针，所以空间复杂度与链表的长度成正比。