[Single Linked List] Head concept doesn't seem to match descriptions

[tamireinhorn]

Reading the descriptions for Linked Lists in general, and even in the cited documentation for the exercise give us the idea of a list that would work as [1,2,3] where 1 would be the head node and 3 would be the tail node, hence follow LIFO. However, all the tests seem to expect that the HEAD would be 3, and, for instance, any new node pushed into the list would be the new head.
Given that even the exercise itself links to documentation which contradicts the expected results, either the explanation is not clear enough (or I'm not very good at understanding it) or the tests should be somewhat changed. I've confirmed that with a mentor as well.

[github-actions]

🤖   🤖

Hi! 👋🏽 👋 Welcome to the Exercism Python Repo!

Thank you for opening an issue! 🐍  🌈 ✨

•   If you are requesting support, we will be along shortly to help. (generally within 72 hours, often more quickly).
•   Found a problem with tests, exercises or something else??  🎉
    ◦ We'll take a look as soon as we can & identify what work is needed to fix it. (generally within 72 hours).

​          ◦ If you'd also like to make a PR to fix the issue, please have a quick look at the Pull Requests doc.
             We  💙  PRs that follow our Exercism & Track contributing guidelines!

•   Here because of an obvious (and small set of) spelling, grammar, or punctuation issues with one exercise,
    concept, or Python document?? 🌟 Please feel free to submit a PR, linking to this issue. 🎉

‼️  Please Do Not ‼️ ​        ❗ Run checks on the whole repo & submit a bunch of PRs.               This creates longer review cycles & exhausts reviewers energy & time.               It may also conflict with ongoing changes from other contributors. ​        ❗ Insert only blank lines, make a closing bracket drop to the next line, change a word               to a synonym without obvious reason, or add trailing space that's not an EOL for the very end of text files.         ❗ Introduce arbitrary changes "just to change things" .         ...These sorts of things are not considered helpful, and will likely be closed by reviewers.

• For anything complicated or ambiguous, let's discuss things -- we will likely welcome a PR from you.
• Here to suggest a feature or new exercise?? Hooray! Please keep in mind Chesterton's Fence.
  Thoughtful suggestions will likely result faster & more enthusiastic responses from maintainers.

💛  💙  While you are here... If you decide to help out with other open issues, you have our gratitude 🙌 🙌🏽.
Anything tagged with [help wanted] and without [Claimed] is up for grabs.
Comment on the issue and we will reserve it for you. 🌈 ✨

[BethanyG]

Hi @tamireinhorn 👋🏽

Thanks for filing this issue. I don't have time at the moment, but will investigate when I do. Meanwhile, could you give me a little more detail? Which tests seem off to you, against which code? What would be your proposed changes?

[tamireinhorn]

For instance, this test:
def test_non_empty_list_has_correct_head(self): sut = LinkedList([1, 2]) self.assertEqual(sut.head().value(), 2)
clearly expects that THE LAST element of the list is the head. In my mind, the test should read:
def test_non_empty_list_has_correct_head(self): sut = LinkedList([1, 2]) self.assertEqual(sut.head().value(), 1) .
This test exemplifies this even better:
def test_pushing_to_empty_list_changes_head(self): sut = LinkedList() sut.push(5) self.assertEqual(len(sut), 1) self.assertEqual(sut.head().value(), 5)
It specifically expects that the head of the LL should change with a push, which doesn't seem to match the concept that I've read about. So I'd say this merely should be talking about the tail of the list, right?
However, this would generate an inconsistency here:
def test_non_empty_list_traverse(self): sut = LinkedList(range(10)) current = sut.head() for i in range(10): self.assertEqual(current.value(), 9 - i) current = current.next() self.assertIsNone(current)
Since it seems to expect that a linked list built of range(10) should in fact be 10-> 9 -> ... -> 1

[IsaacG]

LinkedList.push() pushes elements to the head of the list. Whether intentional or not, LinkedList([a, b, c]) expects elements a, b, c to be pushed to the list ... in that order. Pushing a to a ll results in list(ll) = [a]. Pushing a then b results in list(ll) == [b, a]. And pushing a then b then c results in list(ll) == [c, b, a].

This means list(LinkedList([a, b, c])) = [c, b, a].

I have no idea if this is intentional or not, but this is how the exercise is currently set up.

[tamireinhorn]

Exactly. However, any conceptual aid that a student might seek about linked lists, even the one referenced in the README, will point them towards expecting list(LinkedList([3,4,5])) = [3, 4, 5]. You could argue that this exercise expects a stack implementation, but here's the catch: the exercise expects that the LL is set as: 5 (head) -> 4 -> 3 (tail). Any representation of the LL expected by the exercise winds up being very unintuitive for the reader. In this example, pop() would return the leftmost item, the HEAD of a list, even though we'd expect the tail to be the last item of it given the nomenclature.
Furthermore, the student could build something such as: 3 (tail) -> 4 -> 5 (head) in order to better fit the examples given in the reference, but that would fail other tests, where it's expected (as should be) that head.next != None.
It might very well be that the subset of people I've discussed this with are an exception, and that the exercise is perfectly clear to anyone else. However, given that any reference to LLs a student would find searching to know more about the concept (which, if they haven't seen before, they likely will) results in examples that would not pass our tests, I tend to think something in our exercise is not clear enough.

