Algorithms and Data Structures

Linked List

When working with sequential data, we usually use lists/arrays to store and access the data. Yet, in some cases, it might be faster to use a linked list. Especially when the program should add or remove an element to the beginning of the list many times, linked lists can be faster to operate with.
A linked list is one of the most basic data structures. It holds a list of items, can update the list by adding elements, and access those - all just like an ordinary array/list. When working with linked lists we call each element a Node that holds data in it and a link to the next Node. In a singly linked list, each element (the Node) has a reference to the next node, and the last node has a reference to nothing - null. In literature, the first element of a singly linked list is known as the head, while the last element is known as the tail. One of the implementations of a linked list can have the following form:
class Node:
    def __init__(self, data):
        self.data = data               # Keep the data
        self.after = None              # Keep a link to the next element


class LinkedList:
    def __init__(self):
        self.head = None               # Initially there are no elements

    def append(self, data):            # Add a new element to the list
        new_node = Node(data)          # Create a node that holds `data`
        if self.head is None:          # If there are no elements in the list
            self.head = new_node       # Set the head to the new node
            return
        current = self.head            # Start traversing the list from the head
        while current.after:           # As long as we haven't reached the tail
            current = current.after    # Move to the next node
        current.after = new_node       # Update the tail and set it to the new node

    def print(self):                   # Print all the elements in the list
        current = self.head            # Start from the head
        while current:                 # As long as we haven't reached the end
            print(current.data, end='\n' if current.after is None else ' --> ')
            current = current.after    # Move to the next node


names = LinkedList()                   # Create an empty linked list
names.append('Anna')                   # Add Anna to the list
names.append('Bob')                    # Add Bob to the list
names.append('Sona')                   # Add Sona to the list
names.print()                          # Anna --> Bob --> Sona
notion image
In this implementation, we have two classes: Node and LinkedList. The Node class has two attributes: data and after. The data attribute holds the value of the node, while the after attribute holds the reference to the next node in the list. The LinkedList class has one attribute: head, which holds the reference to the first node in the list. The append() method is used to add a new node to the end of the list, and the print() method is used to print the elements of the list.

Doubly Linked List

Additionally, you can also have doubly linked lists, where each element has a reference to the next element and the previous element. This allows for traversing the list in both directions.

Linked List Analysis

A few important things to keep in mind when working with linked lists:
  • Accessing an element in a linked list takes time, as we need to traverse the list from the head to find the element.
  • If we know the Node after which we need to insert a new element, inserting it takes time, as we only need to update the references of the neighboring elements.
  • If we know the Node which needs to be removed, removing it takes time, as we only need to update the references of the neighboring elements.
  • Linked lists use more memory than arrays because of the extra reference stored in each element.

Challenge

Given n queries, you are asked to execute them. There are 2 types of queries:
  1. Insert a number at the beginning of the list.
  1. Print the whole list.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 1000) the number of queries.
The next n lines contain the queries - print if you should print the whole list, and insert x if you need to insert the number x at the beginning of the list ( ≤ x ≤ ).

Output

The program should correctly execute all the queries and print the list separating the elements by spaces.

Examples

Input
Output
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

To check your solution you need to sign in
Sign in to continue