Singly linked list. Implementation of the Get method - getting an element by index-CodePudding

from typing import Any, Optional


class Node:
    def __init__(self, value: Optional[Any] = None, next: Optional['Node'] = None) -> None:
        self.value = value
        self.next = next

    def __str__(self) -> str:
        return 'Node [{value}]'.format(
            value=str(self.value)
        )


class LinkedList:
    def __init__(self) -> None:
        self.head: Optional[Node] = None
        self.length = 0

    def __str__(self) -> str:
        if self.head is not None:
            current = self.head
            values = [str(current.value)]
            while current.next is not None:
                current = current.next
                values.append(str(current.value))
            return '[{values}]'.format(values=' '.join(values))
        return 'LinkedList []'

    def append(self, elem: Any) -> None:
        new_node = Node(elem)
        if self.head is None:
            self.head = new_node
            return

        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        self.length  = 1

    def remove(self, index) -> None:
        cur_node = self.head
        cur_index = 0
        if self.length == 0 or self.length <= index:
            raise IndexError

        if cur_node is not None:
            if index == 0:
                self.head = cur_node.next
                self.length -= 1
                return

        while cur_node is not None:
            if cur_index == index:
                break
            prev = cur_node
            cur_node = cur_node.next
            cur_index  = 1

            prev.next = cur_node.next
            self.length -= 1


my_list = LinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)
print('Current list:', my_list)
# print('Getting the third element:', )
print('Removing the second element.')
my_list.remove(1)
print('New list:', my_list)

Result:
Current list: [10 20 30]
Getting the third element: 30
Removing the second element.
New list: [10 30]

In a singly linked list, a link is a link only to the next element, that is, it can only move towards the end of the list.
It is impossible to find out the address of the previous element based on the contents of the current node.
Tell me how to implement getting an element by index. And get index 2 (30) ?

CodePudding user response：

Tell me how to implement getting an element by index.

Your instructor is inviting you to

def get(self, index: int) -> Node:

and then flesh out the definition.

You will find the definition of remove(self, index) already offers all that you need. Simply traverse the list in readonly manner, without changing any .next attributes.

Though you may find it simpler to just use a for i in range(index): loop, never bothering to examine self.length.

If a user tries e.g. .get(99), running off the end of the list, it's unclear what the proper result should be. Maybe an exception? You might have latitude to specify what correct behavior would be.

And get index 2 ?

Once def get is correctly defined, it's a simple call:

assert my_list.get(2).value == 30