880226. Insertion in deque
Basic
Insertion in deque
Slug: insertion-in-deque--151437
Difficulty: Basic
Topic Tags: Java, STL, Java-Collections, Data Structures
Company Tags: None
Summary
The problem is about inserting elements into a deque (double-ended queue) in a specific order. The key concepts involved are data structures and algorithms.
Detailed Explanation
Insertion into a deque can be done from both ends. We'll discuss the steps to perform insertion at both ends.
Insertion at Front
To insert an element at the front of the deque, we simply add it to the beginning of the queue. If the deque is empty, we create a new node and assign the element to it.
Insertion at Back
To insert an element at the back of the deque, we traverse the queue from the end until we reach the last node. We then create a new node and assign the element to it.
Time Complexity: O(n) where n is the number of elements in the deque. Space Complexity: O(1), as no extra space is used.
Optimized Solutions
Java
public class Main {
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>();
// Insertion at front
deque.addFirst(5);
System.out.println(deque); // [5]
deque.addFirst(4);
System.out.println(deque); // [4, 5]
// Insertion at back
deque.addLast(10);
System.out.println(deque); // [4, 5, 10]
deque.addLast(11);
System.out.println(deque); // [4, 5, 10, 11]
}
}