链表

一种线性数据结构，每个元素对应链表上一个节点对象，每个节点通过地址(C/C++)或引用相连接，地址或引用记录下一个节点的内存地址，该元素可以通过地址或引用访问下一个元素

节点

链表的组成单位

包含两项数据：节点的值，下一个节点的引用

定义节点类

# 定义链表节点
class ListNode():
    def __init__(self, val):
        self.val = val
        self.next = None

链表常用操作初始化链表

在得到节点定义类后，即可初始化一条节点：

初始化链表后，通常将头结点作为链表的代表，通过引用可访问到每个节点

#实例化 
n0 = ListNode(0)
n1 = ListNode(1)
n2 = ListNode(2)
# 构建关系
n0.next = n1
n1.next = n2

n0.next.next.val

2

插入

链表插入节点相对容易，在相邻两个节点n0,n1之间插入一个新节点p，只需改变该两个节点引用的值即可，时间复杂度为O(1)

相比数组的插入时间复杂度为O(n),在大数据下方便许多

def insert(pre, current):
    temp = pre.next
    current.next = temp
    pre.next = current

n3 = ListNode(3)
insert(n0,n3)
n0.next.val

3

删除

链表删除节点也十分方便，只需要改变一个节点的引用

存在一个n0->n1->n2的链表，删除n1时，只需要将n0的引用指向n2，此时n0节点已经指针n2，访问不到n1，意味着n1不在属于该链表了

def delete(current):
    # 判断是否没有节点
    if not current.next:
        print('当前节点没有下一个节点了')
        return None
    temp = current.next
    current.next = temp.next

delete(n1)
print(type(n1.next))

<class 'NoneType'>

查找

一种线性查找，需要遍历链表

def find(head, target):
    """
    查找职位target的节点，返回索引
    """
    index = 0
    while head:
        if head.val == target:
            return index
        else:
            head = head.next
            index += 1
    print(f'未找到 {target} 所在未知')
    return -1

index = find(n0, 2)
index

未找到 2 所在未知
-1

index_3 = find(n0, 3)
index_3

1

访问

链表查找需要从头开始，一次向后遍历节点值，直到找到目标值，也就是说查找链表的第i个位置需要循环i-1轮，时间复杂度为O(n)

相比数组的下标，在O(1)时间内访问数组中任意元素，效率较低

def access(head, index):
    """
    访问第index个节点
    """
    for _ in range(index):
        # 节点不正确
        if not head:
            return None
        # 下一个
        head = head.next
    return head

access(n0, 2).val

1

链表VS数组链表数组

存储方式

分散内存空间

连续内存空间

容量扩展

可灵活扩展

长度不可变

内存效率

元素占用内存少、但可能浪费空间

元素占用内存多

访问元素

O(n)

O(1)

添加元素

O(1)

O(n)

删除元素

O(1)

O(n)