I've studied that Data Structures can be classified into Linear (arrays, stacks, queues and linked-lists) and Non-Linear (trees and graphs) data structures. flowchart of data structures -- image source: medium
Now, my question is that if linked-lists are "linear" data structures, then why are they used to implement trees, which are non-linear? Since trees have nodes that consist of the keys (or values) and pointers to more child nodes, aren't trees just more complex linked-lists? If they are, then how is the statement "linked-lists are linear data structures" justified?
This is how I actually got this question: I am currently learning data structures in C. So in order to implement the Tree data structure, I use structs, which consist of keys and pointers to the left and right children of each node.
typedef struct Node
{
int key;
struct Node *left;
struct Node *right;
} Node;
Then I wondered that I'm essentially implementing a linked-list (since linked-lists are also done using structs in C).
You are confusing different things. A tree is logical data-structure which is a special case of a directed graph without cycles.
A tree data-structure can be implemented in various ways. An array which stores indices of children, using actual pointers to memory of children (like in your example), and other ways. your struct is a specific implementation of a tree data structure but there are other implementations.
A 'linked list' typically reffers to specific implementation where elements point to each others memory. There is a one directional linked list, where element points to next one, or bi-directional, where element points to previous and next one.
If you implement trees with pointers and each node has only one child, then this is a special case where the implementation resembles a linked list.
Note: that a linked list may have a loop, while a tree never has a loop, because then it becomes graph (by definition). Also it is not common for a tree node to point back to its parent, only point to its children, while linked lists sometimes point to parent (previous element).
So linked list is an implementation of logical data structure which is called 'list'. This implementation uses pointers.
List can be implemented in other ways (arrays, histograms, hash tables with counters of amount of appearances of each elements, skip lists for O(log(n)) search etc).
A tree is a logical data structre which is commonly implemented using pointers, but has other implementations as well.
When tree is implemented using pointers, each 1 branch in a tree, resembles a linked list - so this is the sources of your confusion.