O(1) for insertion onto a Linkedlist

[DrJones]

I have seen that it is stated a lot of places that Time complexity for insertion for an linked list is constant which doesn't make sense to me.

I would say it is O(N) since it has to through
the whole to find an empty one... could clarify why this isn't the reason??

[ResidentBiscuit]

Sometimes people say finding the node to insert to is considered another operation, which is O(n). Once you have a pointer to that node, though, inserting is obviously O(1).

I don't agree with this view and believe an insert(i, node) function is O(n). I have not seen a good argument to convince me that finding the ith node should be considered a separate operation.

[MiiNiPaa]

Still even then it O(n) for list would be better than almost anything — like O(n2) for vector — if you need to insert element before another element meeting criteria. Like x.insert(find(x.begin(), x.end(), functor()), some_value);.

List is almost never used, because it has very specific pros, which almost never matters.

[Duthomhas]

In the general case, an insert is O(N), for the reasons you give.

The trick is that often enough when working with a linked list we already have a pointer/iterator to the place where we want to insert something. So then the insertion becomes O(1), since we don't actually have to search the list to find the insertion point.

It's one of those vocabulary problems I complain about a lot. Saying O(N) or O(1) depends entirely on the way you are handling the list. Some insertions are linear, some are constant.

Hope this helps.

[Lowest0ne]

There are many use cases for the linked list, but the typical case is that insertion happens to the front:

struct Node
{
  Node* next;

  Node( Node* n ): next( n ){}
};

struct List
{
  Node *head;

  void insert( void )
  {
    head = new Node( head );
  }
};

If you want to insert at the end of the list, then you should keep track of the tail:

struct List
{
  Node *head;
  Node *tail;

  void insert()
  {
    if ( !head )
    {
      head = new Node();
    }
    else if ( !tail )
    {
      tail = new Node();
      head->next = tail;
    }
    else
    {
        tail->next = new Node();
    }
  }
}

Insertion in the middle of the list does add linear time complexity ( if the list is sorted you can reduce the comparisons to log(N) ).

[MiiNiPaa]

but the typical case is that insertion happens to the front

deque? Even vector often beats list on random insert (+search) speed.

List is good if you have large amount of big data classes with costly copy and move constructors and if you need to insert elements in the middle often. This is fairly rare occurence.

Another plus of the list is that element insert/removal is fairly easy to make thread safe and it will not block operations with other nodes.

http://baptiste-wicht.com/posts/2012/11/cpp-benchmark-vector-vs-list.html
http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

if the list is sorted you can reduce the comparisons to log(N)

No. You are apparently referring to the binary search? Well, list does not have random access, so the cost of getting middle element is still linear, and average cost of finding needed element equals to n/2 +n/4 +... = n

[helios]

But the number of comparisons (not of operations) does grow at log n, assuming you know the size ahead of time. This may be relevant for non-trivial comparisons.

[LB]

You would have to try pretty hard to make a move constructor slow enough to make a std::list faster than a std::vector for typical uses of lists. For me, the most common use case is an initial spurt of adding elements to the end (a reserve() can mitigate resizes) and then after that, frequent iteration and not-so-frequent additions and removals (effectively the inverse of what a linked list is good for).

I think the real killer is iteration. For me, iteration is the most frequent thing that happens, whereas insertions and removals are comparatively rare.

[mpauna]

One thing which the OP didn't specify is if he was interested in the generic linked list data structure or in std::list and std::forward_list. For the standard containers, the complexity is actually shown in the description of each method.

I think the real killer is iteration. For me, iteration is the most frequent thing that happens, whereas insertions and removals are comparatively rare.

And this is why complexity is broken down into individual operations. If I am creating a stack or queue, I am interested in the complexity for insertions and removals, not iterations or searches or "random insertion".

If linked-list insertion complexity was a linear O(n) because it included an unnecessary search complexity as the OP wondered about, that would be misleading.

Of course, for a sorted linked-list insertion, complexity would be linear because you simply can't insert a random item into a sorted linked-list without searching for a valid insertion point which would not break the sorted pattern.


