Связный список
При работе с последовательными данными мы обычно используем списки или массивы, чтобы хранить и получать к ним доступ. Однако в некоторых случаях использование связного списка может быть быстрее. Особенно когда программе часто нужно добавлять или удалять элемент в начале списка — в таких ситуациях связные списки могут работать эффективнее.
Связный список — одна из самых простых структур данных. Он хранит набор элементов, может обновлять их (например, добавлять новые элементы) и предоставляет доступ к ним, аналогично обычному массиву или списку. В контексте связных списков каждый элемент называют
Node (узел), который содержит данные и ссылку на следующий Node. В односвязном списке каждый узел имеет ссылку на следующий, а последний элемент не ссылается ни на что (то есть указывает на null). В литературе первый элемент односвязного списка называют головой (head), а последний — хвостом (tail). Одна из возможных реализаций связного списка может выглядеть так:class Node:
def __init__(self, data):
self.data = data # Хранит данные
self.after = None # Хранит ссылку на следующий элемент
class LinkedList:
def __init__(self):
self.head = None # Сначала список пуст
def append(self, data): # Добавить новый элемент в конец списка
new_node = Node(data) # Создаем узел, содержащий data
if self.head is None: # Если в списке еще нет элементов
self.head = new_node # Делаем голову новым узлом
return
current = self.head # Начинаем обход списка с головы
while current.after: # Пока не дойдем до хвоста
current = current.after # Переходим к следующему узлу
current.after = new_node # Обновляем хвост, ссылаясь на новый элемент
def print(self): # Вывести все элементы списка
current = self.head # Начинаем с головы
while current: # Пока не достигнут конец списка
print(current.data, end='\n' if current.after is None else ' --> ')
current = current.after # Переходим к следующему узлу
names = LinkedList() # Создаем пустой связный список
names.append('Anna') # Добавляем в список элемент Anna
names.append('Bob') # Добавляем в список элемент Bob
names.append('Sona') # Добавляем в список элемент Sona
names.print() # Anna --> Bob --> Sona
В этой реализации мы используем два класса:
Node и LinkedList. В классе Node есть два атрибута: data и after. data хранит значение, а after хранит ссылку на следующий узел списка. Класс LinkedList содержит атрибут head, который ссылается на первый элемент списка. Метод append() добавляет новый узел в конец списка, а метод print() выводит элементы списка.Двусвязный список
Кроме того, существуют двусвязные списки, где каждый элемент имеет ссылку и на следующий, и на предыдущий элемент. Это позволяет обходить список в обоих направлениях.
Анализ связного списка
Несколько важных моментов при работе со связными списками:
- Доступ к элементу в связном списке занимает время , поскольку для нахождения элемента нам приходится идти от головы к нужному узлу по всей цепочке ссылок.
- Если мы знаем
Node, после которого нужно вставить новый элемент, вставка займет , так как достаточно обновить ссылки соседних элементов.
- Если мы знаем
Node, который необходимо удалить, удаление также займет , так как мы только меняем ссылки соседних элементов.
- Связные списки занимают больше памяти, чем массивы, из-за дополнительной ссылки, хранящейся в каждом элементе.
Задача
Дано
n запросов, которые нужно выполнить. Существует 2 типа запросов:- Вставить число в начало списка.
- Вывести весь список.
Входные данные
В первой строке содержится одно целое число
n (1 ≤ n ≤ 1000) — количество запросов.В следующих
n строках содержатся запросы: print означает, что нужно вывести весь список, а insert x означает, что нужно вставить число x в начало списка ( ≤ x ≤ ).Выходные данные
Необходимо корректно выполнить все запросы и вывести список, разделяя элементы пробелами.
Примеры
Вход | Выход |
6
insert 8
print
insert 10
insert -2
insert -6
print | 8
-6 -2 10 8 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB