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
Nodethat 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
In this implementation, we have two classes:
Nodeclass has two attributes:
dataattribute holds the value of the node, while the
afterattribute holds the reference to the next node in the list. The
LinkedListclass 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
Nodeafter 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
Nodewhich 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.
nqueries, you are asked to execute them. There are 2 types of queries:
- Insert a number at the beginning of the list.
- Print the whole list.
The first line of the input contains a single integer
n(1 ≤ n ≤ 1000) the number of queries.
nlines contain the queries -
insert xif you need to insert the number
xat the beginning of the list ( ≤ x ≤ ).
The program should correctly execute all the queries and print the list separating the elements by spaces.
6 insert 8 print insert 10 insert -2 insert -6 print
8 -6 -2 10 8
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB