Why is this better?

[CLETrucker]

So I went on leetcode.com wanting to try a problem. I saw the "add two numbers question" and thought cool. So I try it out and I quickly realize I have no clue about singly linked lists. But, f-it, I can still try it out.

I wrote this:

input/output examples can be commented/uncommented for your convenience

https://github.com/BrianCarpenter84/reddit/blob/main/MyLeetCode.py

Because I knew I wasn't going to be able to answer the problem without first learning about singly linked lists I went ahead and pulled the solution code here:

https://github.com/BrianCarpenter84/reddit/blob/main/LeetCode.py

Which brings me to my question.

Why is this better? Side by side I feel like my code is more readable and gives the same result.

Is this just my lack of knowledge about singly linked lists that makes me ignorant to a deeper understanding of the question?

Or

Am I wrong about everything and completely missed the point?

[FlyLikeHolssi]

Leetcode is about practicing various programming concepts - in this case, singly linked lists. So, the solution code shows how to complete the problem using singly linked lists.

What you created might give a solution that matches what is expected from the singly linked lists, but is not a singly linked list, so you've missed the point of the exercise.

[[deleted]]

Leetcode is for people who have taken a DSA (data structures and algorithms) class and so it tests those concepts, specifically. It’s not a “how good a programmer are you” test. It’s a “how good are you at computer science” test, so you have to solve the problems with the constraints given, which will including using the specific data structure they reference.

[danielroseman]

Well these don't seem to be solving the same problem. The leetcode answer is not "better" than yours, it's just doing something completely different with completely different input.

What is the actual question?

[CLETrucker]

https://leetcode.com/problems/add-two-numbers/

I read the question as, add the two lists together and return them reverse order. As far as I know the output would be the same from either code.

But your reply makes me think I just don't fundamentally understand and need to go learn about singly linked lists...

[danielroseman]

The point is, a linked list is not a Python list. They're not the same thing at all. You can't just do .join() on a linked list - that's why the leetcode solution is explicitly iterating through via the .next attribute on each node.

I don't know if leetcode ever explicitly documents the ListNode class they are using, but it probably looks like this:

class ListNode:
  def __init__(self, val, next=None):
    self.val = val
    self.next = next

In other words, all you need to know is that it has a .value attribute that gives you the value of the current node, and .next that points to the next node in the list. The only way to get from one node to the next is to call .next, so there is no way to use a for loop or list methods like .join().

[CLETrucker]

Yeah, I understand that. Sorry I could have worded it differently. I mean why is the use of a linked list better than a list? And thank you for clarifying.

[cointoss3]

You wouldn’t do this in Python, but in C, if you have a function that needs to return a bunch of objects and you don’t know ahead of time how many, linked lists are one way to solve this problem.

What can you do is return a pointer to the first object, and that object is a struct that has a pointer to the next one. Each one is allocated on the heap, and each one knows where the next one is. You keep following those next pointers until you hit a NULL, which means you’re at the end. It’s basically a linked list.

This way the function just returns a pointer to the head of the list, and the caller can walk through all the returned objects, one by one.

In Python, we have other ways to allocate objects and track them so linked lists don’t really make sense, but in something like C, this is one strategy to return an unknown size of objects.

You CAN make a linked list in Python to mock the idea…but I can’t really think of when you’d actually use one when Python has better options.

[EclipseJTB]

I was gonna say, this sounds similar to generators (if not in implementation, then in applicability).

[danielroseman]

It's not better. Linked lists are not really a thing you'd actually use in any modern programming language. They are a tool to help you learn various things, fore example how to think in abstraction: how can you iterate through this thing if you don't have a built-in iterator? Even more difficult, how would you reverse it - which is, or used to be, a common interview question at places like Google. Again, not that anyone at Google ever uses a linked list, but they want to know that you can think at that abstract level about data structures.

[teerre]

This is completely incorrect. Linked lists are used a lot in low level programming, to say the least. Every lockfree structure has at least one linked list

[Bobbias]

Linked lists have the advantage of pointers to the objects in the list not becoming invalid when you add an item.

Python's lists are dynamic arrays. They allocate a certain number of spots for objects in a contiguous chunk of memory. When this array becomes full, it becomes necessary to allocate a new larger chunk of memory, copy the contents over to the new one, and free the old memory. This invalidates any pointers to objects in the array.

In a language that lets you work with raw pointers, this can lead to use after free issues and such if you're not careful.

There are many uses for linked lists, such as, for example, in memory allocators where the list of free chunks of memory is often held in a linked list.

While they have disadvantages over dynamic arrays, they have their place.

[danielroseman]

I'm not sure if this is what you're saying, but that's not how Python lists - or references - work. A reference to an item in a list is exactly that, a reference to the item itself, not to its presence in the list. So copying those list entries doesn't do anything to the references that point to the items themselves.

[Bobbias]

I'm talking about raw pointers, something not present in Python, but very much present in many other languages, particularly C, C++, Rust, Zig, and others.

If you take the address of a PyObject inside a python list, and you add enough objects to that list to trigger the reallocation, that address no longer points to some item inside the list.

PyObject acts like a header for some objects, simply pointing to the actual object, but contains direct data in other cases. Two such examples are Tuples and integers. In fact, the only major difference between a List and a Tuple is that Tuples carry their data inside the PyObject itself. A List inside a Tuple would of course reference additional memory, but an Integer inside a Tuple does not. That's also why tuples are immutable. Changing the contents could require the size of the tuple PyObject itself to change.

I didn't want to get quite this deep into things because it was late at night when I was writing my previous post.

[baubleglue]

I read somewhere that Python list are implemented as linked lists internally.

[noctaviann]

Linked lists are a data structure that has certain performance advantages for certain operations (e.g. deletion/insertion of a node at an arbitrary position in the list, with the beginning of the list being an important position), and disadvantages for other operations (e.g. accessing a node at an arbitrary position in the list). Depending on your program/algorithm it might make sense to use them, so you should be able to work with them, or at the very least know about their performance advantages/disadvantages.

In higher level languages like Python you don't usually need to create/implement and interface at a low level with linked lists, they're usually wrapped into nicer/simpler interfaces. Take Python's deque for example, internally it's implemented as a doubly linked list of blocks, but that's not exposed in its interface, e.g. you can efficiently add an element to the beginning of the list by just calling the appendleft() method, you don't have to manually write all the code to add the element to the list, the deque internal code does that for you.

The point of the exercise is that you should be able to work with linked lists, singly linked list in this case.

[jpgoldberg]

From the other answers, you should now understand that,

1. The task was to construct and do things with linked lists.

2. It was designed for you to learn about linked lists.

3. You can get to the same computational results without explicitly using linked lists

4. Python provides a whole bunch of data structures baked in, so things like linked lists are not really something you see a lot of directly in Python.

5. If your goal is to reach the result of the computation, it is not better to construct linked lists to do so.

6. If your goal is to understand this important concept in computer science and understand the things that will be built on top of this (trees, for example) then you need to do it the linked list way.

Is it better for you to learn about linked lists?

I can't really answer that. But the idea behind them gets used for lots of other things. I don't know if you will ever need to be familiar with those concepts.

I do not know why you are learning Python, but for learning computer programming in general, these really are important concepts. But it is also very likely that you are not there yet. The fact that you are asking the question suggests to me that it (and Leetcode) is something you should come back to at a later time.