Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Пожалуйста помогите срочно надо! Python!

Василий Коршук Ученик (95), закрыт 3 года назад
Задача 6. Односвязный список

Мы продолжаем тему структур данных и алгоритмов. И в этот раз вам нужно реализовать односвязный список.

Связный список — это структура данных, которая состоит из элементов, называющихся узлами. В узлах хранятся данные, а между собой узлы соединены связями. Связь — это ссылка на следующий или предыдущий элемент списка.



В односвязном списке связь — это ссылка только на следующий элемент. То есть в нём можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

Реализуйте такую структуру данных без использования стандартных структур Python (list, dict, tuple и прочие) и дополнительных модулей. Для структуры реализуйте следующие методы:

append — добавление элемента в конец списка,
get — получение элемента по индексу,
remove — удаление элемента по индексу.
Дополнительно: сделайте так, чтобы по списку можно было итерироваться с помощью цикла.



Пример основной программы:

my_list = LinkedList()

my_list.append(10)

my_list.append(20)

my_list.append(30)

print('Текущий список:', my_list)

print('Получение третьего элемента:', my_list.get(2))

print('Удаление второго элемента.')

my_list.remove(1)

print('Новый список:', my_list)



Результат:

Текущий список: [10 20 30]

Получение третьего элемента: 30

Удаление второго элемента.

Новый список: [10 30]
Лучший ответ
Остальные ответы
Константин GF Ученик (195) 2 года назад
class LinkedList:
class __Node:
def __init__(self, value):
self.value = value
self.nxt = None

def __init__(self, *args):
length = len(args)
self.__length = length
self.__head = self.__Node(args[0]) if length > 0 else None
self.__tail = self.__head
for i in range(1, length):
self.__tail.nxt = self.__Node(args[i])
self.__tail = self.__tail.nxt

def __iter__(self):
current = self.__head
while current is not None:
yield current.value
current = current.nxt

def __str__(self):
return f"[{' '.join(str(i) for i in self)}]"

def __len__(self):
return self.__length

def __index_check(self, index):
if not 0 <= index < self.__length:
raise IndexError

def append(self, value):
if self.__length > 0:
self.__tail.nxt = self.__Node(value)
self.__tail = self.__tail.nxt
else:
self.__head = self.__tail = self.__Node(value)
self.__length += 1

def get(self, index):
self.__index_check(index)
current = self.__head
for _ in range(index):
current = current.nxt
return current.value

def remove(self, index):
self.__index_check(index)
if self.__length == 1:
self.__head = self.__tail = None
elif index == 0:
self.__head = self.__head.nxt
else:
current = self.__head
for _ in range(index - 1):
current = current.nxt
current.nxt = current.nxt.nxt
if index == self.__length - 1:
self.__tail = current
self.__length -= 1


my_list = LinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)
print('Текущий список:', my_list)
print('Получение третьего элемента:', my_list.get(2))
print('Удаление второго элемента.')
my_list.remove(1)
print('Новый список:', my_list)
Надежда Красильникова Ученик (216) 1 год назад
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

def get(self, index):
t_node = self.head
for i in range(index):
t_node = t_ node.next
return t_node

my_list = LinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)
print('Текущий список:', my_list)
print('Получение третьего элемента:', my_list.get(2))
print('Удаление второго элемента.')
my_list.remove(1)
print('Новый список:', my_list)
Похожие вопросы