Linear Vs Non-Linear Data Structures

In a linear data structure, elements are arranged one after another in a sequence. Each element has at most one previous and one next element, so the data can be traversed in a single run. Examples are arrays, linked lists, stacks and queues.

In a non-linear data structure, an element can be connected to several other elements, forming a hierarchy or a network. The data cannot be traversed in a single straight run. Trees and graphs are the main examples.

A stack is linear. Its elements form a sequence, and you can only add or remove from one end, the top. The same is true for a queue, where elements are added at the rear and removed from the front.

In a tree, one node can have many children, so the data branches out into multiple paths instead of forming one sequence. To visit every node you need a traversal strategy, such as depth-first or breadth-first, rather than a simple loop from start to end.

It depends on the structure, not the category. An array, which is linear, stores elements in one block with no extra pointers, so it is very compact. A linked list, also linear, needs an extra reference per node. Trees and graphs usually need several references per node, so they use more memory but represent relationships that linear structures cannot.

A linear structure needs one simple loop, while a non-linear structure needs recursion (or a stack or queue) to follow every branch:

// Linear: one pass from start to end
static void printArray(int[] arr) {
    for (int value : arr) {
        System.out.print(value + " ");
    }
}

// Non-linear: each node can branch into two paths
static void printTree(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.print(node.val + " ");
    printTree(node.left);
    printTree(node.right);
}

Yes. Both keep elements in a sequence. The difference is in memory: an array stores its elements in contiguous memory, while a linked list stores each element in a separate node connected by references.

• Linear: a queue of print jobs, the browser back button (a stack), a playlist of songs (a list).
• Non-linear: folders on a computer (a tree), an organization chart (a tree), roads between cities and social networks (graphs).

• Unsorted array or linked list: O(n).
• Sorted array with binary search: O(log n).
• Balanced binary search tree: O(log n).
• Graph with BFS or DFS: O(V + E), where V is the number of vertices and E the number of edges.

import java.util.ArrayList;
import java.util.List;

public class SimpleGraph {
    public static void main(String[] args) {
        int vertices = 4;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }
        // Undirected edges: 0-1, 0-2, 1-3
        graph.get(0).add(1); graph.get(1).add(0);
        graph.get(0).add(2); graph.get(2).add(0);
        graph.get(1).add(3); graph.get(3).add(1);

        for (int v = 0; v < vertices; v++) {
            System.out.println(v + " -> " + graph.get(v));
        }
    }
}

Vertex 0 is connected to both 1 and 2, which shows why a graph cannot be represented as a single sequence.