Types of Data Structure

Data Structure > Data Structure Introduction > What is Data Structure

Short Question

1320

Answer:

Depending on the organization of the elements, data structures are classified into two types:

1. Linear data structures

Linear data structures are data structures in which elements are organized sequentially or linearly, meaning each element has a direct predecessor and successor, except for the first and last elements. Linear data structures facilitate simple and straightforward traversal of elements from one end to another.

Here are some common examples of linear data structures:

Arrays: A collection of elements stored in contiguous memory locations, accessible by their index. Elements in an array have a linear order, and you can traverse them in a linear manner.
Linked Lists: A linear collection of elements (nodes), where each node contains both data and a reference (pointer) to the next node. Traversing a linked list involves following the pointers from one node to the next.
Stacks: A Last-In-First-Out (LIFO) linear data structure, where elements are added and removed from the same end, called the top. The most recently added element is the first to be removed.
Queues: A First-In-First-Out (FIFO) linear data structure, where elements are added at the rear and removed from the front. The oldest element is the first to be removed.
Deques (Double-Ended Queues): A linear data structure that allows insertion and deletion at both ends, front and rear.
Vectors (Dynamic Arrays): Similar to arrays but with dynamic resizing capabilities, allowing them to grow or shrink as needed.
Strings: A sequence of characters arranged in a linear manner. Strings are a fundamental linear data structure in many programming languages.

Linear data structures are essential building blocks in computer science and programming. They are used in various algorithms and applications, ranging from simple data storage and retrieval to more complex data processing tasks. The choice of a specific linear data structure depends on the requirements of the problem you are trying to solve and the desired performance characteristics for the operations you need to perform.

2. Non Linear data structures

Non-linear data structures are data structures in which elements are organized in a way that does not follow a sequential order like linear structures. Elements in non-linear data structures can have multiple predecessors and successors, leading to more complex relationships between elements. These structures are particularly useful when data needs to be represented in a hierarchical or interconnected manner.

Here are some common examples of non-linear data structures:

Trees: Trees are hierarchical data structures consisting of nodes connected by edges. Each tree has a root node, and each node can have zero or more child nodes. Nodes with no children are called leaves. Trees can be binary trees, where each node has at most two children, or multiway trees with more than two children per node. Special types of trees include:
- Binary Search Trees (BST): A binary tree where the left child is less than the parent, and the right child is greater.
- AVL Trees: A self-balancing binary search tree to ensure efficient operations.
- Red-Black Trees: Another type of balanced binary search tree with specific properties.
- B-Trees: Multiway search trees used for efficient disk-based storage and retrieval.
Graphs: Graphs are collections of nodes (vertices) connected by edges (links). Unlike trees, graphs can have cycles (cycles are loops in the graph). Graphs can be directed (edges have a direction) or undirected (edges have no direction). Common types of graphs include:
- Directed Graphs (Digraphs): Edges have a specific direction from one vertex to another.
- Undirected Graphs: Edges have no specific direction and represent symmetric relationships.
- Weighted Graphs: Edges have associated weights or costs, representing values like distances or time.
Heaps: Heaps are specialized binary trees used to efficiently find the maximum or minimum element in constant time. They can be max heaps or min heaps, where the root node holds the largest or smallest element, respectively.
Hash Tables: While hash tables store data in a linear array, they are considered non-linear because the relationship between keys and their corresponding hash locations is not sequential. Hash tables use a hash function to convert keys into array indices, allowing for efficient retrieval based on keys.
Trie: A tree-like data structure used for efficient storage and retrieval of a dynamic set of strings with a common prefix. Tries are commonly used for dictionary-like applications and autocomplete features.

Non-linear data structures are essential for representing complex relationships and organizing data efficiently in various applications, including database management systems, network routing algorithms, hierarchical file systems, and more. The choice of a specific non-linear data structure depends on the specific problem domain and the types of operations needed for the application.

Go to Question List

This Particular section is dedicated to Question & Answer only. If you want learn more about Data Structure. Then you can visit below links to get more depth on this subject.

Data Structure Syllabus

Data Structure Tutorial

Data Structure Programs

Data Structure Question Answers

Data Structure MCQ

