Non-Linear Data Structures

Types of Data Structures

Data structures are broadly classified into two categories:

Primitive Data Structures

Primitive data structures are the basic building blocks used to create more complex structures. They include:

• Integers: Whole numbers.
   
• Floats: Decimal numbers.
   
• Characters: Single symbols or letters.
   
• Booleans: True or false values.

Non-Primitive Data Structures

Non-primitive data structures are more complex and can be divided into two types:

• Linear Data Structures: Elements are arranged in a linear sequence.
   
• Non-Linear Data Structures: Elements are arranged in a hierarchical or network-like structure.

Linear Data Structure

Array

An array is a collection of elements identified by index or key. It stores elements in a contiguous memory location.

Example:

• Python

Python

# Python example of an array (list)

numbers = [1, 2, 3, 4, 5]

print(numbers)

You can also try this code with Online Python Compiler

Run Code

Output

[1, 2, 3, 4, 5]

Complexity:

• Time: O(1) for accessing elements by index.
• Space: O(n), where n is the number of elements.

Stack

A stack is a linear data structure that operates on the Last In, First Out (LIFO) principle. It allows two main operations: push, which adds an element to the top of the stack, and pop, which removes the element from the top.

Example:

• Python

Python

# Python example of a stack using a list

stack = []


# Push elements

stack.append(1)

stack.append(2)

stack.append(3)


print("Stack after push operations:", stack)


# Pop element

stack.pop()

print("Stack after pop operation:", stack)

You can also try this code with Online Python Compiler

Run Code

Output

Stack after push operations: [1, 2, 3]
Stack after pop operation: [1, 2]

Complexity:

• Push/Pop Operations: O(1)
• Space: O(n)

Queue

A queue is a linear data structure that operates on the First In, First Out (FIFO) principle. It supports key operations such as enqueue, which adds an element to the rear of the queue, and dequeue, which removes the element from the front.

Example:

• Python

Python

# Python example of a queue using collections.deque
from collections import deque

queue = deque()

# Enqueue elements
queue.append(1)
queue.append(2)
queue.append(3)

print("Queue after enqueue operations:", queue)

# Dequeue element
queue.popleft()
print("Queue after dequeue operation:", queue)

You can also try this code with Online Python Compiler

Run Code

Output

Queue after enqueue operations: deque([1, 2, 3])
Queue after dequeue operation: deque([2, 3])

Complexity:

• Enqueue/Dequeue Operations: O(1)
• Space: O(n)

Linked List

A linked list is a linear data structure where each element (node) points to the next element. It allows for efficient insertion and deletion operations.

Example:

• Python

Python

# Python example of a singly linked list

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None


class LinkedList:

    def __init__(self):

        self.head = None

    def append(self, data):

        if not self.head:

            self.head = Node(data)

        else:

            current = self.head

            while current.next:

                current = current.next

            current.next = Node(data)

    def display(self):

        elements = []

        current = self.head

        while current:

            elements.append(current.data)

            current = current.next

        return elements

# Create and display a linked list

linked_list = LinkedList()

linked_list.append(1)

linked_list.append(2)

linked_list.append(3)

print("Linked List:", linked_list.display())

You can also try this code with Online Python Compiler

Run Code

Output

Linked List: [1, 2, 3]

Complexity:

• Insertion/Deletion: O(1) if the position is known; otherwise O(n)
• Access: O(n)
• Space: O(n)

Non-Linear Data Structure

Non-linear data structures are used to represent more complex relationships between data elements.

Tree

A tree is a hierarchical data structure composed of nodes, where each node is connected by edges. It starts with a root node, and the nodes are organized in a hierarchical structure, with parent-child relationships forming sub-trees.

Example:

• Python

Python

# Python example of a basic tree structure
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)

    def display(self, level=0):
        print(' ' * level * 2 + str(self.value))
        for child in self.children:
            child.display(level + 1)

# Create and display a tree
root = TreeNode("Root")
child1 = TreeNode("Child 1")
child2 = TreeNode("Child 2")
root.add_child(child1)
root.add_child(child2)

child1.add_child(TreeNode("Child 1.1"))
child1.add_child(TreeNode("Child 1.2"))

child2.add_child(TreeNode("Child 2.1"))

root.display()

You can also try this code with Online Python Compiler

Run Code

Output

Root
  Child 1
    Child 1.1
    Child 1.2
  Child 2
    Child 2.1

Complexity:

• Insertion/Deletion: O(1) if position is known, otherwise O(n)
• Access: O(n)
   

Terminologies Used in Tree

• Node: The fundamental unit of a tree that holds data.
   
• Root: The topmost node in the tree.
   
• Leaf: A node that has no children.
   
• Edge: The link or connection between two nodes.
   
• Subtree: A section of a tree consisting of a node and all its descendants.
   

Types of Trees

• Simple Tree: A generic term for any tree without specific constraints.
   
• Binary Tree: A tree where each node can have at most two children (left and right).
   
