🔒 Data structures and time complexity

[clear hemlock]

I've been trying to wrap my head around DSA. My problem is that most courses explain you the idea behind them, maybe give you a small example but I've seen none that explain both the theory and how to implement one.

Started trying to write a linked list to see if I understood it properly but I'm pretty confident that my time complexity for insert_at and insert_last are O(n) rather than O(1).

https://paste.pythondiscord.com/BJ4Q

Really feel like I'm missing something important about how I should be learning DSA.

[radiant tinsel]

@clear hemlock

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[fervent wolf]

yeah that looks O(n) to me as well

append_last could be O(1) if your LinkedList class remembered the last element

not sure if it's correct

but inserting at any given position should be O(n)

https://www.geeksforgeeks.org/time-and-space-complexity-of-linked-list/

[fervent wolf]

I think while this is possible, it wouldn't technically be a single linked list anymore

[clear hemlock]

Shoudn't inserting at any given point be O(1)? Isn't a normal array basically O(n) if you want to insert at any given point?

I thought that was supposed to be the main difference between a linked list and a normal dynamic array

Or at this point i'm just confusing time with space complexity?

[fervent wolf]

I think an array or vector (like python's list) is probably gonna be implemented as a linked link so both will be O(n) to insert at any place

[fervent wolf]

If you have an array of specific size and you do arr[i] = 42 then it's overwriting the value and is indeed O(1)

but list.insert(3, "some val") is O(n)

[fervent wolf]

space complexity is about memory

[vapid mesa]

no, Python's list is not a linked list

[clear hemlock]

I think i need to go and revisit the lecture to figure out if linked list were supposed to have a time or a space complexity of o(1)

[vapid mesa]

Inserting into the middle of a linked list will be O(1) if you have a direct reference to a node in the list

inserting by index is still O(index)

[clear hemlock]

starting to thing i should go and try to write this in c++ rather than python 🤦‍♂️, feels like i'm missing something

[vapid mesa]

If you only have an index, inserting an element will be linear complexity, you're correct here

Do you have some kind of assignment/extra material? Maybe you misunderstood the task

[fervent wolf]

ah yeah you're right, the C impl looks just like an array and they just shift the position of existing elements when inserting at a position

[clear hemlock]

just trying to learn it myself , I watched the mit's first 2 courses. But it had no implementation so figured out I'd give it a try

[vapid mesa]

A linked list supports O(1) insertion if you store the node you want to insert stuff after. Because then you don't need to find where to put the new element

[vapid mesa]

Yes, Python's list is a resizable array (like vector in C++ or array in JavaScript)
Linked lists are actually a lot more rare compared to how much they're covered in DSA courses and leetcode-style problems. Even python's collections.deque is a linked list of small arrays, not just a linked list

[radiant tinsel]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.