# C Tutorials # JAVA Tutorials # HTML Tutorials # Computer Fundamental # Data Structure # DBMS Tutorials SQL # C# Language # R Language # PHP # Python # Vue JS

Join Our telegram group to ask Questions

Click below button to join our groups.

Ask Question - CSE

Programming Language - PDF

Related Program List

541. What is the algorithm?

# Tutorial: What is Algorithm

Question: Data Structure Introduction Long

542. What are the various operations that can be performed on different Data Structures?

Answer:

Insertion: Add a new data item in the given collection of data items.
Deletion: Delete an existing data item from the given collection of data items.
Traversal: Access each data item exactly once so that it can be processed.
Searching: Find out the location of the data item if it exists in the given collection of data items.
Sorting: Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

# Tutorial: Various Data structures operations

Question: Data Structure Introduction Short

543. How is an Array different from Linked List?

Answer:

The size of the arrays is fixed, Linked Lists are Dynamic in size.
Inserting and deleting a new element in an array of elements is expensive, Whereas both insertion and deletion can easily be done in Linked Lists.
Random access is not allowed in Linked Listed.
Extra memory space for a pointer is required with each element of the Linked list.
Arrays have better cache locality that can make a pretty big difference in performance.

Here is a table comparing arrays and linked lists:

	Array	Linked List
Definition	A collection of elements of the same data type, stored in contiguous memory locations	A collection of elements of the same data type, where each element points to the next element in the list
Memory Allocation	Memory allocation is static and fixed at compile time	Memory allocation is dynamic and can be changed during runtime
Access Time	Elements are accessed by their index, and the access time is O(1)	Elements are accessed by traversing the list from the beginning or end, and the access time is O(n)
Insertion and Deletion	Insertion and deletion operations can be slow because all elements after the insertion or deletion point have to be shifted over	Insertion and deletion operations are efficient because only the affected elements need to be modified
Memory Usage	Array size is fixed and predetermined, even if not all elements are used	Linked lists can use memory more efficiently because they only use memory for the elements that are actually in the list
Sorting	Sorting is efficient for small arrays, but less efficient for large arrays	Sorting can be less efficient for linked lists because they require traversing the list multiple times

In summary, arrays and linked lists have different strengths and weaknesses, and their use depends on the specific needs of the application. Arrays are efficient for random access, while linked lists are efficient for dynamic memory allocation and efficient insertion and deletion operations.

# Tutorial: Linked List Introduction

Question: Linked List Short

544. What is Stack and where it can be used?

Answer:

The stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last Out) for accessing elements. Basic operations of the stack are: Push, Pop, Peek

Applications of Stack:

Infix to Postfix Conversion using Stack
Evaluation of Postfix Expression
Reverse a String using Stack
Implement two stacks in an array
Check for balanced parentheses in an expression

# Tutorial: Stack Data Structure Introduction

Question: Stack Data Structure Short

545. What is a Queue, how it is different from the stack and how is it implemented?

# Tutorial: Queue Introduction

Question: Queue Data Structure Long

546. What is a Linked List and What are its types?

# Tutorial: Linked List Introduction

Question: Linked List Long

547. Which data structures are used for BFS and DFS of a graph?

Answer:

Queue is used for BFS
Stack is used for DFS. DFS can also be implemented using recursion (Note that recursion also uses function call stack).

# Tutorial: Graph in Data Structure

Question: Graph Short

548. Which Data Structure Should be used for implementiong LRU cache?

Answer:

We use two data structures to implement an LRU Cache.

Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).The most recently used pages will be near rear end and least recently pages will be near front end.
A Hash with page number as key and address of the corresponding queue node as value. See How to implement LRU caching scheme? What data structures should be used?

# Tutorial: Queue Introduction

Question: Queue Data Structure Short

549. How to check if a given Binary Tree is BST or not?

Answer:

If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do inorder traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false.

# Tutorial: Tree Introduction

Question: Tree Short

550. What is a Tree?

Answer:

A tree is a data structure similar to a linked list but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of a non-linear data structure. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form.
In trees ADT (Abstract Data Type), the order of the elements is not important. If we need ordering information, linear data structures like linked lists, stacks, queues, etc. can be used.

# Tutorial: Tree Introduction

Question: Tree Short

Chapterwise Java Program
Chapterwise C Program
Chapterwise Data Structure Program