Array of pointers pointing to linked lists

[klop]

Hello,

Lets say I have an unknown number of linked lists (the user inputs the number), and a for loop creates them, one by one. I want to have an array of pointers that each cell of it will point to the head of each list.

This is how I define my list (I saw no reason to post the complete code which shows how the list is created):

typedef struct List_node
{
	int key;
	int i, j;
	struct List_node *next,;
}List_node;

typedef struct List
{
	List_node *head;
}List;

1. How do I define this kind of array?
2. How do I make the first cell point to the head of the first list, the second cell point to the head of the second list, and so on? I mean, what is the proper syntax for it?

I am programming using C.

edit - an illustrative image:
http://i.stack.imgur.com/TMf3x.jpg

Thank you.

[sujitnag]

you should follow data structure book in c or c++. you can found how to implement link list in c or c++

tanenbum is a well known writer.

[klop]

Hi,

I have already implemented a linked list, no problems there. What I'm not sure about is the array of pointers to the lists heads, like I wrote.

I'm using C, by the way.

[sujitnag]

graphical representation of your multiple list .


|------| __________________
|*L1 |__________|___|___|____|___|____|
|------| __________________
|L2 |-------------|___|___|____|___|____|
|------|
| .
| .
| .
|------| __________________
|Ln |--------------------|___|___|____|___|____|
--------

am I right?

[klop]

Right. Nothing special there - just a multiple simple linked lists.
Just imagine having an array there where each cell is pointing to the list's head. (I'm not sure whether by L1,L2,...,Ln you mean the name of the lists or if it's an array).

[sujitnag]

simple when a new list is created you store the List_node address to the member head of list.
what are the condition to create a new list it is implementation factor.
you not clearly say any thing about your implementation. it is only small part so coding is not possible for me.

[anup30]

do you want to store all heads or all objects?
latter seems more meaningful to me.

[klop]

Hi,

I edited the post, check the image. Basically you see two arrays, rows and columns (lets focus on one for now, the rows for example,because if I know how to do one the other will be the same). So each cell in the array points to the head of each list. obviously each head has a next pointer that points to the next list node, and so on. So, I'm not sure which of what you meant is true.

Basically the point is that if I have a list L that is created multiple times, thus overwritten every time, it would still be possible for me to access them easily (for example, print them one by one using a for loop). I'm just not sure how to define such an array, thats all.

Basically the image shows a matrix, but I chose to represent the matrix with a series of one-dimensional vectors, where each list is a vector.

[dhayden]

Why not just vector<List> or possibly vector<List*> if you must allocate the lists elsewhere?

[klop]

dhayden, can you please elaborate?

[dhayden]

Sorry. I missed the part about this being in C instead of C++. You can't use vector<> unless it's C++.

In C you can do this by having each element below to two lists: one for the row and one for the column:

typedef struct List_node
{
	int key;
	int i, j;
	struct List_node *rowNext; // next node in the row
        struct List_node *colNext;  // next node in the column.
}List_node;

typedef struct ListArray
{
	List_node *heads;
        unsigned size;  // number of items
}List;

struct Matrix {
    List rows, cols;
};

Now if user wants a matrix with dimensions up to 500x1000:
struct Matrix m;

m.rows.heads = calloc(1000, sizeof(List_node*));
m.rows.size = 1000;
m.cols.heads = calloc(500, sizeof(List_node*));
m.cols.size = 500;

I suggest you create a function:
List_node *findOrAddNode(Matrix *m, int row, int col);
This will find the node corresponding to matrix[row][col]. If it doesn't exist then it will add the node and set its value to zero.

[anup30]

#include <iostream>
#include <list>
#include <vector>
using namespace std;


struct TT {
	int a;
	string str;
	TT (int a1=0, string s1 = ""): a(a1), str(s1) {}
};


int main() {
	
	TT tt1(0, "zero");
	
	list <TT> list1;
	
	list1.push_back(tt1); // include a TT object.
	
	list1.emplace_back(1,"one"); // create at the end.
	list1.emplace_back(2,"two");
	
	list1.emplace_front(-5,"negative"); // create at the front
	
	vector<list<TT>> vect; // contains linked lists
		
	vect.push_back(list1);
	
	for(auto x: vect[0]) {
		cout << x.a << " " << x.str << endl;
	}	
	
	vect.clear();
	
  
	return 0;
}

[klop]

dhayden,

I'm not really sure I understand what you wrote. The matrix struct - is that the Row and columns arrays as in the image (R and C)? Those arrays are really all I care about and all I need to know is how to get each cell of those arrays pointing to the heads of each list.

anup30,

Thank you but I'm using C.

[dhayden]

Yes, the row and column arrays in the Matrix struct are the ones you're talking about. Each element in these arrays is the head pointer of a list.

[dhayden]

Do you have the code to add an element to the sparse matrix? How are you going to indicate that an element is in both a row and a column? Put another way, if you need to examine all elements in row r, how will you do it? If you're going to examine all elements in column c, how will you do that?

[klop]

Yes, the last two things you said are the real challenges, I know that. While printing each vector is very easy, connecting them with the down pointer (or colNext as you call it) was the very hard part.
About adding an element I do have a code but it's pseudo-code.

This thing is really a homework/bonus assignment, so instead of wasting time I don't really have (college student, finals coming up) and treating it as a matrix, I just created vectors and pretend it's a matrix.

So I know how to define the rows/columns arrays, that's good.
How do I assign each element of the array to the head of each list? (i - index of a for loop)

1) *(rows + i) = *L ?
2) *rows[i] = *L ?

Without the asterixs, maybe? with an ampersand somewhere?

Do understand, a program I wrote is already working for me (so you know I'm not asking and asking and not doing anything to try on my own). In my program I wasn't sure whether to define the arrays as List or List_node (in which case it was rows[i]=L->head), and worse, when debugging I saw that the rows array (I tried only the rows first before moving on with the columns as well) did not get the same address as the head of each list. So while it did work, I did not feel it was really "proper" and correct. That's why I'm asking here.