What Is Data Structure and Algorithm [full explained with types]

DATA STRUCTURE: -Structural representation of data items in primary memory to do storage &
retrieval operations efficiently.

--FILE STRUCTURE: Representation of items in secondary memory.
While designing data structure following perspectives to be looked after.
i. Application(user) level: Way of modeling real-life data in specific context.
ii. Abstract(logical) level: Abstract collection of elements & operations.
iii. Implementation level: Representation of structure in programming language.
Data structures are needed to solve real-world problems. But while choosing implementations
for it, its necessary to recognize the efficiency in terms of TIME and SPACE.

TYPES:-

i. Simple: built from primitive data types like int, char & Boolean.
eg: Array & Structure
ii. Compound: Combined in various ways to form complex structures.
1:Linear: Elements share adjacency relationship& form a sequence.
Eg: Stack, Queue , Linked List
 2: Non-Linear: Are multi-level data structure. eg: Tree, Graph.

ABSTRACT DATA TYPE :

Specifies the logical properties of data type or data structure.
Refers to the mathematical concept that governs them.
They are not concerned with the implementation details like space and time
efficiency.
They are defined by 3 components called Triple =(D,F,A)
D=Set of domain
F=Set of function
A=Set of axioms / rules 

LINKED LIST:

A dynamic data structure.
Linear collection of data items.
Direction is associated with it.
Logical link exits b/w items. Pointers acts as the logical link.
Consists of nodes that has two fields.

- Data field : info of the element.
- Next field: next pointer containing the address of next node.

TYPES OF LINKED LIST:

i. Singly or chain: Single link b/w items.

ii. Doubly: There are two links, forward and backward link.
iii. Circular: The last node is again linked to the first node. These can be singly circular
& doubly circular list.

ADVANTAGES:

Linked list use dynamic memory allocation thus allocating memory when program
is initialised. List can grow and shrink as needed. Arrays follow static memory
allocation .Hence there is wastage of space when less elements are declared. There
is possibility of overflow too bcoz of fixed amount of storage.
Nodes are stored incontiguously thus insertion and deletion operations are easily
implemented.
Linear data structures like stack and queues are easily implemented using linked
list.

 DISADVANTAGES:

Wastage of memory as pointers requirextra storage.
Nodes are incontiguously stored thereby increasing time required to access
individual elements. To access nth item arrays need a single operation while
linked list need to pass through (n-1) items.
Nodes must be read in order from beginning as they have inherent sequential
access. 
Reverse traversing is difficult especially in singly linked list. Memory is wasted for
allocating space for back pointers in doubly linked list.

DEFINING LINKED LIST:

struct node {
int info;
 struct node *next; \\next field. An eg of self referencetial structure.(#)
 } *ptr;
(#)Self Referencetial structure: A structure that is referencing to another structure of same
type. Here “next” is pointing to structure of type “node”.
-ptr is a pointer of type node. To access info n next the syntax is: ptr->info; ptr->next;

OPERATIONS ON SINGLY LINKED LIST:

i. Searching
ii. Insertion
iii. Deletion
iv. Traversal
v. Reversal
vi. Splitting
vii. Concatenation
Some operations:
a: Insertion :
 void push(struct node** headref, int data) --------(1)
{
 struct node* newnode = malloc(sizeof(struct node));
 newnode->data= data;
 newnode->next= *headref;
 *headref = newnode;
} 
(1) : headref is a pointer to a pointer of type struct node. Such passing of pointer to pointer
is called Reference pointer. Such declarations are similar to declarations of call by
reference. When pointers are passed to functions ,the function works with the original
copy of the variable.

i. Insertion at head:

struct node* head=NULL;
for(int i=1; i<6;i++)
{ push(&head,i); \\ push is called here. Data pushed is 1.’&’ used coz references are
passed in function arguments.
 }
return(head);
}
# :o\p: 5 4 3 2 1

# :Items appear in reverse order.(demerit)
ii. Insertion at tail:

struct node* add1()
{ struct node* head=NULL;
struct node* tail;
push(&head,1);
tail = head;
for(int i=2 ;i<6; i++)
{ push(&(tail->next),i);
tail= tail->next;
}
return(head);
}
 # : o\p: 1 2 3 4 5

b. Traversal:

int count( struct node* p)
{int count =0;
struct node* q;
current = q; 
while(q->next != NULL)
{ q=q->next;
count++; }
return(count);
}
c. Searching:
struct node* search( struct node* list, int x)
{ struct node* p;
for(p= list; p ->next != NULL; p= p->next )
{
 if(p->data==x)
 return(p);
 return(NULL);
}}

IMPLEMENTATION OF LISTS:

i : Array implementation:

 #define NUMNODES 100
 structnodetype
{ int info ,next ;
} ;
structnodetype node[NUMNODES];
# :100 nodes are declared as an array node. Pointer to a node is represented by an array
index. Thus pointer is an integer b/w 0 & NUMNODES-1 . NULL pointer is represented by -1.
node[p] is used to reference node(p) , info(p) is referenced by node[p].info & next by
node[p].next. 

ii : Dynamic Implementation :

 This is the same as codes written under defining of linked lists. Using malloc() and
freenode() there is the capability of dynamically allocating & freeing variable. It is identical to
array implementation except that the next field is an pointer rather than an integer.
NOTE : Major demerit of dynamic implementation is that it may be more time consuming to call
upon the system to allocate & free storage than to manipulate a programmer- managed list.
Major advantage is that a set of nodes is not reserved in advance for use. 

• Facebook
• Twitter
• Google+
• Pinterest

PLZ... Share This Site To Your Contacts.....

• share our website
• please don't forget to share our blog and also subscribe to our youtube channel.. click here to subscribe our youtube channel
• click here to  follow our Facebook page

With regards

Team EveTech