Data Structure

Data Structure

A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.

Type of Data Structure?

1. Primitive Data Structures
2. Non-primitive Data Structures

Primitive data Structures are also called Primitive Data Types. byte, short,? int, float, char, boolean, long, and double are primitive Data types.

Non-primitive data Structures – Non-primitive Data Structures are of two types:-

1. Linear Data Structures ( Array, Linked List, Stack, Queue)
2. Non-linear Data Structures (Tree, Graph)

Common Type of Data Structure?

• Array
• Linked List
• Stack?
• Queue
• Binary Tree
• Binary Search Tree
• Heap
• Hashing?
• Graph

Classification of Data Structures

• Static Data Structures are the Data structures whose size is declared and fixed at Compile Time and cannot be changed later are called Static Data structures.
• Example – Arrays
• Dynamic Data Structures are the Data Structures whose size is not fixed at compile time and can be decided at runtime depending upon requirements are called Dynamic Data structures.
• Example – Binary Search Tree

Array

An array is a dynamically-created object. It serves as a container that holds the constant number of values of the same type. It has a contiguous memory location. Once an array is created, we cannot change its size. We can create an array by using the following statement:

1. int array[]=new int[size];??

Array Advantages

• Random access
• Easy sorting and iteration
• Replacement of multiple variables

Array Disadvantages

• Size is fixed
• Difficult to insert and delete
• If capacity is more and occupancy less, most of the array gets wasted?
• Needs contiguous memory to get allocated

Java ArrayList

In Java, ArrayList is a class of Collections framework. It implements List<E>, Collection<E>, Iterable<E>, Cloneable, Serializable, and RandomAccess interfaces. It extends AbstractList<E> class.

1. ArrayList<Type> arrayList=new ArrayList<Type>();??

ArrayList is internally backed by the array in Java. The resize operation in ArrayList slows down the performance as it involves new arrays and copying content from an old array to a new array. It calls the native implemented method System.arraycopy(sec, srcPos, dest, destPos, length) .

We cannot store primitive types in ArrayList. So, it stores only objects. It automatically converts primitive types to objects. For example, we have create an ArrayList object,

1. ArrayList <Integer> list=new ArrayList<Integer>();? //object of ArrayList??
2. arrayObj.add(12); ? //trying to add integer primitive to the ArrayList??

The JVM converts it into an Integer object through auto-boxing.

1. ArrayList arrayObj=new ArrayList()//object of ArrayList??
2. arrayObj(new Integer(12)); //converts integer primitive to Integer object and added to ArrayList object

Similarities

• Array and ArrayList both are used for storing elements.
• Array and ArrayList both can store null values.
• They can have duplicate values.

Linked list

A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node.

Type of Linked List?

• 1. Singly Linked List?
• 2. Doubly Linked List
• 3. Circular Linked List?

Singly Linked List?

Singly linked lists contain two “buckets” in one node; one bucket holds the data and the other bucket holds the address of the next node of the list. Traversals can be done in one direction only as there is only a single link between two nodes of the same list.

Doubly Linked List

Doubly Linked Lists contain three “buckets” in one node; one bucket holds the data and the other buckets hold the addresses of the previous and next nodes in the list. The list is traversed twice as the nodes in the list are connected to each other from both sides.

Circular Linked List

Circular linked lists can exist in both singly linked list and doubly linked list.

Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken.

Linked List Advantages

• Dynamic in size
• No wastage as capacity and size is always equal
• Easy insertion and deletion as 1 link manipulation is required
• Efficient memory allocation

Linked List Disadvantages

• If head Node is lost, the linked list is lost
• No random access is possible

Stack

A stack is a representation of nodes. There are two components to each node: data and next (storing address of next node). Each node’s data portion contains the assigned value, and its next pointer directs the user to the node that has the stack’s subsequent item. The highest node in the stack is referred to as the top. Follows LIFO: Last In First Out.

• It is called as stack because it behaves like a real-world stack, piles of books, etc.
• A Stack is an abstract data type with a pre-defined capacity, which means that it can store the elements of a limited size.
• It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.
• DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.

Stack Operations

• push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
• pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
• isEmpty(): It determines whether the stack is empty or not.
• isFull(): It determines whether the stack is full or not.'
• peek(): It returns the element at the given position.
• count(): It returns the total number of elements available in a stack.
• change(): It changes the element at the given position.
• display(): It prints all the elements available in the stack.

Queue

The queue is called an abstract data structure. Data is always added to one end (enqueued), and removed from the other (dequeue). Queue uses the First-In-First-Out approach and data item that was stored initially will be accessed first in a queue.

Queue Operations

A queue is an object (an abstract data structure - ADT) that allows the following operations:

• Enqueue: Add an element to the end of the queue
• Dequeue: Remove an element from the front of the queue
• IsEmpty: Check if the queue is empty
• IsFull: Check if the queue is full
• Peek: Get the value of the front of the queue without removing it

Binary Tree

In a binary tree, the branches of the tree are made up of up to two child nodes for each node. The left and right nodes are the common names for the two youngsters. Child nodes make references to their parents, whereas parent nodes are nodes with children.

Features of Binary Tree

• Hierarchical? Data Structure
• The topmost element is known as the root of the tree
• Every Node can have at most 2 children in the binary tree
• Can access elements randomly using index
• Eg: File system hierarchy
• Common traversal methods:
• preorder(root) : print-left-right
• postorder(root) : left-right-print?
• inorder(root) : left-print-right

Binary Tree Advantages

• Can represent data with some relationship
• Insertion and search are much more efficient

Binary Tree Disadvantages

• Sorting is difficult
• Not much flexible

Binary Tree Applications

• File system hierarchy
• Multiple variations of the binary tree have a wide variety of applications

Heap

In this tutorial, you will learn what heap data structure is. Also, you will find working examples of heap operations in C, C++, Java and Python.

Heap data structure is a complete binary tree that satisfies the heap property, where any given node is

• always greater than its child node/s and the key of the root node is the largest among all other nodes. This property is also called max heap property.
• always smaller than the child node/s and the key of the root node is the smallest among all other nodes. This property is also called min heap property.

Heap Operations

Some of the important operations performed on a heap are described below along with their algorithms.

Heapify

Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-Heap or a Max-Heap.

Hashing

Hashing is a technique or process of mapping keys, and values into the hash table by using a hash function. It is done for faster access to elements. The efficiency of mapping depends on the efficiency of the hash function used.

Let a hash function H(x) maps the value x at the index x%10 in an Array. For example if the list of values is [11,12,13,14,15] it will be stored at positions {1,2,3,4,5} in the array or Hash table respectively.

Graph

In this tutorial, you will learn what a Graph Data Structure is. Also, you will find representations of a graph.

• Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabelled.
• Edges: Edges are drawn or used to connect two nodes of the graph. It can be ordered by a pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labeled/unlabelled.

A graph data structure is a collection of nodes that have data and are connected to other nodes.

Let's try to understand this through an example. On facebook, everything is a node. That includes User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note...anything that has data is a node.

Every relationship is an edge from one node to another. Whether you post a photo, join a group, like a page, etc., a new edge is created for that relationship.