introduction to data structure

A data structure is a kind of representation of the relationship between logically related data elements. In the data structure, the decision on the operations such as storage, retrieval, and access must be carried out between the logically related data elements. Data structures are divided into two types. They are,

1. Linear data structure
2. Non-linear data structure

Linear data structure

A data structure is said to be linear if its elements are stored in a sequential manner. Therefore, in this data structure, a linear relationship is formatted between elements with the help of sequential memory locations.

Examples of the linear data structure are arrays, stacks, queues and linked list.

Non-linear data structure

A data structure in which the elements are not arranged in a linear or sequential memory locations.

An example of a non-linear data structure is a tree, graph, and table.

The various data structures can be explained as follows

Linear data structure Stack

A stack is a linear data structure. The elements in a stack can be inserted and deleted at only one end. This end is called the top. Two essential operations carried out on a stack are,

1. Push: when an element is added to a stack, such kind of operation is called push.
2. Pop: when an element is deleted from a stack, such kind of operations is called pop.

When elements are added to a stack, the stack expands and when elements are deleted from the stack shrinks.

A stack is also said to be Last-In-First-Out (LIFO).

In the above figure, the value 2 is the first element to be inserted into stack and -15 value is the last element or 5th element to be inserted into the stack and that becomes the top of the stack. If an element needs to be deleted, then the last inserted element of the stack needs to be popped i.e., -15 value will get deleted fist because insertion and deletion are from one end only.

When a stack does not have any element, the stack is said to be empty and the value of top is -1.

Linear data structure Queue

A queue is a linear data structure. In a queue, elements are added at one end called ‘rear’ and deletion of an element is done at the other end called the ‘front’. Elements in a queue are inserted or deleted in a sequential manner and the elements in a queue cannot be sorted or get accessed randomly.

In the real world, an example of a queue can be, people standing in a queue to take tickets for a movie at a theatre. the first person, who takes the ticket will be the first one to move out.

Queue follows a First-in-First-out (FIFO) fashion, in which, the element that is inserted first gets deleted first.

In the above figure -2 is the value of element inserted first from the rear end and thus -2 will get deleted at the front end. This is known as FIFO organization.

When there are no elements in a queue, the queue is empty and rear and front contains the value -1. As elements are inserted or deleted, the rear and front get incremented respectively.

Linear data structure Linked List

A linked list is a linear data structure used to stores similar data in memory. The elements in the linked list are not stored in adjacent memory locations but are stored randomly. A linked list is a collection of elements known as nodes which contains two fields of information. One contains the data items and other contains the link or address of the successor list element. A node can be represented as,

There are different types of a linked list that are formatted by changing the link position. They are,

1. Singly linked list
2. Doubly linked list
3. Circular linked list

Non-Linear Data Structure – Trees

Trees are a non-linear data structure that can be represented in a hierarchical number. For example the representation of ‘Birds’. Birds are divided into flying birds and non-flying birds.

A tree contains nodes and each node contains the name of data and link to other tree nodes. This type of tree is called as ‘Binary Tree’.

• Root: the basic element of the nodes in a tree is called a root. For the above tree ‘a’ is the root node.
• Left sub-tree: the sub-tree representing the left-hand position is the left sub-tree. For the above tree, the left subtree is formatted by nodes ‘b’, ‘d’ and ‘e’.
• Right sub-tree: the sub-tree representing the right sub-tree. for the above tree the nodes ‘c’,’f’ and ‘g’ forms the right sub-tree.
• A node that cannot be subdivided is called a leaf node.
• Degree of a node relates to the number of nodes connected to a particular node.

The height of a tree is judged by its level and depth.

Accessing a tree is called tree traversal and there are different tree traversals such as inorder tree traversal, preorder tree traversal, and post-order tree traversal.

Different operations can be performed on a tree such as insertion, deletion, searching and traversing.

Non-Linear Data Structure – Graph

A graph is a data structure having a set of interconnected vertices connected with the help of the set of edges.

A graph can be of two types. They are as follows,

• Directed Graph: in a directed graph, the order of vertices representing an edge is important. For example

The set of vertices here are [A,B,C,D] and set of edges are [(A,B),(A,C),(B,D),(C,D)]

• Undirected Graph: in an undirected graph, the order of pair of vertices is not important.

Set of vertices are [A,B,C,D]

Set of edges are [ (A,B),(A,C),(B,D),(A,D),(C,D),(D,C)]

Graph can be represented in two ways

1. By adjacency matrices
2. Adjacency lists.

The operations that can be performed on the graph are as follows.

1. Depth-first search
2. Breadth-first search