Linked List Insertion vs. BST Insertion Time Costs

Question

In a Linked List, insertion is O(1) because we assume that we already know where we want to insert. In a binary search tree, insertion is O(logN) because we have to find where to insert before we insert (however, the actual insertion process should be constant time). Why is it that in LinkedList's case we assume we already have the location, whereas in BST we assume we must traverse the nodes to find the insertion location (causing the time complexity to be O(logN)?

Answer 1

When insertion to linked list is considered, it is mainly assumed that the list does not have an order that should be maintained during an insertion. (i.e. the elements of the list are not ordered in a certain way) Hence, the cost of the insertion is considered to be the cheapest that can be achieved. After all, we, as you put it, don't care how the elements are ordered once we are done with the insertion. In that spirit, just adding the new node to the head of the list works, and that operation has O(1) time complexity, as you too have said.

In binary search tree(BST), however, the data structure has a predefined order. Thus, when we are talking about an insertion, where to insert is defined by the definition of BST itself.

Note that the complexity of insertion to BST depends on how balanced the tree is, and insertion to an unbalanced BST may have a different average time complexity than O(logN). (See here for an explanation) However, for the scope of your question, how balanced a BST is not that relevant. The key notion is that the difference in complexity is a result of an order being mandated by the definition of BST.

Consequently, for a BST with N nodes, it would take more than O(1) time to find that specific location dictated by the tree structure specified in the definition of BST. Whereas in the definition of a generic linked list, there are no such specific conditions regarding the inner structure of the individual elements. So, unless we are talking about a list that is ordered in a certain way or we are specified that we have to insert to the tail of the list (and have only a pointer to the head) any spot to insert the new node is deemed acceptable in a linked list, at least when the performance of the linked list data structure is analyzed.

Answer 2

The basic idea behind binary search tree is to have such a storing repository that provides the efficient way of data sorting, searching and retrieval. Searching in a BST has O(h) worst-case run time complexity, where h is the height of the given tree. Binary search tree with n nodes has a minimum of O(log n) levels, it takes at least O(log n) comparisons to find a particular position to insert. Unfortunately, a binary search tree can degenerate to a linked list, reducing the search time to O(n). In linked list, if you don't care about any order, you can insert element in O(1) time, but if you are traversing a linked list which is not good idea, then it would take o(n) time.

Answer 3

Finding a spot in a BST only takes O(log N) time if the tree is balanced, and if we're maintaining the tree in balance then the insert operation also takes O(log N) time, even after you know where to insert.

So... for a practical BST, like a red-black tree or an AVL tree, we can just say that insert takes O(log N) time, and it doesn't matter whether or not we include the cost of finding a place to insert.

For linked lists, you need to be specific - O(1) time to insert at the beginning or end, or after a node that you already have a pointer to, or O(N) time if you have to scan the list to find a position. We don't assume that we already know the position, we determine the complexity of the operation(s) we're actually interested in.

In real life, it's not usually a good idea to scan through a linked list to find a place to insert, because it takes O(N) time. We just don't do that, so we don't talk about it much. The appropriate use cases for linked lists almost always involve constant-time insertions.

Answer 4

You're comparing apples with oranges.

A linked list has no necessary order. You might well want to order the list by your own criterion. Insertion is O(1) if you don't care about order (just insert to the front), or if you care about order and already have a pointer to the insert position (which is pretty common, e.g. we have a linked list of lines in a text object, and a pointer to the current cursor position. User presses paste, and we insert lines).

With a BST, the elements are kept in an order, and you must define an ordering for them. Insertion is always O(log N) because you do a search on the insert position. Since the tree is roughly balanced, half the leaves are left children and half are right children of every node, so we quickly get to the leaf insert point.