Standard disclaimer for all things performance related ... complexity is only one factor affecting performance. Measure first, optimize later. Overhead may overwhelm complexity on smaller data sets. Thread safety, memory allocation, caching, spatiality, predictability, etc. may all affect performance.

[Z e r e o]

For me, the most common use case is an initial spurt of adding elements to the end (a reserve() can mitigate resizes) and then after that, frequent iteration and not-so-frequent additions and removals (effectively the inverse of what a linked list is good for).

Specially when you consider that removal from a vector can be O(1) also if you aren't concerned with ordering.

std::vector<int> vec = {1, 2, 3, 4, 5};
	
// O(1) removal
vec[1] = std::move(vec.back());
vec.pop_back();

Not saying that std::vector is the best for everything, but generally it is a good place to start looking. Though of course std::list does have cases where it would be better as does every container type.

[htirwin]

I would say it is O(N) since it has to through
the whole to find an empty one... could clarify why this isn't the reason??

There's no such thing as an empty one when it comes to linked lists.

[JLBorges]

std::list<> has two properties which makes it a requisite in some contexts.

a. std::list<> is the only sequence container that provides a strong exception-safety guarantee for modifiers.

b. std::list<> is the only sequence container where modifiers do not invalidate iterators, references and pointers to other elements.

If insert/erase in the middle is the most frequent operation (this is not really a common use-case for sequence containers), std::list<> would be the sequence container of choice.

#include <iostream>
#include <vector>
#include <list>
#include <numeric>
#include <ctime>
#include <cassert>

template< typename CONTAINER > std::clock_t geminate( CONTAINER& cntr )
{
    const auto start = std::clock() ;
    for( auto iter = cntr.begin() ; iter != cntr.end() ; ++iter, ++iter )
        iter = cntr.insert( iter, *iter ) ;
    return std::clock() - start ;
}

int main()
{
    constexpr std::size_t N = 150'000 ; 
    
    {
        std::vector<int> vector(N) ;
        std::iota( std::begin(vector), std::end(vector), 0 ) ;
        vector.reserve( N*2 ) ;
        std::cout << "vector insert: " << geminate(vector) * 1000.0 / CLOCKS_PER_SEC << " msecs\n" ;
        assert( vector.size() == N*2 ) ;
    }
    
    {
        std::list<int> list(N) ;
        std::iota( std::begin(list), std::end(list), 0 ) ;
        std::cout << "list insert: " << geminate(list) * 1000.0 / CLOCKS_PER_SEC << " msecs\n" ;
        assert( list.size() == N*2 ) ; 
    }
} 

**** llvm ****
vector insert: 8640 msecs
list insert: 10 msecs
**** gnu ****
vector insert: 8710 msecs
list insert: 20 msecs

http://coliru.stacked-crooked.com/a/5e5e67482b9ce345

One reason to try and avoid std::list<>, notwithstanding its insert/erase performance, is that the widely used GNU implementation of the library is non-conforming with respect to std::list<>::size(); and it is likely to remain non-conforming till their abi is revised.

include <iostream>
#include <vector>
#include <list>
#include <numeric>
#include <ctime>
#include <cassert>

volatile std::size_t n = 0 ;

template< typename CONTAINER > std::clock_t perf_size()
{
    constexpr std::size_t N = 16'000'000 ; 
    CONTAINER cntr(N) ;
    const auto start = std::clock() ;
    n = cntr.size() ;
    return std::clock() - start ;
}

int main()
{
    std::cout << "vector size: " << perf_size< std::vector<char> >() * 1000.0 / CLOCKS_PER_SEC << " msecs\n" ;
    std::cout << "list size: " << perf_size< std::list<char> >() * 1000.0 / CLOCKS_PER_SEC << " msecs\n" ;
}

**** llvm ****
vector size: 0 msecs
list size: 0 msecs
**** gnu ****
vector size: 0 msecs
list size: 260 msecs

http://coliru.stacked-crooked.com/a/d04961a8a1d3162a