2
\$\begingroup\$

I've been programming for 3 months now, and I've just come across Linked List, and I'm not gonna lie, I've been struggling a little. I wrote this code to practice on Linked Lists. The purpose is to add a Node in a desired position. Even though it works, I'm wondering if there would be more efficient and synthetic solutions to this and if I'm not considering some cases where this wouldn't work.

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

def print_linked_list(head):
    while head:
        print(head.val)
        head = head.next

def add_node(prev_node, node_to_add):
    node_to_add.next = prev_node.next
    prev_node.next = node_to_add

def run_and_add(head, position):
    counter = 0
    current_node = head
    while current_node:
        if counter != position-1:
            print(f"Node ({counter}): {current_node.val}")
            current_node = current_node.next
        else:
            try:
                number = int(input("Please insert an Integer: "))
            except ValueError:
                print("Not an Integer")
                return
            new_node = ListNode(number)
            add_node(current_node, new_node)
            print("Node added at position:", position)
        counter += 1

    print("Updated linked list:")
    print_linked_list(head)

first = ListNode(1)
first.next = ListNode(2)
first.next.next = ListNode(3)
run_and_add(first, 2)

As I said it's working fine, but I think there might be a better way to do it.

\$\endgroup\$

4 Answers 4

6
\$\begingroup\$

Summary

I won't dwell on what has already been cited by users toolic and J_H, so I just have a few comments:

Type Hinting

I would suggest that you include type hinting, especially if your functions do not contain docstrings that describe the type of arguments being passed to functions (J_H has suggested this, so pardon if this is too repetitive).

Be More Tolerant of Errors in User Input

If the user does not enter a valid integer in function run_and_add, you essentially quit. You should instead put out the prompt again and give the user as many chances needed to enter valid input. The user can always terminate by entering Ctrl-C if they get stuck.

Strive for Encapsulation and Reusability

I can't stress too strongly that your code is crying out for you to create a LinkedList abstract data type that abstracts the notion of a linked list while encapsulating the actual implementation. To that end, I would use attribute names that begin with '_' where appropriate to suggest that they are "private" and not to be either updated nor depended on existing in the future (such as the next instance attribute of the ListNode class.

The following classes are just one possibility. Note:

  1. There is no print method implemented since printing the entire list is trivial given that the class implements the iterator protocol. Besides, what if you wanted to print to a file? Then a print method would require one or more additional arguments.
  2. The client never explicitly creates ListNode instances.
  3. The linked list keeps explicit track of the final (last) node in the list to provide efficient appending of a node or an entire linked list to the end.

I can envision your using this as a starting point and potentially adding other methods (for example, __eq__ methods to compare nodes and linked lists).

"""A module for creating and manipulating linked lists."""

from abc import ABC, abstractmethod
from typing import TypeVar, Any

LinkedListInstance = TypeVar('LinedListInstance', bound='LinkedList')

class NodeType(ABC):
    @property
    @abstractmethod
    def val(self):
        pass

    @val.setter
    @abstractmethod
    def val(self, val):
        pass

class LinkedList:

    class _ListNode(NodeType):
        """Initialize a new node with some value, val."""

        def __init__(self, val):
            self._val = val
            self._next = None

        @property
        def val(self):
            return self._val

        @val.setter
        def val(self, val):
            self._val = val

        def __repr__(self):
            return f'_ListNode({repr(self._val)})'

        def __str__(self):
            return str(self._val)

    def __init__(self):
        """Create a new, empty linked list."""

        self._head = None
        self._tail = None

    def append_node(self, val: Any) -> LinkedListInstance:
        """Append a new node to the list initialized with val."""

        new_node = LinkedList._ListNode(val)
        if self._head is None:
            self._head = new_node
        else:
            self._tail._next = new_node
        self._tail = new_node

        return self

    def insert_node(self, at_node: NodeType, val: Any) -> LinkedListInstance:
        """Create and insert a new node after the specified at_node node initialized
        with val."""

        if at_node is self._tail:  # special case
            return self.append_node(val)
        node_to_insert = LinkedList._ListNode(val)
        node_to_insert._next = at_node._next
        at_node._next = node_to_insert

        return self

    def append_list(self, linked_list: LinkedListInstance) -> LinkedListInstance:
        """Append a linked list to the current list."""

        if self._head is None:
            self._head = linked_list._head
        else:
            self._tail._next = self._head
        self._tail = linked_list._tail

        return self

    def __iter__(self) -> NodeType:
        """Iterate the list."""

        current = self._head
        while current is not None:
            yield current
            current = current._next

if __name__ == '__main__':
    def insert_node_at_position(linked_list: LinkedList, position: int) -> None:
        for counter, current_node in enumerate(linked_list, start=1):
            print(f"Node at position {counter}: {current_node}")
            if counter == position:
                while True:
                    try:
                        number = int(input("Please insert an Integer: "))
                    except ValueError:
                        print("Not an Integer")
                    else:
                        break
                linked_list.insert_node(current_node, number)
                print("Node added at position:", position)

        print("Updated linked list:")
        for node in linked_list:
            print(node)

    linked_list = LinkedList().append_node(1).append_node(2).append_node(3)
    insert_node_at_position(linked_list, 2)
\$\endgroup\$
5
\$\begingroup\$

names

class ListNode:

This is a perfectly fine identifier, as-is.

There's no adjacent code that uses other node types. Consider shortening to just Node.

design of Public API

OO

def print_linked_list(head):
...
def add_node(prev_node, node_to_add):
...

