Thread: C linked list or hash table for matrix operations and representation

Originally Posted by anya

I want to have operations on matrix such as : delete first element and find i-th element.

Those don't really sound like quintessential matrix operations though. What does it mean to "delete first element"? What is the "i-th element" of this matrix?

Originally Posted by anya

Delete first element means to delete first column from matrix, and delete i-th element means to delete it-h column from the matrix.

Oh, so your matrix is in column-major order?

What I mean is that when people implement a matrix, a fairly common solution is to use an array of arrays such that the outer array is an array of rows and each inner array is an array of matrix entries. This way, we would use array notion for matrix[i][j] to denote the entry at the ith row and jth column, much like the subscript notation for denoting an entry in a matrix in mathematics. This is called row-major order. To remove the first column from a matrix represented in this way means removing the first element of each of the rows. This would be potentially very inefficient if "removing an element" means shifting the elements that come after by one position.

But your matrix, on the other hand, seems to require a representation where it is efficient to remove columns. We could still use a row-major ordering by having an array of linked lists such that each linked list corresponds to a row in the matrix and each node in each linked list corresponds to an entry in the matrix. This way, removing the ith element just requires linking the previous and next nodes to exclude it. Problem is, finding the ith element will take linear time, so if you want to remove a column in the middle, you're going to get time complexity of O(m * n). Alternatively, you can have a linked list of arrays such that each array corresponds to a column in the matrix (hence column-major order). This way, finding the ith column will take O(n) time, but deletion takes O(1) time.

Using a hash table does not appear appropriate since you have the notion of ith element, i.e., some kind of ordering.

I don't think you know what a hash table is, if you think it might have even the slightest suitability to the problem you describe.

But in any case, the answer is neither. An array should always be the first data structure you consider.
Even with having to copy elements over to remove a column, (which I might add is an extremely unusual and uncommon thing to do) it still tends to beat the time taken to follow pointers in a linked-list, due to what is known as the pre-fetcher.

O_o

Do you actually have a matrix? Or do you just have a table?

The combination implied seems more like you want to build data structure not a mathematics construct.

Soma