Basic Data Structures and their types

Basic Data Structures:

There are five fundamental data structures: arrays, stacks, linked lists, queues, and deque (pronounced as deck, a double ended queue).

Arrays
:

Array is the most helpful data structures, however, this data structure will almost for all the time employed in all contest problems. At first let’s look at the good side: if index is recognized, searching an element in an array is much fast, O(1), this good for looping or iteration. Array can as well be employed to implement other sophisticated data structures like stacks, queues, and hash tables. However, being the simplest data structure does not mean that array is proficient. In some situations array can be very inefficient. Furthermore, in standard array, the size is fixed. When you do not know the input size beforehand, it might be wiser to employ vector (that is, a resizable array). Array as well suffer a very slow insertion in ordered array, other slow searching in unordered array, and inevitable slow deletion since you have to shift all elements.

1337_dsa1.jpg

We generally use one-dimensional array for the standard use and 2-dimensional array to symbolize matrices, board, or anything which is 2-dimensional. Three-dimensional is hardly ever employed to model 3D conditions.

Row major, cache-friendly; use this technique to access all items in an array sequentially.

for (i=0; i<numRow; i++)    // ROW FIRST = EFFECTIVE
   for (j=0; j<numCol; j++)
      array[i][j] = 0;


Column major, NOT cache-friendly, DO NOT employ this technique or you will get much poor performance. Why? You will learn this in Computer Architecture course. For now just take note that computer access the array data in row major.

for (j=0; j<numCol; j++)    // COLUMN FIRST = INEFFECTIVE
   for (i=0; i<numRow; i++)
      array[i][j] = 0;


Vector Trick - A resizable array:

Static array consists of a drawback whenever the size of input is not recognized beforehand. If that is the case, you might want to consider vector, that is, a resizable array.

There are other data structures that offer much more proficient re-sizing capability such as Linked-List and so forth.

=> TIPS: UTILIZING C++ VECTOR STL

C++ STL has vector template for you.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
void main() {
  // just do this, write vector<the type you want,
  // in this case, integer> and the vector name
  vector<int> v;
  // try inserting seven different integers, not ordered
  v.push_back(3); v.push_back(1); v.push_back(2);
  v.push_back(7); v.push_back(6); v.push_back(5);
  v.push_back(4);
// to access the element, you require an iterator...
  vector<int>::iterator i;
  printf("Unsorted version\n");
  // start with 'begin', end with 'end', advance with i++
  for (i = v.begin(); i!= v.end(); i++)
    printf("%d ",*i); // iterator's pointer hold the value
  printf("\n");
  sort(v.begin(),v.end()); // default sort, ascending
  printf("Sorted version\n");
  for (i = v.begin(); i!= v.end(); i++)
    printf("%d ",*i); // iterator's pointer hold the value
  printf("\n");
}

Linked List:

Motivation for employing linked list: Array is static and even although it has O(1) access time when index is recognized, Array should shift its elements when an item is going to be inserted or deleted and this is completely ineffective. Array can’t be re-sized when it is full.

Linked-list can encompass a very fast deletion and insertion. The physical position of data in linked list can be anyplace in the memory however each node should know which portion in memory is the subsequent item after them.

The linked list can be as big as you wish as long there is enough memory. The side effect of Linked-list is there will be wasted memory whenever a node is "deleted" (that is, only flagged as deleted). This wasted memory will just be freed up whenever garbage collector doing its action (based on compiler/Operating System employed).

Linked list is a data structure which is commonly employed since of its dynamic feature. Linked list is not employed for fun; it is very complex and has a tendency to make run time memory access error). Some programming languages like Java and C++ really support Linked-list implementation via API (abbreviated as Application Programming Interface) and STL (abbreviated as Standard Template Library).

Linked-list is composed of a data and at times pointer to the data and a pointer to next item. In Linked list, you can simply find an item via complete search from head till it found the item or until tail (not found). This is the horrible side for Linked list, particularly for a very long list. And for insertion in the Ordered Linked List, we have to search for suitable place employing Complete Search technique, and this is slow too. (There are certain tricks to enhance searching in Linked List, like remembering references to particular nodes and so on).

Variations of Linked List:

With tail pointer: Rather than standard head pointer, we employ the other pointer to keep track the last item. This is helpful for queue-like structures as in Queue, we enter Queue from rear (or tail) and delete item from the front (or head).

With dummy node (or sentinels): This variation is for making our code simpler (I prefer this way), this can simplify empty list code and inserting to the front of list code.

Doubly Linked List: Proficient when we require to traverse the list in both the direction (that is, forward and backward). Each node now consists of 2 pointers, one point to the subsequent item, and the other one point to the prior item. We require dummy head and dummy tail for this kind of linked list.