• Binary Search Tree (BST): A binary tree where the left child contains values smaller than the node, and the right child contains values larger than the node.

Example of Binary Tree:

• Python

Python

# Python example of a binary tree

class BinaryTreeNode:

    def __init__(self, value):

        self.value = value

        self.left = None

        self.right = None

    def display(self, level=0):

        if self.right:

            self.right.display(level + 1)

        print(' ' * level * 2 + str(self.value))

        if self.left:

            self.left.display(level + 1)


# Create and display a binary tree

root = BinaryTreeNode(10)

root.left = BinaryTreeNode(5)

root.right = BinaryTreeNode(15)

root.left.left = BinaryTreeNode(2)

root.left.right = BinaryTreeNode(7)

root.right.right = BinaryTreeNode(20)

root.display()

You can also try this code with Online Python Compiler

Run Code

Output:

 20
  15
      10
    7
  5
    2

Complexity:

• Insertion/Deletion/Access: O(log n) for balanced trees, O(n) for unbalanced trees

Graph Data Structure

A graph is a data structure consisting of a set of nodes (also called vertices) and edges that connect pairs of nodes. Graphs are widely used to model relationships and structures in real-world systems such as social networks, communication networks, and transportation routes.

Example:

• Python

Python

# Python example of a graph using adjacency list

class Graph:

    def __init__(self):

        self.graph = {}

    def add_vertex(self, vertex):

        if vertex not in self.graph:

            self.graph[vertex] = []

    def add_edge(self, vertex1, vertex2):

        if vertex1 in self.graph and vertex2 in self.graph:

            self.graph[vertex1].append(vertex2)

            self.graph[vertex2].append(vertex1)  # For undirected graph

    def display(self):

        for vertex in self.graph:

            print(f'{vertex}: {self.graph[vertex]}')

# Create and display a graph

graph = Graph()

graph.add_vertex('A')

graph.add_vertex('B')

graph.add_vertex('C')

graph.add_edge('A', 'B')

graph.add_edge('A', 'C')

graph.display()

You can also try this code with Online Python Compiler

Run Code

Output

A: ['B', 'C']
B: ['A']
C: ['A']

Complexity:

• Edge Insertion: O(1)
• Vertex Insertion: O(1)
• Space: O(V + E), where V is the number of vertices and E is the number of edges

Properties of Non-linear Data Structures

Non-linear data structures are essential for organizing data in a multi-dimensional space where relationships between elements are not sequential or linear. Below are the key properties and features of non-linear data structures:

Hierarchical Structure

Non-linear data structures are often organized hierarchically, with elements arranged in different levels. This is clearly seen in structures like trees, where data starts at the root and spreads out to leaves.

Multiple Connections

Unlike linear structures, where each element connects to only one other (or in the case of singly linked lists, just one next element), non-linear structures can have multiple connections. For instance, a graph node can have several edges connecting it to various nodes.

Dynamic Size

Non-linear structures can grow or shrink as elements are added or removed, making them perfect for handling unknown data volumes, like mapping relationships in a social network.

Efficient Data Access and Manipulation

Non-linear structures allow for quicker and more efficient operations in certain situations:

• Trees provide fast search, insert, and delete operations, which often outperform linear structures like arrays or linked lists.
• Graphs are ideal for representing and querying complex relationships, vital in areas like navigation systems and network mapping.

Recursive Access

Processing non-linear structures often involves recursion. Many operations on trees (such as searching, traversing, and inserting) are implemented through recursion, which naturally follows the tree’s hierarchical structure.

Complex Memory Management

Non-linear structures often require more memory than linear ones, as they need to store additional information like pointers or edges to represent complex relationships.

Applications of Non-linear Data Structures

Non-linear structures are useful when elements are interconnected or have non-linear relationships. Common applications include:

• Tree Structures for organizing file systems, decision trees, and syntax trees in compilers.
   
• Graph Structures for social networks, web page linking (like the World Wide Web), and utility grids (like power networks).

Storage Techniques

• Adjacency Lists/Matrix: Common methods for storing graphs, representing relationships between nodes efficiently.
   
• Pointer-based Storage: Trees are often stored with pointers to their child and parent nodes, maintaining hierarchical relationships.

Frequently Asked Questions

What is the difference between linear and non-linear data structures?

Linear structures arrange elements in sequence, while non-linear structures organize elements hierarchically or in a network, supporting more complex relationships.

How is a binary tree different from a binary search tree?

A binary tree allows each node to have up to two children, while a binary search tree (BST) organizes nodes so that the left child is smaller and the right child is larger than the parent.

What are the applications of graphs in real life?

Graphs model real-world systems like social networks, transportation routes, and recommendation systems by representing relationships between entities.

Conclusion

Non-linear data structures like trees and graphs are powerful tools for representing and managing complex data relationships. Understanding these structures is key to handling hierarchical and network-based data efficiently. By understanding these concepts, you can solve a wide range of challenges in both academic and professional settings.

You can also check out our other blogs on Code360.