标准LinkedList中“增删改查”的时间复杂度

一、标准LinkedList

List 是一个接口，用来表示线性表，线性表中又有顺序表和链表

        //创建顺序表
        List<String> list = new ArrayList<>();
        //创建链表
        List<String> linkedList = new LinkedList<>();

二、增

• 2.1 尾插

如果是单链表，尾插需要先找到尾结点。标准库中标的链表是双向带环、首尾相接的链表；除此之外还有一种典型的链表是可以记录,链表的尾部，链表不带环。

综上所述：链表尾插的时间复杂度是O(1)

        linkedList.add("hello");

• 2.2中间插入

按照下标取元素，依赖于“随机访问能力”，对于数组和顺序表，是支持“随机访问”,但是对于链表，需要先找到下标对应的节点，再插入元素。

故对于链表中间元素插入的操作时间复杂度是O(N)

        linkedList.add(10,"java");

三、删

删除元素：无论是按照下标删除还是按照值删除，都需要先遍历链表找到要删除的节点

因此删除操作的时间复杂度是O(N)

        linkedList.remove("java");

四、改

修改元素：链表修改元素首先需要遍历链表找到目标下标，再修改目标元素

故其时间复杂度是O(N)

        linkedList.set(10,"C++");

五、查

查找元素

链表无论那种查找方式，都需要先遍历链表，故标准库LinkedList查找

操作的时间复杂度是O(N)

• 5.1 按值查找

        linkedList.indexOf("java");

• 5.2 按下标查找

        linkedList.get(10);