Adding Node to Linked List

Question

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.

Answer 1

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)

Answer 2

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.

Answer 3

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.

Answer 4

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.