WORK IN PROGRESS
A data structure is a particular technique used to organize and store information in a computer with efficiency in mind. They can store both primitive and abstract data types and they are quite varied.I will be using C++ to demonstrate most examples , as that is my language of choice, and I will also be implementing some data structures myself. While most programming languages have them built-in, it's always good to know how everything works.
Arrays
<data_type> <array_name>[<size>];
int arr[10];
<data_type> <name>[<size1>][<size2>]
int m[10][10]
template<typename T>class Stack {public :Stack(); // constructor~Stack(); // destructorint size() const; // returns number of elements in stackbool isEmpty() const; // pretty obvious...const T& top() const; // returns a constant reference to the top objectvoid push(const T& obj); // adds an object to the topvoid pop(); // removes the object from top}
private :struct Element {T data;Element *below;};Element *top;int count;
template<typename T>class Stack{public : Stack(); ~Stack(); int size() const; bool isEmpty() const; const T& top() const; void push(const T& obj); void pop();private : struct Element { T data; Element *below; }; Element *top; int count;};
template<typename T> Stack::Stack(){top = NULL; // initializng the stack implies the top being nullcount = 0; // also count must be 0}
template<typename T> bool Stack<T>::isEmpty() const{ return top == NULL;}Returning the number of elements is pretty easy :template<typename T> int Stack<T>::size() const{return count;}
template<typename T> void Stack<T>::push(const T& ob){if(isEmpty()){top = new Element;top->data = ob;top->below = nullptr;count = 1;}else{Element * newElement = new Element;newElement->data = ob;newElement->below = top;top = p;++count;}}
template<typename T> void Stack<T>::pop(){if(isEmpty()) throw "Error. Empty stack.";Element * oldTop = top;top = top->below;delete oldTop;--count;}
template<typename T> const T& Stack<T>::top() const{if(isEmpty()) throw "Error. Empty stack.";return top->data;}Deconstructor :template<typename T> Stack<T>::~Stack(){while(top != nullptr){Element *oldTop = top;top = top->below;delete q;}}
template<typename T>class Stack{public :Stack();~Stack();int size() const;bool isEmpty() const;const T& top() const;void push(const T& obj);void pop();private :struct Element{T data;Element *below;};Element *top;int count;};template<typename T> Stack::Stack(){top = NULL;count = 0;}template<typename T> bool Stack<T>::isEmpty() const{return top == NULL;}template<typename T> int Stack<T>::size() const{return count;}template<typename T> void Stack<T>::push(const T& ob){if(isEmpty()){top = new Element;top->data = ob;top->below = nullptr;count = 1;}else{Element * newElement = new Element;newElement->data = ob;newElement->below = top;top = p;++count;}}template<typename T> void Stack<T>::pop(){if(isEmpty()) throw "Error. Empty stack.";Element * oldTop = top;top = top->below;delete oldTop;--count;}template<typename T> const T& Stack<T>::top() const{if(isEmpty()) throw "Error. Empty stack.";return top->data;}template<typename T> Stack<T>::~Stack(){while(top != nullptr){Element *oldTop = top;top = top->below;delete oldTop;}}
Stack< <data_type> > <variable_name>;
Stack<int> stack;
template<typename T>class Queue{public: Queue(); // Constructor ~Queue(); // Destructor void enqueue(const T& obj); // add an element in back void dequeue(); // remove element from front const T& front() const; // return reference to front const T& back() const; // return reference to back int size() const; // return number of elements bool isEmpty() const;private: struct Element { T data; Element *next; }; Element * front; Element * back; int count;};
template<typename T> Queue<T>::Queue(){ front = back = NULL; count = 0;}
template<typename T> bool Queue<T>::isEmpty() const{ return front == NULL;}
template<typename T> int Queue<T>::size() const{ return count;}
template<typename T> void Queue<T>::enqueue(const T& ob){ if(isEmpty()) { front = new Element; front->data = ob; front->next = nullptr; back = front; count = 1; } else { Element * p = new Element; p->data = ob; p->next = back; back = p; ++count; }}
template<typename T> void Queue<T>::dequeue(){ if(isEmpty()) throw "Error. Empty Queue."; Element * q = front; front = front->next; delete q; --count;}
template<typename T> const T& Queue<T>::front() const{ if(isEmpty()) throw "Error. Empty Queue."; return front->data;}
template<typename T> const T& Queue<T>::back() const{ if(isEmpty()) throw "Error. Empty Queue."; return back->data;}
template<typename T> Queue<T>::~Queue(){ while(front != NULL) { Element * q = front; front = front->next; delete q; }}
template<typename T>class Queue{public: Queue(); ~Queue(); void enqueue(const T& obj); void dequeue(); const T& front() const; const T& back() const; int size() const; bool isEmpty() const;private: struct Element { T data; Element * next; }; Element *front; Element *back; int count;};template<typename T> Queue<T>::Queue(){ front = back = NULL; count = 0;}template<typename T> bool Queue<T>::isEmpty() const{ return front == NULL;}template<typename T> int Queue<T>::size() const{ return count;}template<typename T> void Queue<T>::enqueue(const T& ob){ if(isEmpty()) { front = new Element; front->data = ob; front->next = nullptr; back = front; count = 1; } else { Element * p = new Element; p->data = ob; p->next = NULL; back->next = p; back = p; ++count; }}template<typename T> void Queue<T>::dequeue(){ if(isEmpty()) throw "Error. Empty Queue."; Element * q = front; front = front->next; delete q; --count;}template<typename T> const T& Queue<T>::front() const{ if(isEmpty()) throw "Error. Empty Queue."; return front->data;}template<typename T> const T& Queue<T>::back() const{ if(isEmpty()) throw "Error. Empty Queue."; return back->data;}template<typename T> Queue<T>::~Queue(){ while(front != NULL) { Element * q = front; front = front->next; delete q; }}
class Lista{public : struct Iterator; Lista() { head = tail = NULL; } ~Lista() { if(!isEmpty()) clear(); } void push_back(int elem); void push_front(int elem); void insert_before(int elem, Iterator nod); void insert_after(int elem, Iterator nod); void pop_front(); void pop_back(); void remove(Iterator nod); bool isEmpty() const { return head == NULL; } void clear(); Iterator front() const { return Iterator(head); } Iterator end() const { return Iterator(NULL); } Iterator search(int value) const;private : struct Nod { int data; Nod *next; }; Nod *head; Nod *tail;public : struct Iterator { friend class Lista; Iterator() { list = NULL; } Iterator(Nod *ls) { list = ls; } int& operator*() { if(list != NULL) return list->data; else throw "Null iterator!"; } //postfix Iterator operator++(int) { Iterator temp = *this; ++(*this); return temp; } //prefix Iterator& operator++() { list = list->next; return *this; } bool operator==(const Iterator& it) const { if(it.list == this->list) return true; else return false; } bool operator!=(const Iterator& it) const { if(!(it==*this)) return true; else return false; } private : Nod *list; };};void Lista::push_front(int elem){ if(isEmpty()) { head = new Nod; head -> data = elem; head -> next = NULL; tail = head; } else { Nod *nod = new Nod; nod->data=elem; nod->next=head; head=nod; }}void Lista::push_back(int elem){ if(isEmpty()) { head = new Nod; head -> data = elem; head -> next = NULL; tail = head; } else { Nod *nod = new Nod; nod->data=elem; nod->next=NULL; tail->next = nod; tail = nod; }}void Lista::insert_after(int elem, Iterator nod){ Nod *newNod = new Nod; newNod -> data = elem; newNod -> next = nod.list->next; nod.list->next = newNod; if(nod.list == tail) tail = newNod;}void Lista::insert_before(int elem, Iterator nod){ Nod *newNod = new Nod; newNod -> data = nod.list->data; nod.list->data=elem; newNod -> next = nod.list->next; nod.list->next = newNod; if(nod.list == tail) tail = newNod;}Lista::Iterator Lista::search(int value) const{ for(Nod* it = head; it != NULL; it = it->next) { if(it->data == value) return Iterator(it); } return end();}void Lista::pop_front(){ if(isEmpty()) throw "Empty List"; if(head==tail) delete head; head = tail = NULL; Nod *temp = head; head = head->next; delete temp;}void Lista::pop_back(){ if(isEmpty()) throw "Empty List"; if(head==tail) delete head; head = tail = NULL; Nod *pred; for(pred = head; pred->next->next != NULL; pred = pred->next); pred->next = NULL; delete tail; tail = pred;}void Lista::clear(){ Nod *it = head, *temp; while(it!=NULL) { temp = it; it = it->next; delete temp; } head = tail = NULL;}
class ListD{private : struct Node { int data; Node *next; Node *prev; }; Node *tail; Node *head;public : struct Iterator { private: Node * list; public: friend class List; Iterator() { list == NULL; } Iterator(Node *ls) { list = ls; } int& operator*() const { if(list!=NULL) return list->data; else throw "Null Iterator"; } Iterator& operator++() { list = list->next; return *this; } Iterator operator++(int) { Iterator temp = *this; ++(*this); return temp; } bool operator==(const Iterator& it) const { if(it.list == this->list) return true; else return false; } bool operator!=(const Iterator& it) const { if(!(it==*this)) return true; else return false; } }; bool isEmpty() { return head == NULL; } List() { head=tail=NULL; } ~List() { if(!isEmpty())clear(); } Iterator end() const { return Iterator(NULL); } Iterator front() const { return Iterator(head); } Iterator search(int value) const { for(Node *i = head; i !=NULL; i=i->next) if(value==i->data) return Iterator(i); } void pop_back() { if(isEmpty()) throw "Empty List"; else if(head==tail) delete head; else { Node *temp = tail->prev; delete tail; temp->next = NULL; tail = temp; } } void pop_front() { if(isEmpty()) throw "Empty List"; else if(head==tail) delete head; else { Node *temp = head->next; delete head; temp->prev = NULL; head = temp; } } void remove(Iterator node) { if(isEmpty()) throw "Empty List"; else if(head==tail) { delete head; head=tail=NULL; return; } else if(node==this->end()) { pop_back(); } else if(node==this->front()) { pop_front(); } else { node.list->prev->next= node.list->next; node.list->next->prev = node.list->prev; } } void insert_after(int value, Iterator node) { Node *newNode = new Node; newNode->data=value; newNode->prev=node.list; newNode->next=node.list->next; node.list->next->prev=newNode; node.list->prev->next=newNode; } void insert_before(int value, Iterator node) { Node *newNode = new Node; newNode->data=value; newNode->next=node.list; newNode->prev=node.list->prev; node.list->prev->next=newNode; node.list->next->prev=newNode; } void push_back(int value) { if(isEmpty()) { head = new Node; head->data=value; head->next=NULL; head->prev=NULL; tail=head; } else { Node *newNode = new Node; newNode->data=value; newNode->next=NULL; newNode->prev=tail; tail->next=newNode; tail=newNode; } } void push_front(int value) { if(isEmpty()) { Node newNode; head = tail = &newNode; newNode.data = value; newNode.prev = NULL; newNode.next = NULL; } else { Node newNode; newNode.data = value; newNode.prev=NULL; newNode.next = head; head->prev = &newNode; head = &newNode; } } void clear() { Node *i = head, *temp; while(i!=NULL) { temp=i; i=i->next; delete temp; } head=tail=NULL; } void print() { for(List::Iterator it = this->front(); it!=this->end(); it++)std::cout << *it << ' '; std::cout<<"\n"; } void swap(Iterator node1, Iterator node2){ int temp = node1.list->data; node1.list->data = node2.list->data; node2.list->data=temp; } void sort(){ bool is_sorted; do { is_sorted = true; for(Iterator it = this->front(); Iterator(it.list->next)!=this->end(); it++) if(it.list->data > it.list->next->data) { is_sorted = false; swap(it.list,it.list->next); } } while(!is_sorted); }};
template <class T>class List{ struct Node { T data; Node *prev; Node *next; }; Node *head; Node *tail;public: struct Iterator { private: Node *node; public: friend class List; Iterator() { node = NULL; } Iterator(Node *n) { node = n; } T& operator*() const { if(node!=NULL) return node->data; else throw "Null operator"; } Iterator& operator++() { if(node->next==NULL)node=NULL; //throw "Iterator out of bounds"; else { node=node->next; return *this; } } Iterator operator++(int) { if(node->next==NULL)node=NULL ;//throw "Iterator out of bounds"; else { Iterator temp = *this; ++(*this); return temp; } } Iterator& operator--() { if(node->prev==NULL)node=NULL ;//throw "Iterator out of bounds"; else { node = node->prev; return *this; } } Iterator operator--(int) { if(node->prev==NULL)node=NULL ;//throw "Iterator out of bounds"; else { Iterator temp = *this; --(*this); return temp; } } bool operator==(const Iterator& it) const { if(it.node == this->node)return true; else return false; } bool operator!=(const Iterator& it) const { if(!(it==*this)) return true; else return false; } }; bool isEmpty() { return head ==NULL; } List() { head=tail=NULL; } ~List() { if(!isEmpty()) clear(); } void clear() { Node *i = head, *temp; while(i!=NULL) { temp = i; i=i->next; delete temp; } head=tail=NULL; } Iterator end() const { return Iterator(tail); } Iterator front() const { return Iterator(head); } void pop_back() { if(isEmpty()) throw "Empty List"; else if(head==tail) delete head; else { Node *temp = tail->prev; delete tail; temp->next = NULL; tail=temp; } } void pop_front() { if(isEmpty()) throw "Empty List"; else if(head==tail) delete head; else { Node *temp = head->next; delete head; temp->prev = NULL; head=temp; } } void remove(Iterator it) { if(isEmpty()) throw "Empty List"; else if(head==tail) { delete head; head = tail = NULL; return; } else if(it==this->end()) pop_back(); else if(it==this->front()) pop_front(); else { it.node->prev->next = it.node->next; it.node->next->prev = it.node->prev; delete it.node; } } void push_back(T value) { if(isEmpty()) { head = new Node; head->data = value; head->next=NULL; head->prev=NULL; tail=head; } else { Node *newNode = new Node; newNode->data = value; newNode->next=NULL; newNode->prev=tail; tail->next=newNode; tail=newNode; } } void push_front(T value) { if(isEmpty()) { head = new Node; head->data = value; head->next=NULL; head->prev=NULL; tail=head; } else { Node *newNode = new Node; newNode->data = value; newNode->prev=NULL; newNode->next=head; head->prev=newNode; head=newNode; } } void swap(Iterator node1, Iterator node2) { T temp = node1.node->data; node1.node->data = node2.node->data; node2.node->data=temp; } void insert_before(T value, Iterator it) { Node *newNode = new Node; newNode->data = value; it.node->prev->next = newNode; newNode->prev=it.node->prev; it.node->prev=newNode; newNode->next=it.node; } void insert_after(T value, Iterator it) { Node *newNode = new Node; newNode->Data = value; newNode->prev=it.node; newNode->next=it.node->next; it.node->next->prev=newNode; it.node->next=newNode; }};
smjpl got a reaction from NaLu in computer on desk
smjpl got a reaction from dalekphalm in T-Mobile going after data 'thieves' who abuse unlimited data
smjpl got a reaction from EChondo in T-Mobile going after data 'thieves' who abuse unlimited data
smjpl got a reaction from iStartedTheWar in T-Mobile going after data 'thieves' who abuse unlimited data
smjpl reacted to ShadowCaptain in Is it time to upgrade my i7 2600K to i5 6600K ?
smjpl got a reaction from SaperPL in How hard is an electrical engineering degree?
smjpl got a reaction from Bensemus in Research lab accidentally creates longer lasting Li-Ion battery
smjpl got a reaction from Embattled in "Anonymous" DDOS attacked largest internet provider of the Netherlands!
smjpl got a reaction from zMeul in "Anonymous" DDOS attacked largest internet provider of the Netherlands!
smjpl got a reaction from ChineseChef in [UPDATE] The Ashley Madison hackers just released all of their stolen data
smjpl got a reaction from SImoHayha in Research lab accidentally creates longer lasting Li-Ion battery
smjpl got a reaction from Syntaxvgm in Research lab accidentally creates longer lasting Li-Ion battery
smjpl got a reaction from LAwLz in [UPDATE] The Ashley Madison hackers just released all of their stolen data
smjpl got a reaction from minibois in Is there any hobby that doesn't cost money?
smjpl got a reaction from W-L in Is there any hobby that doesn't cost money?