=> TIPS: UTILIZING C++ LIST STL

A demo on the usage of STL list. The underlying data structure is the doubly link list.

#include <stdio.h>
// this is where list implementation resides
#include <list>
// use this to avoid specifying "std::" everywhere
using namespace std;
// just do this, write list<the type you want,
// in this case, integer> and the list name
list<int> l;
list<int>::iterator i;
void print() {
  for (i = l.begin(); i != l.end(); i++)
    printf("%d ",*i); // remember... use pointer!!!
  printf("\n");
}
void main() {
  // try inserting eight different integers, has duplicates
  l.push_back(3); l.push_back(1); l.push_back(2);
  l.push_back(7); l.push_back(6); l.push_back(5);
  l.push_back(4); l.push_back(7);
  print();
l.sort(); // sort the list, wow sorting linked list...
  print();
  l.remove(3); // eliminate element '3' from the list
  print();
  l.unique(); // eliminate duplicates in SORTED list!!!
  print();
  i = l.begin(); // set iterator to head of the list
  i++; // 2nd node of the list
  l.insert(i,1,10); // insert 1 copy of '10' here
  print();
}


Stack:

It is a data structure which only permits insertion (or push) and deletion (or pop) from the top only.

This behavior is termed as Last in First out (or LIFO), alike to normal stack in the actual world.

Important stack operations:

A) Push (C++ STL: push())
It adds a new item at the top of stack.

B) Pop (C++ STL: pop())
It retrieves and eliminates the top of stack.

C) Peek (C++ STL: top())
It retrieves the top of a stack devoid of deleting it.

D) IsEmpty (C++ STL: empty())
Finds out whether a stack is empty.

Some stack applications:

A) To model "real stack" in computer world: Procedure Calling, Recursion and so on.
B) Checking palindrome (though checking palindrome employing Queue & Stack is 'stupid').
C) To read an input from the keyboard in text editing by backspace key. 
D) To reverse the input data, (that is, the other stupid idea to employ stack for reversing data).
E) Checking the balanced parentheses.
F) Postfix computation.
G) Transforming mathematical expressions. Infix, Prefix or Postfix.

Some stack implementations:

A) Linked List with the head pointer only (Best).
B) Array
C) Resizable Array

=> TIPS: UTILIZING C++ STACK STL

Stack is not hard to implement. Stack STL's implementation is much efficient, even although it will be slightly slower than your custom prepared stack.

#include <stdio.h>
#include <stack>
using namespace std;
void main() {
  // just do this, write stack<the type you want,
  // in this case, integer> and the stack name
  stack<int> s;
  // try inserting seven different integers, not ordered
  s.push(3); s.push(1); s.push(2);
  s.push(7); s.push(6); s.push(5);
  s.push(4);
  // the item which is inserted first will come out last
  // Last In First Out (LIFO) order...
  while (!s.empty()) {
    printf("%d ",s.top());
    s.pop();
  }
  printf("\n");}


Queue:

Data structures which only permit insertion from the back (or rear), and only permit deletion from the head (or front). This behavior is termed as First in First out (or FIFO), alike to normal queue in the real world.

Significant queue operations:

1) Enqueue (C++ STL: push())
It adds new item at the back (or rear) of the queue.

2) Dequeue (C++ STL: pop())
It retrieves and eliminates the front of a queue at the back (or rear) of a queue.

3) Peek (C++ STL: top())
It retrieves the front of queue devoid of deleting it.

4) IsEmpty (C++ STL: empty())
It determines whether the queue is empty.

=> TIPS: UTILIZING C++ QUEUE STL

The standard queue is as well not hard to implement. Again, why mess yourself, just utilize C++ queue STL.

#include <stdio.h>
#include <queue>
// employ this to avoid specifying "std::" everywhere
using namespace std;
void main() {
  // just do this, write queue<the type you want,
  // in this case, integer> and the queue name
  queue<int> q;
  // try inserting seven distinct integers, not ordered
  q.push(3); q.push(1); q.push(2);
  q.push(7); q.push(6); q.push(5);
  q.push(4);
  // the item which is inserted first will come out first
  // First In First Out (FIFO) order...
  while (!q.empty()) {
    // notice that this is not "top()" !!!
    printf("%d ",q.front());
    q.pop();
  }
 printf("\n");}

Latest technology based Programming Languages Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Programming Languages help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Programming Languages, project ideas and tutorials. We provide email based Programming Languages help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Programming Languages. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Programming Languages Homework help and assignment help services. They use their experience, as they have solved thousands of the Programming Languages assignments, which may help you to solve your complex issues of Programming Languages. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.