链表(linked list)和二叉树(binary tree)基础知识回顾

    技术2025-07-15  9

    链表与数组相比的优缺点

    优点:链表中插入删除元素是非常迅速的,时间复杂度:O(1) 数组中插入元素往往需要挪动多次

    缺点:在访问元素的时候,链表需要O(n)的时间复杂度 数组中可以直接根据index访问到元素

    单向链表、双向链表和循环链表

    通过.next来访问下一个元素

    二叉树

    通过 .left.value、.right.value来访问子节点

    满二叉树(full binary tree)和完全二叉树(complete binary tree)

    满二叉树是完全二叉树的一种特殊情况

    二叉搜索数(BST binary search tree)

    左边的比当前结点小,右边的比当前结点大(注意:不能只检查局部,要遍历所有,需要有递归的思想)
    Processed: 0.013, SQL: 9