Non Linear Data Structure

Nov 27 • Notes • 9459 Views • No Comments on Non Linear Data Structure

Non linear data structure is a data structure in which data items are not stored linearly in the memory. So there is no contiguous memory allocation of the data. This feature is included because it uses the memory optimally.

How does it do so?

Well, memory is represented in blocks. So each time a certain amount of memory is allocated for storing any data. If that data is smaller than the allocated memory, the extra memory is wasted as that memory is not big enough to store another data. But may be it can store a part of data. So this feature helps in the way that the memory that got wasted like this can be used to store a part of the data, and the remaining parts are stored in some other memory location and all allocated memory is connected, like this the memory is saved from being wasted and our data also remains intact in order. So this non linear data structure decreases the space complexity and the memory is used optimally.

The following are non linear data structures:-

1. Linked list

Linked list is a non linear data structure in which data is stored in memory with contiguous memory allocation. One item of linked list is linked with next data item. Linked list are of different types- circular linked list, doubly linked list, circular doubly linked list.

The one advantage of linked list it allows insertion, deletion at any position of the linked list. A circular doubly linked list is the one in which the last data item is linked with the first data item. Whereas a doubly linked list is the one in which there are both forward and backward links between data items.

2. Trees

A tree is an abstract data type, having a hierarichal structure. A tree has root node, and a sub tree. It follows parent – child relationship.

Types of trees are-

Binary tree:- A binary tree is a tree in which each node has at most two child nodes, one left child and one right child. It is used to implement binary search tree.
AVL tree:- Adlen veliskii landis (avl) tree is a self balanced tree in which the difference between the height of the two child sub trees at any node is 0, 1, -1. The tree is balanced to maintain its property in case of any disperancy.
Binary search tree
Complete binary tree
Red – black tree
Weighted balance tree
B tree – A B tree can have more than two children at a node.
B+ tree
2 -3 tree

3. Graph

A graph is an abstract data structure which consists finite set of vertices and edges. A graph may be directed or undirected.

Advantages