Data Structure Basic Concepts
Before formally learning various data structures, you need to master the classification methods of data structures, the concept of abstract data types, and review the core C language knowledge points closely related to data structures.
Classification of Data Structures
Data structures can be classified from two dimensions: logical structure and storage method. Understanding these two classification methods helps you quickly determine which type of data structure should be chosen when facing specific problems.
The figure above shows the complete classification system of data structures, explained one by one below.
Classification by Logical Structure
Logical structure describes the abstract relationships between data elements, without involving the actual storage method of data in memory.
| Type | Element Relationship | Typical Example | Applicable Scenario |
|---|---|---|---|
| Linear Structure | One-to-one sequential relationship | Arrays, linked lists, stacks, queues | Data has an obvious order, such as to-do lists and browsing history |
| Tree Structure | One-to-many hierarchical relationship | Binary trees, BST, heaps | Data has hierarchical ownership, such as file system directories and organizational structures |
| Graph Structure | Many-to-many network relationship | Directed graphs, undirected graphs, weighted graphs | Relationships between data are complex, such as social networks and map navigation |
Classification by Storage Method
Storage method describes the actual organization of data in memory.
| Type | Characteristics | Typical Example | Trade-off |
|---|---|---|---|
| Sequential Storage | Elements are stored one by one in contiguous memory space | Arrays, stacks/queues implemented with arrays | Fast access (O(1)), but slow insertion and deletion, fixed size |
| Linked Storage | Elements can be stored scattered, connected via pointers | Linked lists, trees, graphs (adjacency list) | Fast insertion and deletion, but does not support random access, extra pointer overhead |
| Indexed Storage | Establish an additional index table to locate data | Hash tables (indexed via hash functions) | Extremely fast lookup, but requires extra space to store the index structure |
The same logical structure can be implemented with different storage methods. For example, a stack (logically a linear structure) can be implemented either with an array (sequential storage) or a linked list (linked storage). Which implementation is chosen depends on the specific application's requirements for access speed, insertion/deletion efficiency, and memory usage.
Abstract Data Type (ADT)
Abstract Data Type (ADT)is a core concept in the study of data structures.
It refers to an abstract description of a set of data and a set of operations defined on that data, caring only about "what to do," not "how to do it."
Take "stack" as an example to understand ADT:
| ADT level (what to do) | Implementation level (how to do it) |
|---|---|
| Define operations: push, pop, peek | Implement with array: maintain an array + top pointer |
| Define behavior: Last In, First Out (LIFO) | Implement with linked list: use the linked list head as the top of stack |
| Specify constraints: operations can only be performed at one end | Both implementations satisfy the ADT definition, but have different performance characteristics |
This idea of "separation of interface and implementation" is the cornerstone of modular design in modern software engineering.
When you use a stack, you only need to know how to use operations such as push and pop, without needing to care whether the underlying implementation is an array or a linked list—this is exactly the value of ADT.
Review of C Language Basics
Before learning data structures, you need to master the following three core C language knowledge points, which appear throughout almost all chapters of this tutorial.
Pointer
A pointer is one of the most important and flexible features in C. It stores the memory address of another variable, allowing indirect access and manipulation of the target variable.
Example
int main() {
int num = 42; /* ordinary integer variable */
int *ptr = # /* ptr is a pointer to int, storing the address of num */
printf("num value: %d\n", num); /* Output: 42 */
printf("address of num: %p\n", &num); /* Output: 0x16d2f2f38 (example address) */
printf("address stored in ptr: %p\n", ptr); /* Output: same as above */
printf("value dereferenced by *ptr: %d\n", *ptr); /* Output: 42, * is the dereference operator */
*ptr = 100; /* Modify the value of num through the pointer */
printf("after modification, num = %d\n", num); /* Output: 100 */
return 0;
}
Core uses of pointers in data structures:
| Use | Example |
|---|---|
| Build connections between dynamic nodes | In linked list nodes,nextpointers; in tree nodes,left/rightpointers |
| Indirectly access and modify data | Use pointer parameters to let functions modify the values of external variables |
| Dynamic memory management | mallocReturns the starting address of allocated memory, which must be received with a pointer |
| Avoid copying large amounts of data | When passing large structs to functions, passing pointers is more efficient than passing by value |
What beginners most easily confuse is
*and&the usage of * and &: in declarations,int *p* indicates p is a pointer type; when using,*p* indicates dereferencing (getting the value);&x& indicates taking the address. These are two completely different operators, and understanding this difference is the prerequisite for using pointers well.
Structure (struct)
A struct allows combining multiple data of different types into a custom type, and is the basic unit for building composite data structures such as linked list nodes and tree nodes.
Example
#include <string.h> /* header file for strcpy */
/* Define linked list node struct */
struct Node {
int data; /* Data field: stores actual data */
struct Node* next; /* Pointer field: points to the next node */
};
/* Define student information struct */
struct Student {
int id; /* Student ID */
char name[50]; /* Name, character array */
float score; /* Score */
};
int main() {
/* Create node */
struct Node node1;
node1.data = 10;
node1.next = NULL; /* NULL means there is currently no next node */
printf("node1.data = %d\n", node1.data); /* Output: 10 */
/* Create student record */
struct Student stu;
stu.id = 1001;
strcpy(stu.name, "EXAMPLE"); /* strcpy: copy string to character array */
stu.score = 95.5;
printf("ID: %d, Name: %s, Score: %.1f\n",
stu.id, stu.name, stu.score);
/* Output: ID: 1001, Name: EXAMPLE, Score: 95.5 */
return 0;
}
Structs combined with pointers enable flexible dynamic data structures. For example, the self-referential structure of a linked list node (struct Node* nextpoints to the next node of the same type) is exactly the implementation basis of linked lists.
Dynamic Memory Allocation
Dynamic memory allocation allows a program to request and release heap memory at runtime as needed, and is the key to building data structures with variable size (such as linked lists and trees).
C provides four core functions:
| Function | Functionality | Example |
|---|---|---|
| malloc | Allocate memory of the specified byte size, contents uninitialized | int* p = malloc(10 * sizeof(int)); |
| calloc | Allocate memory and initialize to zero | int* p = calloc(10, sizeof(int)); |
| realloc | Resize already allocated memory | p = realloc(p, 20 * sizeof(int)); |
| free | Free allocated memory and return it to the system | free(p); |
Example
#include <stdlib.h> /* header file for malloc, free */
int main() {
int n = 5;
/* malloc: allocate contiguous space for n ints on the heap */
int* arr = (int*)malloc(n * sizeof(int));
/* Check whether allocation succeeded; malloc returns NULL on failure */
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1; /* Abnormal exit */
}
/* Use dynamically allocated memory like a normal array */
for (int i = 0; i < n; i++) {
arr[i] = (i + 1) * 10; /* Assign: 10, 20, 30, 40, 50 */
}
printf("Dynamic array contents: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* Output: Dynamic array contents: 10 20 30 40 50 */
free(arr); /* Free memory to prevent memory leaks */
arr = NULL; /* Good practice: Set the pointer to NULL to prevent wild pointers */
return 0;
}
Other extensionsThe C language does not automatically reclaim dynamically allocated memory. Each time
malloc(orcalloc) must have a correspondingfree, otherwise it will cause memory leaks. In real projects, memory leaks will gradually exhaust system resources and eventually cause the program to crash. This is one of the most common mistakes made by C language beginners.