What is a Data Structure?
Data Structure aware us how to manage the data into the computer system. In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. Management of data can be done in different ways by using various available algorithms. Basically data structure give us brief knowledge about how the data are travels in different paths and how the sectors of memory store the data in a proper format. Data structure are core part of the computer system, without data structure proper knowledge no one can design a computer software. During the Software development process, major part of data structure are used to develop a error free software.
Data Structures are a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently. Data structures have a wide and diverse scope of usage across the fields of Computer Science and Software Engineering.Data structures are either system-generated or created by the application developer. A data structure is a collection of data items used to pass data to other components of the same application or to another application entirely. Data structures are being used in almost every program or software system that has been developed.
What is an algorithm?
There are many definitions of algorithms. An algorithm is a procedure, a finite set of well-defined instructions, for solving a problem which, given an initial state, will terminate in a defined end-state. The computational complexity and efficient implementation of the algorithm are important in computing, and this depends on suitable data structures.
Classification of Design Techniques:
- Brute-Force
- Divide-and-Conquer
- Depth First
- Breadth First
- Backtracking
- Greedy -- local optimal
- Branch and Bound.
- Recursive
Types of data structure in computer science:
The most important data structure topic must know to a programmer.
1.) ARRAY
2.) LINK LIST
3.) STACK
4.) QUEUE
5.) Hash Tables
6.) Heaps
7.) Tree
8.) Graph
9.) Time Complexity.
1.) Array Data structure:
Array give an mechanism to hold data which are Matched to similar background like Numbers, String, flot etc. Array stored the data into memory sequentially and can retrieve those data from anywhere in the memory randomly through index calling. But that does mean that the memory address are also be in a sequence manner. Absolutely memory allocation of array are in-sequential. Array can be one dimensional or may be more than one-D.
An array is a structure of fixed-size, which can hold items of the same data type. It can be an array of integers, floating-point numbers, strings or even an array of arrays (such as 2-dimensional arrays). Arrays are indexed, that means dynamically access of random numbers can be possible.
Array operations
- Traverse: Go through the elements and print them.
- Search: Search for an element in the array. You can search the element by its value or its index
- Update: Update the value of an existing element at a given index.
Problem Exercise 1:
An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A , of size N , each memory location has some unique index, i (where 0<= i < N), that can be referenced as A[i].
Reverse an array of integers.
Note: If you've already solved our C++ domain's Arrays Introduction challenge, you may want to skip this.
Example :
A[1, 2, 3 ]
Return output [3, 2, 1]
Function Description Complete the function reverseArray in the editor below.
ReverseArray has the following parameter(s):
● int A[n]: the array to reverse
Returns
● int[n]: the reversed array Input Format
Input Format The first line contains an integer, N , the number of integers in A.
The second line contains N space-separated integers that make up A .
Constraints
1 <= N <= 1000
1 <= A[i] <= 10000, where a[i] is the ith integer in A.
Sample Input 1
4
1 4 3 2
.Sample Output 1
2 3 4 1
2.) Link List Data Structure:
Linked lists are an ordered collection of objects. So what makes them different from normal lists? Linked lists differ from lists in the way that they store elements in memory. While lists use a contiguous memory block to store references to their data, linked lists store references as part of their own elements.
Each element of a linked list is called a node, and every node has two different fields:
- Data contains the value to be stored in the node.
- Next contains a reference to the next node on the list.
Linked lists provide a simple and flexible representation of dynamic sets.
- Elements in a linked list are known as nodes.
- Each node contains a key and a pointer to its successor node, known as next.
- The attribute named head points to the first element of the linked list.
- The last of the linked list is known as the tail.
Types of link list :
- Singly linked list — Traversal of items can be done in the forward direction only.
- Doubly linked list — Traversal of items can be done in both forward and backward directions. Nodes consist of an additional pointer known as prev, pointing to the previous node.
- Circular linked lists — Linked lists where the prev pointer of the head points to the tail and the next pointer of the tail points to the head.
Linked list operations
- Search: Find the first element with the key k in the given linked list by a simple linear search and returns a pointer to this element
- Insert: Insert a key to the linked list. An insertion can be done in 3 different ways; insert at the beginning of the list, insert at the end of the list and insert in the middle of the list.
- Delete: Removes an element x from a given linked list. You cannot delete a node by a single step. A deletion can be done in 3 different ways; delete from the beginning of the list, delete from the end of the list and delete from the middle of the list.
3.) Stack Data Structure:
Stack use LIFO concept "Last In First Out ", A stack is a collection that is based on the last-in-first-out (LIFO) policy. By tradition, we name the stack insert method push() and the stack remove operation pop(). the last data element stored in a stack is the first data element retrieved from the stack.
A stack is an abstract data type that consists of a predefined capacity. It allows adding and removing elements in a particular order. When every time an element is added, it goes to the top of the stack. Stack enables all data to operations at one end only. So the only element that can be removed is the element at the top of the stack, and only one item can be read or removed at a given time.
Examples of stacks in "real life":
- The stack of trays in a cafeteria;
- A stack of plates in a cupboard;
- A driveway that is only one car wide.
Examples of stacks in computing:
- Back/Forward stacks on browsers;
- Undo/Redo stacks in Excel or Word;
- Activation records of method calls;
Given a stack, the accessible element of the stack is called the top element. Elements are not said to be inserted; they are pushed onto the stack.
When an element (the last one) is removed, an element is said to be popped from the stack. Both array-based and linked stacks are fairly easy to implement.
Applications of Stack-
Balanced parenthesis · Our code editor uses a stack to check if we have closed all our parentheses properly, and even to prettify the code. The below code is an example for checking balanced parenthesis.
Backtracking · Stacks are particularly useful when the computation has to go back in reverse order. This happens often in artificial intelligence applications: games, logic programs, theorem provers, etc. Think of walking through a maze. Whenever you have options to move in more than one direction, push all but one of the options onto the stack and then go in the direction you didn’t push. When you run into a dead end, walk backwards to your last option (i.e. pop the stack) and proceed from there.
Activation records · Every time a function is called in a program, all the function’s arguments and local variables are stored by being pushed onto a stack. When the function exits, all that memory can be reclaimed by simply popping the stack back to where it was before the function call.
Reverse a word · Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.
In compilers · Compilers use the stack to calculate the value of expressions like-
2 + 4 / 5 * (7–9)
by converting the expression to prefix or postfix form.
In browsers · The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack, and the previous URL is accessed .
NEXT TOPIC
4.) QUEUE
5.) Hash Tables
6.) Heaps
7.) Tree
8.) Graph
9.) Time Complexity
Click below to Continue Read ............
