Python list insert iterators

[Weatherby,Gerard]

Python lists are arrays in other languages. You’ll have to roll your own or find something in https://pypi.org, etc. I think this incomplete implementation does the trick.

#
# MIT licensed
#
from dataclasses import dataclass
from typing import TypeVar, Generic

T = TypeVar("T")


@dataclass
class ListNode(Generic[T]):
    _value: T
    _next: "ListNode" = None


# noinspection PyProtectedMember
class ListIter(Generic[T]):

    def __init__(self, list_: 'LinkedList', node: ListNode[T]):
        self._list = list_
        self._node: ListNode[T] = node

    def __next__(self) -> T:
        if self._node != None:
            v = self._node._value
            self._node = self._node._next
            return v
        raise StopIteration()

    @property
    def value(self) -> T:
        return self._node._value

    def insert_after(self, value: T) -> None:
        self._list._insert_after(self._node, value)


# noinspection PyProtectedMember
class LinkedList(Generic[T]):
    """Singly linked List"""

    # noinspection PyTypeChecker
    def __init__(self):
        self._head: ListNode[T] = None
        self._tail: ListNode[T] = None

    def __iter__(self):
        return ListIter(self, self._head)

    def _insert_after(self, node: ListNode[T], value: T):
        if node != self._head:
            if node != self._tail:
                node._next = ListNode(value, node._next)

    def append(self, value: T) -> None:
        """Add to end of list"""
        if self._head != None:
            self._tail._next = (n := ListNode(value))
            self._tail = n
            return
        self._head = self._tail = ListNode(value)

    def appendleft(self, value: T) -> None:
        """Add to beginning of list"""
        if self._head != None:
            single = self._head == self._tail
            self._head = (n := ListNode(value, self._head))
            if single:
                self._tail = n
            return
        self._head = self._tail = ListNode(value)

    def index(self, nth: int) -> ListIter[T]:
        """Return iterator at nth position"""
        n = self._head
        for i in range(nth):
            n = n._next
            if n == None:
                raise IndexError('list index out of range')
        return ListIter(self, n)


#
# TODO: add search for value, deletion of elements, et. al.
#


def unit_test():
    """Test basics"""
    linked_list = LinkedList()
    for i in range(1, 11):
        linked_list.append(i)

    # iteration matching equivalent list
    for item in zip(linked_list, [i for i in range(1, 11)]):
        assert (item[0] == item[1])

    # verify index() method
    assert linked_list.index(0).value == 1
    assert linked_list.index(1).value == 2
    try:
        print(linked_list.index(11).value)
        assert False
    except IndexError:
        pass
    # test append left
    linked_list.appendleft(0)
    for item in zip(linked_list, [i for i in range(0, 12)]):
        assert (item[0] == item[1])


def python_mailing_list_example():
    """Example from mailing list"""
    linked_list = LinkedList()
    for i in range(1, 11):
        linked_list.append(i)
    a = linked_list.index(1)
    print(a.value)
    b = linked_list.index(5)
    print(b.value)
    a.insert_after(27)
    b.insert_after(45)
    print(','.join(str(x) for x in linked_list))


unit_test()
python_mailing_list_example()

From: Python-list <python-list-bounces+gweatherby=uchc.edu at python.org> on behalf of Guenther Sohler <guenther.sohler at gmail.com>
Date: Friday, March 3, 2023 at 12:28 PM
To: python-list at python.org <python-list at python.org>
Subject: Python list insert iterators
*** Attention: This is an external email. Use caution responding, opening attachments or clicking on links. ***

Hi Python community,

I have a got an example list like

1,  2,  3, 4, 5, 6, 7, 8, 9, 10
        T               T

and i  eventually want to insert items in the given locations
(A shall go between 2 and 3,  B shall go between 6 and 7)

Right now i just use index numbers to define the place:

A shall insert in position 2
B shall insert in position 6

However when i insert A in position 2, the index for successful insertion
of B gets wrong
(should now be 7 instead of 6)

No, it's not an option to sort the indexes and start inserting from the
back.
The most elegant option is not to store indexes, but list iterators, which
attach to the list element
and would automatically move, especially if an element is inserted before.

I could not find such functionality in python lists of [ 1,2,3 ]

Does python have such functionality ?
if yes, where can i find it ?
--
https://urldefense.com/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!gMAiBffu8h9N-YxV4nxLjapnR3InnNHeAbrHchQ-QoKfCHpF68yr8MKpEvXNdW1uJI3pFEXPiSvDRy9BpXAPfbP0k-Mn$<https://urldefense.com/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!gMAiBffu8h9N-YxV4nxLjapnR3InnNHeAbrHchQ-QoKfCHpF68yr8MKpEvXNdW1uJI3pFEXPiSvDRy9BpXAPfbP0k-Mn$>