Design a Data structure which supports insertion and first non-repeating element in O(1) time. Operations that are supported by the data structure:
- Insertion: Insert a element into the data structure.
- First non-repeating Element: First non-repeating element into the array.
Note: If there is no non-repeating element in the array then print -1.
Consider the following custom Data structure:
Insert(4): [4]
Insert(1): [4, 1]
Insert(4): [4, 1, 4]
First_Non_Repeating Element: 1
The idea is to use Doubly Linked List and a Hash-map to maintain the frequency of the elements of the array. Below is the use-cases of the Hash-map and Doubly-Linked List in this Data-structure:
- Doubly Linked-List: to keep track of the non-repeating elements in the array.
- Hash-map: To keep track of the occurrence of the elements and the address of non-repeating elements in the Doubly Linked-List
Below is the illustration of the operations:
- Insertion: Insert an element into the array and check the frequency of the element into the map. If it is previously occurred then remove the element from the Doubly Linked List with the help of the addresses stored in the hash-map. Finally, increase the occurrence of the element into the hash-map.
- First Non-repeating element: First Non-repeating element of the array will be the first element of the Doubly Linked List.
Advantages of this Data-structure:
- Insertion and First Non-repeating element in O(1) time.
Disadvantages of this Data-structure:
- Cannot Keep track of the order of the elements.
- Custom Data-structures will need custom Hasp-map to store the elements into the map.
- Memory Inefficient
Below is the implementation of the above approach:
C++
// C++ implementation of a structure// which supports insertion, deletion// and first non-repeating element // in constant time#include <bits/stdc++.h>using namespace std;// Node for doubly // linked liststruct node { // Next pointer struct node* next; // Previous pointer struct node* prev; // Value of node int data; };// Head and tail pointer // for doubly linked liststruct node *head = NULL, *tail = NULL;// Occurrences map container // to count for occurrence // of the elementmap<int, int> occurrences;// Address map container // to store nodes of the // list which are uniquemap<int, node*> address;// Function to insert the element// into the given data-structurevoid insert(int value){ // Increasing count of // value to be inserted occurrences[value]++; // If count of element is // exactly 1 and is yet // not inserted in the list, // we insert value in list if (occurrences[value] == 1 && address.find(value) == address.end()) { struct node* temp = (struct node*)malloc(sizeof(struct node)); temp->next = NULL; temp->prev = NULL; temp->data = value; // Storing node mapped // to its value in // address map container address[value] = temp; // Inserting first element if (head == NULL) { head = temp; tail = temp; } else { // Appending // element at last tail->next = temp; temp->prev = tail; tail = temp; } } // if occurrence of particular // value becomes >1 and, // it is present in address // container(which means // it is not yet deleted) else if (occurrences[value] > 1 && address.find(value) != address.end()) { // Taking node to be deleted struct node* temp = address[value]; // Erasing its value from // map to keep track that // this element is deleted address.erase(value); // Deleting node in // doubly linked list if (temp == head) { temp = head; head = head->next; free(temp); } else if (temp == tail) { temp = tail; tail->prev->next = NULL; free(temp); } else { temp->next->prev = temp->prev; temp->prev->next = temp->next; free(temp); } }}// Function to find the first// unique element from listvoid findUniqueNumber(){ // No element in list if (head == NULL) cout << "-1\n"; // Head node contains // unique number else cout << head->data << "\n";}// Driver Codeint main(){ // Inserting element in list insert(4); insert(1); insert(4); // Finding the first // unique number findUniqueNumber(); cout << "\n"; return 0;} |
Java
// Java implementation of a structure// which supports insertion, deletion// and first non-repeating element// in constant timeimport java.util.HashMap;// Node for doubly linked listclass Node { // Next pointer Node next; // Previous pointer Node prev; // Value of node int data; // Constructor Node(int data) { this.data = data; this.next = null; this.prev = null; }}public class Main { // Head and tail pointers for doubly linked list static Node head = null, tail = null; // Occurrences map container to count for occurrence of // the element static HashMap<Integer, Integer> occurrences = new HashMap<>(); // Address map container to store nodes of the list // which are unique static HashMap<Integer, Node> address = new HashMap<>(); // Function to insert the element into the given // data-structure static void insert(int value) { // Increasing count of value to be inserted occurrences.put( value, occurrences.getOrDefault(value, 0) + 1); // If count of element is exactly 1 and is yet not // inserted in the list, we insert value in list if (occurrences.get(value) == 1 && !address.containsKey(value)) { Node temp = new Node(value); // Storing node mapped to its value in address // map container address.put(value, temp); // Inserting first element if (head == null) { head = temp; tail = temp; } else { // Appending element at last tail.next = temp; temp.prev = tail; tail = temp; } } // If occurrence of particular value becomes >1 and, // it is present in address container(which means it // is not yet deleted) else if (occurrences.get(value) > 1 && address.containsKey(value)) { // Taking node to be deleted Node temp = address.get(value); // Erasing its value from map to keep track that // this element is deleted address.remove(value); // Deleting node in doubly linked list if (temp == head) { head = head.next; head.prev = null; } else if (temp == tail) { tail = tail.prev; tail.next = null; } else { temp.next.prev = temp.prev; temp.prev.next = temp.next; } } } // Function to find the first unique element from list static void findUniqueNumber() { // No element in list if (head == null) System.out.println("-1"); // Head node contains unique number else System.out.println(head.data); } // Driver Code public static void main(String[] args) { // Inserting element in list insert(4); insert(1); insert(4); // Finding the first unique number findUniqueNumber(); System.out.println(); }}// This code is contributed by rutikbhosale |
Python3
# Python3 implementation of a structure# which supports insertion, deletion# and first non-repeating element # in constant time # Node for doubly # linked listclass node: def __init__(self): # Next pointer self.next = None # Previous pointer self.prev = None # Value of node self.data = 0 # Head and tail pointer # for doubly linked listhead = Nonetail = None # Occurrences map container # to count for occurrence # of the elementoccurrences = dict() # Address map container # to store nodes of the # list which are uniqueaddress = dict() # Function to insert the element# into the given data-structuredef insert(value): global head, tail # Increasing count of # value to be inserted if value not in occurrences: occurrences[value] = 0 occurrences[value] += 1 # If count of element is # exactly 1 and is yet # not inserted in the list, # we insert value in list if (value in occurrences and occurrences[value] == 1 and value not in address): temp = node() temp.next = None temp.prev = None temp.data = value # Storing node mapped # to its value in # address map container address[value] = temp # Inserting first element if (head == None): head = temp tail = temp else: # Appending # element at last tail.next = temp temp.prev = tail tail = temp # If occurrence of particular # value becomes >1 and, # it is present in address # container(which means # it is not yet deleted) elif (value in occurrences and occurrences[value] > 1 and value in address): # Taking node to be deleted temp = address[value] # Erasing its value from # map to keep track that # this element is deleted address.pop(value) # Deleting node in # doubly linked list if (temp == head): temp = head head = head.next del(temp) elif (temp == tail): temp = tail tail.prev.next = None del(temp) else: temp.next.prev = temp.prev temp.prev.next = temp.next del(temp) # Function to find the first# unique element from listdef findUniqueNumber(): global head # No element in list if (head == None): print(-1) # Head node contains # unique number else: print(head.data) # Driver Codeif __name__=='__main__': # Inserting element in list insert(4) insert(1) insert(4) # Finding the first # unique number findUniqueNumber() # This code is contributed by rutvik_56 |
C#
// C# implementation of a structure// which supports insertion, deletion// and first non-repeating element// in constant timeusing System;using System.Collections.Generic;// Node for doubly linked listclass Node { // Next pointer public Node next; // Previous pointer public Node prev; // Value of node public int data; // Constructor public Node(int data) { this.data = data; this.next = null; this.prev = null; }}class MainClass { // Head and tail pointers for doubly linked list static Node head = null, tail = null; // Occurrences map container to count for occurrence of // the element static Dictionary<int, int> occurrences = new Dictionary<int, int>(); // Address map container to store nodes of the list // which are unique static Dictionary<int, Node> address = new Dictionary<int, Node>(); // Function to insert the element into the given // data-structure static void Insert(int value) { // Increasing count of value to be inserted if (occurrences.ContainsKey(value)) { occurrences[value]++; } else { occurrences[value] = 1; } // If count of element is exactly 1 and is yet not // inserted in the list, we insert value in list if (occurrences[value] == 1 && !address.ContainsKey(value)) { Node temp = new Node(value); // Storing node mapped to its value in address // map container address[value] = temp; // Inserting first element if (head == null) { head = temp; tail = temp; } else { // Appending element at last tail.next = temp; temp.prev = tail; tail = temp; } } // If occurrence of particular value becomes >1 and, // it is present in address container(which means it // is not yet deleted) else if (occurrences[value] > 1 && address.ContainsKey(value)) { // Taking node to be deleted Node temp = address[value]; // Erasing its value from map to keep track that // this element is deleted address.Remove(value); // Deleting node in doubly linked list if (temp == head) { head = head.next; head.prev = null; } else if (temp == tail) { tail = tail.prev; tail.next = null; } else { temp.next.prev = temp.prev; temp.prev.next = temp.next; } } } // Function to find the first unique element from list static void FindUniqueNumber() { // No element in list if (head == null) Console.WriteLine("-1"); // Head node contains unique number else Console.WriteLine(head.data); } // Driver Code public static void Main(string[] args) { // Inserting element in list Insert(4); Insert(1); Insert(4); // Finding the first unique number FindUniqueNumber(); Console.WriteLine(); }}// This code is contributed by user_dtewbxkn77n |
Javascript
// Node for doubly // linked listclass Node { constructor() { // Next pointer this.next = null; // Previous pointer this.prev = null; // Value of node this.data = 0; }}// Head and tail pointer // for doubly linked listlet head = null;let tail = null;// Occurrences map container // to count for occurrence // of the elementconst occurrences = new Map();// Address map container // to store nodes of the // list which are uniqueconst address = new Map();// Function to insert the element// into the given data-structurefunction insert(value) { // Increasing count of // value to be inserted if (!occurrences.has(value)) { occurrences.set(value, 0); } occurrences.set(value, occurrences.get(value) + 1); // If count of element is // exactly 1 and is yet // not inserted in the list, // we insert value in list if ( occurrences.has(value) && occurrences.get(value) === 1 && !address.has(value) ) { const temp = new Node(); temp.next = null; temp.prev = null; temp.data = value; // Storing node mapped // to its value in // address map container address.set(value, temp); // Inserting first element if (head === null) { head = temp; tail = temp; } else { // Appending // element at last tail.next = temp; temp.prev = tail; tail = temp; } } // If occurrence of particular // value becomes >1 and, // it is present in address // container(which means // it is not yet deleted) else if ( occurrences.has(value) && occurrences.get(value) > 1 && address.has(value) ) { // Taking node to be deleted const temp = address.get(value); // Erasing its value from // map to keep track that // this element is deleted address.delete(value); // Deleting node in // doubly linked list if (temp === head) { head = head.next; head.prev = null; temp.next = null; temp.prev = null; } else if (temp === tail) { tail = tail.prev; tail.next = null; temp.next = null; temp.prev = null; } else { temp.prev.next = temp.next; temp.next.prev = temp.prev; temp.next = null; temp.prev = null; } }}// Function to find the first// unique element from listfunction findUniqueNumber() { // No element in list if (head === null) { console.log(-1); } else { // Head node contains // unique number console.log(head.data); }}// Driver Code// Inserting element in listinsert(4);insert(1);insert(4);// Finding the first // unique numberfindUniqueNumber();// Contributed by adityasharmadev01 |
Output:
1
Time Complexity: O(1) for insertion and deletion operations
Auxiliary Space: O(n), where n is the number of unique elements
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