[BethanyG]

Hi @tamireinhorn 👋🏽

First - apologies for taking so long to get back to you. Things have been busy, but I also wanted to make absolutely sure that I had resources as well as an implementation consistent with a stack that passes all the tests. I agree that it is easy to get confused, as many resources on singly linked lists cover both stacks AND queues, which have somewhat "opposite" implementations of push and pop.

As the directions point out, we are implementing a LIFO/stack abstract data structure.

As I was coding, it was easiest to visualize a NewNode being added to the "top" or left-hand side of the LinkedList, thereby becoming the head Node. Having the head be at the left-hand side allows additions to be made in constant time. More details in the book excerpt further down.

The former head (OldNode) is "pushed" or moved right-ward or "down":

1. NewNode becomes head: LinkedList.head is updated to NewNode.
2. NewNode.next is then set to OldNode (the one that used to be LinkedList.head).
3. LinkedList.size is updated to reflect a newly added Node.

So under those circumstances, whatever is pushed last is designated LinkedList.head. Because this is LIFO/Stack, LinkedList.pop() removes and returns LinkedList.head, and the steps above are done in reverse:

1. LinkedList.head.value() gets assigned to a variable.
2. LinkedList.head gets reassigned the Node returned from LinkedList.head.next()
3. LinkedList.size is decremented by 1
4. variable with former LinkedList.head Node.value() is returned.

So the big takeaway for a student (IMHO) is that in an array-like stack head points to the "left-most" position always for both push and pop purposes -- not the "end", or right-hand side as you might expect when working with pop() or append() on a list.

You can see my implementation here it is virtually a one-to-one copy of the stack example in the attached excerpt of Data Structures and Algorithms in Python, published by Wiley.

Stack with Singly Linked List.pdf

Since I'd never done a singly linked list before, I also went googling and found the following:

1. Real Python: Linked Lists - which has a pretty detailed rundown of single, double, and circular linked lists, as well as the core Python deque.
2. Towards Data Science: How to Implement a Linked List in Python.
3. sanfoundry - which is an implementation without a whole lot of explanation.
4. Koderdojo: Coding a Stack Using a Linked List in Python - which is also an implementation without much explanation.

---

TL;DR

This may be a confusing/challenging exercise, but the tests are correct, as are the instructions (but they do indeed leave a whole bunch of detail out). The credit link (this exercise was adapted from a Ruby exercise and we linked to it to give credit) is being confused for documentation when it shouldn't be.

1. I do think we could do a better job with our instruction append, so that students are given links that are Python, and that also explain the difference between a queue and a stack, and direct them toward a non-list based stack. Maybe all or some of those links I found? We can't exactly point students to the Algo book, since it is $$$.

2. We probably want to have a hints file that perhaps shows some diagrams or other more pointed examples, for students who are really stuck and really confused.

3. We probably want to make it clearer that the source link is NOT documentation. We'd need to do that by raising and issue in exercism/problem-specifications.

4. linked lists, stacks and queues aren't really straightforward if you've never seen them before. We may want to consider bumping the difficulty level on this to medium.

Thoughts? I know I took a while to get back to you (apologies!) - but I'd welcome a PR to add instructions_apped.md and/or hints.md for this exercise, should you want to take that on.

[BethanyG]

Hi @tamireinhorn -

I've submitted both an instruction append and a hints file in PR #3026. I'd welcome any thoughts or additions/edits you'd want to make. It also OK if you don't want to comment.

[tamireinhorn]

Perfect! I think it's much better and clearer now. I'll see if I can add a small representation with arrows as to what the LL should look like, what do you think? Em qui, 28 de abr de 2022 21:18, BethanyG ***@***.***> escreveu:

…

Hi @tamireinhorn <https://github.com/tamireinhorn> - I've submitted both an instruction append and a hints file in PR #3026 <#3026>. I'd welcome any thoughts or additions/edits you'd want to make. It also OK if you don't want to comment. — Reply to this email directly, view it on GitHub <#3009 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AI5HUYZHAJEWSANHMAPLH5DVHMTERANCNFSM5TLOBLQA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[jeewonkoo]

I found this issue on https://ovio.org/projects and would love to contribute! I am new to Github contribution but have coding experience in Python. Please let me know!