Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • 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: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

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