Types of Data Structure: Linear and Non-Linear With Code

For my first six months, I couldn't tell a stack from a queue without looking up the diagram. In a 2025 interview round, I watched a candidate explain a stack by reciting the definition, then freeze when asked to write push() from memory. This post walks through every type with real code, so you can explain it with confidence.

Data structures split into two families: linear and non-linear. Linear structures (arrays, stacks, queues, linked lists) store elements in a sequence, each connected to its neighbors. Non-linear structures (trees, graphs) arrange elements in hierarchies or networks. Knowing which family fits your problem is the first step to solving it in an interview.

What Is a Linear Data Structure?

In a linear data structure, elements are arranged in a sequence, each connected to the one before and after it. Every element sits on a single level, which means you can traverse the whole structure in one run from start to end. This makes linear structures easy to implement, but their memory use is less efficient, as GeeksforGeeks explains.

Arrays, stacks, queues, and linked lists are the four you will meet most often. Each one solves a different problem, and each has a distinct way of handling data.

Array: The Simplest Linear Structure

An array stores elements of the same type in contiguous memory, and you access any element by its index starting at 0. This indexed lookup is what makes arrays fast: the position tells you exactly where to go, no searching required. Arrays are simple to write and understand, but their size is fixed when you create them, which makes resizing a manual job.

# Create an array (list in Python)
marks = [78, 85, 91, 67, 88]
# Indexed lookup: access the third element
print(marks[2])   # Output: 91
# Update an element
marks[4] = 92
print(marks)      # Output: [78, 85, 91, 67, 92]

When you need random access to any element quickly, an array is the natural choice. The trade-off is that inserting or deleting in the middle means shifting every element after it. For example, to insert 90 at index 2 in [78, 85, 91, 67, 88], you'd copy 91, 67, and 88 one step right first.

Stack: LIFO in Code

A stack follows Last-In-First-Out (LIFO): the last element pushed is the first popped, like a browser's back button. You add to the top and remove from the top, nothing else. The two operations are push to add and pop to remove, with peek to look at the top without removing it. Browsers use this exact mechanism to store your history, as unstop notes: the back button pops the most recent page first.

1. Push

   Add an element to the top of the stack.

2. Pop

   Remove and return the top element.

3. Peek

   Look at the top element without removing it.

Let's see the same stack in C, where you manage the array size yourself.

#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
void push(int value) {
    if (top == MAX - 1) {
        printf("Stack overflow\n");
        return;
    }
    stack[++top] = value;
}
int pop() {
    if (top == -1) {
        printf("Stack underflow\n");
        return -1;
    }
    return stack[top--];
}
int main() {
    push(10);
    push(20);
    push(30);
    printf("%d\n", pop());   // Output: 30
    printf("%d\n", pop());   // Output: 20
    return 0;
}

Beyond browsers, compilers use stacks to track function calls, and text editors use them for undo operations. Any problem where you need to reverse the order of processing is a stack problem.

Queue: FIFO in Code

A queue follows First-In-First-Out (FIFO): the first element enqueued is the first dequeued, like people in a bus queue. The person who arrives first boards first, and the same logic applies to your data. Two pointers manage the structure: front tracks where the next removal happens, and rear tracks where the next addition goes. Unstop uses a ticket counter and people in a bus queue as real-world FIFO examples.

from collections import deque
# Create a queue
queue = deque()
# Enqueue: add to the rear
queue.append("task-1")
queue.append("task-2")
queue.append("task-3")
# Dequeue: remove from the front
print(queue.popleft())   # Output: task-1
print(queue.popleft())   # Output: task-2
print(queue)             # Output: deque(['task-3'])

Printers process jobs in queue order, and operating systems schedule processes this way. When fairness matters, where the first request gets served first, a queue is the structure.

Linked List: Nodes That Point Forward

