Arrays are predictable. You store items one after another in a neat, contiguous block of memory. This sequential layout makes it fast to access any element if you know its index, but it comes at a cost. Inserting or deleting an item in the middle of a large array requires shifting every subsequent element, which can be painfully slow.

To overcome this, we can break free from sequential memory and organize data based on relationships. This leads us to non-linear structures, where elements are connected via links, or pointers, rather than being physically next to each other.

A linked list is a chain of nodes. Each node contains two things: the data it's storing and a pointer to the next node in the sequence. The list has a starting point, called the head, and the last node points to null, signaling the end of the chain.

The simplest version is a singly linked list, where traversal is one-way. A more flexible version is the doubly linked list, where each node has a pointer to the next node and the previous node. This extra pointer uses more memory but allows you to move backward and forward through the list. This is perfect for features like a web browser's back button or an editor's undo/redo functionality.

The main trade-off with linked lists is search time. To find an element, you must start at the head and visit each node one by one until you find what you're looking for. This is an $O(n)$ operation, meaning the search time grows linearly with the number of items. For insertions and deletions, linked lists shine with $O(1)$ performance, provided you already know where the change needs to happen.

What if we need fast insertions and fast searches? This is where tree structures come in. A Binary Search Tree (BST) is a node-based structure that imposes a strict ordering rule.

This rule makes searching incredibly efficient. Instead of checking every element, you start at the root and make a simple decision at each node: go left if your target is smaller, or go right if it's larger. With each step, you discard roughly half of the remaining nodes. This reduces the average search time from $O(n)$ to $O(\log n)$, a massive improvement for large datasets.

Unlike linear structures, there are multiple ways to visit, or traverse, every node in a tree. The three most common recursive methods are defined by when we process the current node's data relative to its children:

Each traversal method serves a different purpose. Visiting nodes in-order on a BST will always give you the elements in ascending sorted order. Post-order is useful for deleting a tree because you can safely delete a parent node only after its children have been deleted.

Let's test your understanding of these non-linear data structures.

Choosing the right data structure involves understanding these performance trade-offs. Linked lists offer fast insertions at the cost of slow searches, while BSTs provide a balanced approach for dynamic datasets.