Complexity of the linkedlist

#1

how the inseration operation take the 0(1) time . if the head is pointing to the first node and i have to insert a node at k index .
Then i need to traverse to the k-1 node then insert the kth node so 0(k)

#2

@Vikaspal if u have to insert at head or tail
it works in o(1) using head and tail pointer
but if in between at k distance then yes its not o(1) its O(k)
i hope its cleared if yes dont forget mark it as resolved :smiley:

#3

but for the last element we have to iterate till the null does the iteration is going to count ?

#4

if you are implementing linked list using a tail pointer too then you dont have to go to last so
o(1) otherwise its o(size) @Vikaspal

#5

@vatsal38 okay got it means it double linked list it always 0(1)

#6

yes and if insert at pos k in middle its o(k)

#7

@vatsal38 when we are using the forward_list its inseration and deletion take the constant time means 0(1) due to the inbuilt functionality?

#8

@Vikaspal yes in it to if you insert at end or begin its 0(1) due to internal functionality but inert_after() function takes o(n).

#9

@vatsal38 could be explain this snippet of code
forward_list< int >::iterator ptr;

// Inserting value using insert_after()

// starts insertion from second position

ptr = flist.insert_after(flist.begin(), {1, 2, 3});

I didn’t get this and also the push_back() and insert_after() seem like the same ?

#10

it means the list 1 2 3 will be inserted at begin position .
push back means inserting at end always
insert after means inserting in the position you want.
for more function details refer this

#11

if its cleared dont forget to mark the doubt resolved @Vikaspal :smiley:

#12

@vatsal38
sorry i send the wrong function to u .
I means emplace_fron() or push_front() it like same ?

#13

@Vikaspal emplace front means append at start and push _ back append at last.
complexity of both is 0(1)

#14

is it clear now? @Vikaspal

#15

@vatsal38 i am saying the push_front() emplace front()
and also how to take the inputs from user in list ?

#16

yes they do same work
for input run a loop for how many inputs and take a var and cin it then l.push_back(var) where l is list @Vikaspal. is it ok?

#17

@vatsal38
ya i did like that but after reading the documentation there is no push_back() it feels like lol :grin: :rofl:

#18

push_back is both in list and vector
just study the functions of stl from gfg @Vikaspal

#19

so is your doubt clear now?

#20

@vatsal38 i am talking about forward list push_back a didn’t find it?