链表表示与数组表示的稀疏矩阵有何差异及优劣势？

Great question! Let's break down the key differences, advantages, and disadvantages between linked list (like cross lists) and array (triplet) representations of sparse matrices:

This approach stores non-zero elements as a collection of triplets (row, column, value) in an array. Here's how it stacks up:

Advantages #

• Dead-simple implementation: No pointer management or node creation required—just a standard array to hold triplets. It's easy to code, debug, and grasp for beginners.
• Lower memory overhead (for moderately sparse matrices): Each entry only stores three values, no extra pointer storage. For matrices where non-zero elements aren't extremely rare, this is more memory-efficient than linked lists.
• Faster random access: If you need to look up a specific position, you can iterate through the array (or even use binary search if the array is sorted by row/column), which is way quicker than traversing a linked list node by node.
• Easier sorting & batch operations: Arrays can be sorted by row, column, or value with minimal effort, making matrix operations like addition or transpose smoother when dealing with batches of elements.

Disadvantages #

• Costly insertions/deletions: Since arrays are contiguous, adding or removing an element means shifting all subsequent entries—this is an O(n) operation, which gets painful if you're modifying the matrix frequently.
• Poor for dynamic matrices: If the number of non-zero elements changes often, you'll need to resize the array constantly, leading to unnecessary overhead.
• Less flexibility for extreme sparsity: While it's better than a dense array, it still requires preallocating (or resizing) space, which isn't ideal for huge matrices with almost no non-zero elements.

This method uses nodes that link to other nodes in the same row and column, storing row/column indices, the value, and pointers to adjacent nodes. Here's its pros and cons:

Advantages #

• Blazing-fast dynamic updates: Inserting or deleting a non-zero element only requires adjusting a few pointers—no shifting elements around. This is O(1) time if you already have the position, perfect for matrices that change often.
• Ideal for extreme sparsity: For massive matrices with barely any non-zero elements, linked lists don't waste space on preallocated storage. Nodes are created on-demand, so you only use memory for what you need.
• Smarter complex operations: Matrix multiplication, transpose, or other advanced operations can leverage the dual row/column links to traverse elements more efficiently, without needing to sort entries first.

Disadvantages #

• Steeper learning curve & complex code: Managing pointers, handling edge cases (like empty rows/columns), and avoiding null pointer errors makes implementation way trickier than the array approach. Debugging linked list issues can be a headache.
• Higher memory usage: Each node needs extra space for pointers (e.g., a cross list node has at least two pointers in addition to row, column, and value). For matrices with many non-zero elements, this adds up to more memory than the array method.
• Terrible random access: To find a specific element, you have to start at the head of a row or column and traverse each node until you hit your target—this is O(n) time and much slower than array lookups.
• Worse cache performance: Linked list nodes are scattered in memory, so CPU cache can't optimize access like it does with contiguous array storage. This leads to slower overall read/write speeds.

• Go with array representation if your matrix is static, non-zero elements don't change often, and you need fast lookups or batch processing.
• Choose linked list representation if you're dealing with a dynamic matrix (frequent adds/deletes) or an extremely sparse, large-scale matrix.

内容的提问来源于stack exchange，提问作者user7752488