A linked list is a sequence of nodes, each holding data and a pointer to the next node, allowing dynamic memory use. Unlike an array, a linked list does not need contiguous memory. Each node lives anywhere in memory, and the pointer connects them into a chain. This means you can grow and shrink the list freely, but you lose indexed access: finding the third element requires walking from the start.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
# Build a list: 5 -> 10 -> 15
head = Node(5)
head.next = Node(10)
head.next.next = Node(15)
# Traverse and print
current = head
while current:
    print(current.data, end=" ")   # Output: 5 10 15
    current = current.next

Linked lists shine when you need frequent insertions and deletions. Adding a node in the middle only requires changing a couple of pointers, whereas an array would demand shifting every subsequent element. The cost is the extra memory each pointer consumes.

What Is a Non-Linear Data Structure?

A non-linear data structure arranges elements in multiple levels or a network, so they are not in a single sequence. Each element can connect to several others, creating a hierarchy or a mesh. You cannot traverse all elements in one straight run; you must branch at each node. This makes them harder to implement, but they use memory efficiently, as GeeksforGeeks details. Trees, graphs, and heaps are the primary examples, and they power everything from file systems to social networks.

Non-linear structures trade implementation complexity for power. A tree organizes data with a clear hierarchy, and a graph models arbitrary connections. Each handles problems that linear structures simply cannot express.

Tree: Hierarchy With a Root

A tree has a root node and child nodes forming a hierarchy, with no cycles. Every node except the root has exactly one parent, and the structure branches downward. Family trees work exactly this way, as unstop points out: grandparents at the top, parents below them, children below that. In computing, a binary search tree (BST) is a common variant where each node has at most two children, and smaller values go left while larger values go right. AVL trees and binary trees are other types you will encounter.

1. Compare

   Compare the new value with the current node's value.

2. Go left or right

   If smaller, go left; if larger, go right.

3. Insert

   When you find an empty spot, place the new node there.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root
# Build a BST: 50, then 30 left, 70 right
root = insert(None, 50)
root = insert(root, 30)
root = insert(root, 70)
print(root.value)              # Output: 50
print(root.left.value)         # Output: 30
print(root.right.value)        # Output: 70

File systems on your computer are trees: the root directory branches into folders, which branch into more folders and files. Searching a sorted tree is fast because each comparison eliminates half the remaining nodes.

Graph: Nodes and Edges Without Rules

A graph is a set of vertices connected by edges, with no connection rules, unlike a tree. Any node can connect to any other node, and cycles are allowed. This freedom makes graphs the right model for road maps, where cities connect by highways in any pattern, and social networks, where people connect by friendships with no hierarchy. GeeksforGeeks notes that graphs are used for social and telephone networks precisely because of this flexibility.

# Adjacency list representation
graph = {
    "Alice": ["Bob", "Charlie"],
    "Bob": ["Alice", "David"],
    "Charlie": ["Alice", "David"],
    "David": ["Bob", "Charlie"]
}
# Print who Alice is connected to
print(graph["Alice"])   # Output: ['Bob', 'Charlie']
# Check if a connection exists
print("Bob" in graph["Alice"])   # Output: True

The key contrast with a tree: a tree is a graph with strict rules. Trees cannot have cycles, and each node has one parent. Graphs impose neither restriction. In the diagram above, notice how Alice connects to Bob and Charlie, but Bob and Charlie also connect to David — there's no single parent, so cycles can form. That's what makes it a graph, not a tree. Routing algorithms for GPS and recommendation engines for social media both rely on graph traversal.

Linear vs Non-Linear: The Table You Can Quote

This comparison table summarizes the key differences, so you can quote it directly in an interview. The distinctions come straight from GeeksforGeeks and unstop.

Use a linear structure when your data naturally forms a sequence and you need simple, predictable behavior. Use a non-linear structure when relationships between elements matter more than their order. For a deeper foundation in how data organizes in databases, read our guide to normalization in DBMS. That covers the rest of the syllabus.

Pick your favorite language and implement each structure from scratch: array, stack, queue, linked list, tree, graph. Run the code, print the output, and explain it out loud. Then try one LeetCode problem per structure to lock it in.