Working with Common Data Structures - How Do Singly Linked Lists Work and How Do They Differ From Doubly Linked List?

Python
1

Tell us what’s happening:

I’m questioning this time complexity:

If the node has to be inserted somewhere in the middle of the linked list…
The insertion operation has a constant space complexity O(1), since inserting a new node only requires creating it and updating the connections between the nodes. This operation doesn’t depend on the size of the linked list itself.

If it has to insert a new node near the end of the list (worst case) the complexity is n because it needs to traverse the list to n-1

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:146.0) Gecko/20100101 Firefox/146.0

Challenge Information:

Working with Common Data Structures - How Do Singly Linked Lists Work and How Do They Differ From Doubly Linked List?

2

“Somewhere in the middle” is a bit vague but if we need to measure worst case, that’s n-1 from the end? Not so different from adding it to the end. From the lesson:

To insert a node at the end of the linked list, first you need to reach the end and then add a connection to the new node to make it the new tail node.
This operation has linear time complexity, O(n)

Some references

Insert – O(n)
Demystifying Linked List Time Complexity – TheLinuxCode

Inserting or removing an element at index i in a list of length n takes time proportional to n-1
6.4 Linked Lists and Running Time — CSC148 Course Notes

Am I correct on this? Just wanted some feedback before opening an Issue

3

what part? that paragraph is talking about space complexity

1 Like
4

Thanks! I totally missed that. It’s the space complexity for any Linked List Insert overall.

In this case… I think it’s missing the time complexity for inserting into the middle of the list. It mentions it specifically for the beginning and end, so I was expecting that to be the next time complexity mentioned.

Beginning:

Inserting a node at the beginning of the linked list has a constant time complexity O(1)…

End:

To insert a node at the end of the linked list, first you need to reach the end and then add a connection to the new node to make it the new tail node.

This operation has linear time complexity, O(n), where n is the number of nodes stored in the linked list, because first you need to reach the end of the linked list to make the insertion and this would require going from one node to the next and so on until the end is reached.

Middle:

If the node has to be inserted somewhere in the middle of the linked list, the connections between the nodes will have to be updated too. The previous node in the sequence should be connected to the new node and the new node should be connected to the next node, like in the following diagram.

I missed that it switched over and started talking about space complexity.