These are somewhat unexpected signatures, the sort of thing I might expect in Fortran code. ListNode turned out to be just a very brief @dataclass, with no OO aspect to it. Given a ListNode, we find no methods to call on it for list operations. This works, but makes it a little harder for developers and maintenance engineers to discover your API. For example if I hit a breakpoint() I cannot p dir(node) to find plausible things I might do with a node -- I instead have to scour the codebase for such operations.

Also, your signatures lack ListNode type annotations, so I can't just grep for that or use type-aware IDE features to narrow my search.

I propose some more natural implementations.

    def print_linked_list(self):
        head = self
        while head:
            print(head.val)
            head = head.next

    def add_node(self, node_to_add):
        assert node_to_add.next is None
        node_to_add.next = self.next
        self.next = node_to_add

Consider renaming these to simply .print() and .insert().

interactive input vs parameter

(I am paraphrasing, renaming the vague number to new_val.)

def run_and_add(head, position):
                ...
                new_val = int(input("Please insert an Integer: "))

Prefer to place calls of input() further up in the call stack, such as within def main():, and pass in such a value as a parameter:

def run_and_add(head, position, new_val):

main guard

On which topic, you don't have a main() function, and you really need one. Why? So you or some maintenance engineer can safely import linkedlist when exercising your functions in a test suite. Also, it's convenient to ensure that local variables like first (which are not part of your exported Public API) will disappear when they go out of scope. That way such identifiers won't pollute the module namespace.

def main():
    first = ListNode(1)
    first.next = ListNode(2)
    first.next.next = ListNode(3)
    run_and_add(first, 2)

if __name__ == '__main__':
    main()

single responsibility

run_and_add() is an awkward identifier, suggesting that instead of one we're doing two things. Also I find "run" less than clear.

Consider making caller responsible for passing in an already-created node, and then this could be a simple insert_at_position(head, position, new_node) function.

\$\endgroup\$
3
\$\begingroup\$

Overview

You've done an excellent job:

  • You did a good job partitioning code into functions
  • You used meaningful names for the class, functions and variables
  • You showed an example of how to run the code

Here are some adjustments to consider for coding style.

Documentation

You should add documentation at the top of the file describing the purpose of the code. It is not clear what the meaning of the input is or what the output is.

"""
Linked list for integers ...

"""

Lint check

pylint identified a few style issues.

The PEP 8 style guide recommends adding docstrings to classes and public methods.

Input checking

The code handles the input very well. I tried inputting words and spaces and other junk, and I get the expected error message.

Consider also using the pyinputplus module. It has a feature where you allow the user to keep trying to input valid data. This is handy if the user makes a typo.


I'll leave it to the linked list experts out there to give you more specific advice along those lines.

\$\endgroup\$
3
\$\begingroup\$

Your code looks good, and you've gotten some good suggestions from others already, but I would advise to think about the intended usage, about responsiblity of the class(es), and about encapsulation. You can usually get some hints on all of this by using your code. Taking it a step further, you could use test-driven-development (TDD) to help basically clarify a specification for what you should implement.

I'll show this with pytest because I find it superiour to the standard library's unittest (and I would argue it is the de-factor default testing framework to use with python). I'll just take your code as-is and will copy it into a listnode.py, and now I write on test_listnode.py.

from listnode import ListNode

def test_creating_node():
    node = ListNode("dummy_data")

    assert node.val == "dummy_data"
    assert node.next == None

When I run this (pytest from same dir) I immediately get errors;

Node (0): 1
Please insert an Integer: 
==================================================== short test summary info ====================================================
ERROR test_listnode.py - OSError: pytest: reading from stdin while output is captured!  Consider using `-s`.

Here we see what @J_H already pointed out, so let's put in his main guard. We run again and this looks fine:

$ pytest   
====================================================== test session starts ======================================================
platform darwin -- Python 3.12.1, pytest-8.1.1, pluggy-1.4.0
rootdir: .
collected 1 item                                                                                                                

test_listnode.py .                                                                                                        [100%]

======================================================= 1 passed in 0.00s =======================================================

Alright, so let's now add another node.

from listnode import ListNode, add_node

def test_creating_node():
    node = ListNode("dummy_data")

    assert node.val == "dummy_data"
    assert node.next == None
    
def test_creating_multiple_nodes():
    node = ListNode("first")
    add_node(node, ListNode("second"))

...but wait a minute - what am I adding these to? Something is strange.

This is what @Booboo already pointed out. You should really have a linked list to deal with the nodes. So let's tweak this a bit. I won't use what @Booboo wrote, because it should be up to you to decide on the behaviour of the list.

You say you want to be able to insert a node at a position, and I will also make an assumption that you want the list to be iterable, so I will implement tests for those two.

from linkedlist import LinkedList, ListNode

def test_creating_node():
    node = ListNode("dummy_data")

    assert node.val == "dummy_data"
    assert node.next == None
    
def test_creating_empty_list():
    lst = LinkedList()

    assert not lst  # since it is empty

def test_creating_list():
    lst = LinkedList()
    lst.add_node(ListNode("dummy_data"))

    assert lst
    assert next(iter(lst))).data == "dummy_data"

def test_inserting_node_at_position():
    lst = LinkedList()
    for data in ["first", "second", "third"]:
        lst.add(ListNode(val)

    lst.insert(2, ListNode("new"))
    
    assert len(lst) == 4
    assert lst[2].data == "new"
    assert lst.head == "first"

    # let's also check the last element
    data = None
    for node in lst:
        data = node.data
    assert data == "third"

Now, what you would do if you continued using TDD here, is basically to first write tests, and then to write the code you need to make sure that the tests pass.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.