Recommended Reading

Complete Source Code | C Language Design and Implementation of Employee Attendance System

Notes Version | A Very Concise Summary of C Language Knowledge!

Latest C Language Interview Questions Summary PDF Detailed Version

Understanding | Essential Skills for C Language Programming—GDB Debugging

C Language Dynamic Memory Management: From Beginner to Proficient, Understand Thoroughly in One Article

Main Content

The most commonly used and core data structures in C language development can be divided into linear and non-linear two categories:

1. Linear Data Structures

In these structures, data elements are arranged in order.

1. Array

• Description: The most basic data structure, a contiguous block of memory used to store elements of the same type.
• Characteristics: Accessed via index (subscript), very fast (O(1)). However, the size is fixed, and the efficiency of inserting and deleting elements is low (O(n)).
• Uses: To store data sets of known fixed size, such as caches, lookup tables, matrices, etc.

2. Linked List

• Description: Composed of a series of nodes, each containing data and a pointer to the next node. Does not require contiguous memory.
• Variants:
• Single Linked List: Each node points only to the next node.
• Double Linked List: Each node points to both the previous and next nodes, supporting traversal in both directions.
• Circular Linked List: The tail node points to the head node, forming a loop.
• Characteristics: Dynamic size, high efficiency for insertion and deletion (O(1)). However, accessing specific elements is inefficient (O(n)), and additional memory is required to store pointers.
• Uses: Implementing stacks, queues, memory pools, managing variable-length data, etc.

3. Stack

• Description: A restricted linear table that follows the Last In First Out (LIFO) principle. Only allows insertion (push) and deletion (pop) operations at one end (the top of the stack).
• Implementation: Typically implemented using arrays (static or dynamic) or linked lists.
• Characteristics: Simple operations, high efficiency.
• Uses: Function call stack, expression evaluation, bracket matching, undo functionality, depth-first search (DFS).

4. Queue

• Description: A restricted linear table that follows the First In First Out (FIFO) principle. Elements enter from the rear and leave from the front.
• Variants:
• Circular Queue: When implemented with an array, it treats the array as a ring to efficiently utilize space.
• Priority Queue: Elements have priorities, and the order of removal is based on priority rather than insertion order. Typically implemented using a heap.
• Deque (Double-Ended Queue): Allows insertion and deletion operations at both ends.
• Implementation: Commonly implemented using linked lists or circular arrays.
• Uses: Task scheduling, message queues, breadth-first search (BFS), printer buffering.

2. Non-Linear Data Structures

5. Tree

• Description: A hierarchical data structure composed of nodes and edges, where each node has zero or more child nodes.
• Common Types:
• Uses:Indexing in databases and file systems.
• Uses:Autocomplete in search engines, spell checking, IP routing tables.
• Uses:Efficiently implementing priority queues and heap sort algorithms.
• Binary Search Tree: In a binary search tree, all nodes in the left subtree have values less than the root node, and all nodes in the right subtree have values greater than the root node. In-order traversal yields a sorted sequence.
• Balanced Binary Search Tree: Such as AVL trees and Red-Black trees, which ensure the height of the tree is approximately logarithmic through self-balancing operations, preventing degeneration into a linked list and ensuring search efficiency of O(log n).
• Binary Tree: Each node has at most two child nodes (left subtree and right subtree).
• Heap: A special complete binary tree. The value of the parent node is always greater than or equal to (max heap) or less than or equal to (min heap) any child node’s value.
• Trie (Prefix Tree): Used for efficient storage and retrieval of a set of strings. Each edge of the tree represents a character.
• B-Tree/B+ Tree: A multi-way search tree where a node can have multiple child nodes. Significantly reduces the number of disk I/O operations.

6. Graph

• Description: A collection of vertices and edges connecting the vertices.
• Representation Methods:
• Adjacency Matrix: Uses a two-dimensional array to represent the connection relationships between vertices. Fast lookup, but wastes space for sparse graphs.
• Adjacency List: Uses arrays and linked lists (or arrays of arrays) to represent. Each vertex maintains a linked list storing the vertices it is connected to. Saves space and is the more commonly used method.
• Uses: Social networks, map navigation, network routing, state machine modeling.

7. Hash Table

• Description: Accesses records by mapping keys to a position in an array using a hash function, achieving nearly constant time (O(1)) lookup.
• Key Issues:
• Chaining: Stores key-value pairs that collide in a linked list at the same position (most common).
• Open Addressing: Uses probing algorithms to find the next empty slot in the array.
• Hash Function Design: Aims for uniform distribution of keys to reduce collisions.
• Collision Resolution:
• Characteristics: Average time complexity for lookup, insertion, and deletion is very high. However, in the worst case, it may degrade to O(n).
• Uses: Implementing dictionaries or mapping structures, compiler symbol tables, caches (like Memcached), and deduplication of sets.

Summary

Data Structure	Advantages	Disadvantages	Typical Applications
Array	Fast random access	Fixed size, slow insertion and deletion	Fixed size collections, lookup tables
Linked List	Dynamic size, fast insertion and deletion	No random access, high memory overhead	Stacks, queues, dynamic lists
Stack	LIFO, simple implementation	Access is restricted	Function calls, DFS, undo
Queue	FIFO, simple implementation	Access is restricted	Task scheduling, BFS, buffering
Tree (BST)	Fast search (if balanced)	Can be unbalanced, complex operations	Dynamic ordered data collections
Heap	Fast access to max/min value	Can only access root node	Priority queues, heap sort
Hash Table	Extremely fast operations on average	Slow in worst case, unordered	Dictionaries, caches, fast lookups
Graph	Strong modeling capability for relationships	Complex algorithms	Networks, path planning, recommendation systems

How to Choose?

1. Need fast random access? -> Array
2. Need frequent insertions and deletions? -> Linked List
3. Need LIFO/FIFO? -> Stack/Queue
4. Need fast lookup, insertion, deletion (key-value pairs)? -> Hash Table
5. Data needs to remain ordered? -> Balanced Binary Search Tree (like Red-Black Tree)
6. Need efficient access to max/min value? -> Heap
7. Need to represent network relationships? -> Graph

Mastering the principles, implementations, and applicable scenarios of these fundamental data structures is essential for becoming an excellent C language programmer. In practical projects, they often form the core components of complex algorithms and system functionalities.

--End--

If you have read this far, it means you like the articles from this public account. Please pin (star) this public account C Language Chinese Community, so you can receive notifications immediately!

In this public account, reply: 1024 to receive a free C language learning gift package.

If you think the content is good, please give me a thumbs up!