C++

Forum

 
How to do a linked list of linked lists?

Pages: 12
Metalman488 (60)
I am trying to figure out how I would make a linked list that contains other linked lists as the nodes. I am very new to linked lists, but I think I am beginning to understand them better, but this really confuses me.
I didn't think the lists had names because the tutorials just start with something like: (I am needing to use doubly linked lists if that matters)

1
2
3
4
5
6
 
  struct node
{
	string str;
	node *prv = NULL;
	node *nxt = NULL;
};


I thought that this was just to tell the program what a node was, but now I'm thinking this is how I would name a list, so if I did:

1
2
3
4
5
6
 
struct word
{
	string str;
	word *prv = NULL;
	word *nxt = NULL;
};


Would that mean that I would have a list named word? So if I did this, then made another one with "lines" instead of "word", I would then have the beginnings of two linked lists?

If so, how would I make the second one to hold linked lists instead of strings? Would I just put a pointer to the other lists head?

If not, then how would I do this?

I am having to write a program that will read string data from a file. It is supposed to store each word in a line as a node in a list, then I am supposed to store each of those lists in a list that contains the lines. I also have to remove the symbols from the lines.

So if these are the lines:
xyz abc
fun sad book 123,678+1000
a AA aaa123, $%
[X]

Then "xyz" and "abc" would be nodes in one list, "fun", "sad", "book", "123", "678", and "1000" would be nodes in another list, and so on. Then I would need to have a list where each of those lists is a node.

So the other problem I have is that I won't know the exact number of lines or the number of words in a line, so how would I deal with that? How would I make it create lists for each line when I don't know how many there will be?

Sorry if I'm asking way too many questions, but I'm not that good at coding yet and I had never even heard of linked lists until a couple of days ago and this is really stressing me out.

I have looked online for help a lot before posting this and I will continue to look it up while I wait for an answer, so please don't tell me to go look it up.

Thanks in advance!

EDIT: I forgot to mention that I can't use the linked list template in the STL library.

EDIT: I just got done making a LinkedList class that works. So far it has a insert function and a print function. I'm thinking that this is how I am supposed to create different linked lists with names I can reference. I am still not sure how to do a linked list of linked lists though. My current class just has this for the node:
1
2
3
4
5
6
7
8
9
10
11
12
 
 
struct node
{
	string str;
	node *nxt = NULL;
	node *prv = NULL;
	node(string s)
	{
		str = s;
		nxt=prv=NULL;
	}
};


I'm also not sure how to use this class when I don't know the total number of lines. I could create an instance for each line, but I don't know how many to create.
Last edited on
closed account (48T7M4Gy)
If you have a templated class for a single linked list of integers, SINGLE_LL<int> xyz;

And a single linked list of single linked lists of integers would be; SINGLE_LL<SINGLE_LL<int>> abc;

This is the same as a STL vector of vectors of int's, <vector<vector<int>>

I doubt whether you can mix types, so strings might be a good choice.

The number of items in each list is/can be managed via the struct or class individually for each object.
Metalman488 (60)
If you have a templated class for a single linked list of integers, SINGLE_LL<int> xyz;


I'm not sure what you mean by that... I just got done making a linked list class, so that I can just make different linked list objects. Is that what you mean? Or is that something from the linked list template in the STL library?
jonnin (11429)
what he is saying is that if your linked list is generic via a template, then you can make it accept itself as the template argument, making it 2-d.
A common example of this is stl vectors:
vector<vector<int>>; //2d int vector.

a 2-d linked list will be a nightmare to search and use; I can't think of a less efficient structure.

if you don't do it via a template, its not too hard.

struct node
{
node * down;
node * across;
type data;
};

This is actually a full 2d construct; you can go across and then down again, so you could iterate over the diagonal or something if you wanted to connect up the pointers that way. There are other ways to do it that waste less memory (this one has excessive pointers that won't be used if you just want down, then across, nothing more logic). But this is simple to code.

If you wanted to avoid wasting space you would want to either do the template of templates, or if you are not ready to tackle that, 2 list classes, an inner and an outer.

you can also do this monster. This would get ugly in a hurry, and I don't recommend it, but it might allow some code tricks the above did not.
node
{
node**both; //node[1][3] is 1 down, 3 across, right? you can do a type of direct access if you know the position...
type data;
}

note that a list of lists is a form of a tree:
1
2
3
4
5
6
7
 
        x            //entry point
     ///\\\
     abcdef      //outer list
     ||||||
     ABCDEF   //inner list first values
     ||||||
     GHIJKL   //inner list 2nd values,
... etc

Last edited on
closed account (48T7M4Gy)
@OP
Check out the code in section 3 of this. It shows how template work. Instead of int or string etc T is the key to the template idea.

Last edited on
Metalman488 (60)
If you wanted to avoid wasting space you would want to either do the template of templates, or if you are not ready to tackle that, 2 list classes, an inner and an outer.


I think this sounds like what I want to do. Do you mean that one list class would have a node structure that stores strings, and the other would store lists?

And to store lists would I create a node structure kind of like this?
1
2
3
4
5
6
 
struct lines
{
     node *rowHead;
     lines *prev = NULL;
     lines *next = NULL;
};


I'm also going to need to print everything in reverse. Each of the lines and every word in the line.
So 
1
2
 
abc efg hij
klm nop qrs

would become
1
2
 
qrs nop klm
hij efg abc


I think I know how to reverse one list, but I'm not sure how to reverse both.

I also have a new problem.... I was going to use arrays to get the data out of the file, then store the info from the arrays into the lists, but I just found out that I am not allowed to do that for some reason. So how would I get the words from each line into a linked list? In other words, how do I get it to start a new list each time it reaches the end of a line?
Last edited on
closed account (48T7M4Gy)
If you model your class on the reference I posted above then a list of lists (of strings) is quite easy to implement and get results with only the usual linked list functionality encountered in introductory courses.

No STL, no searching or nightmares are involved. Reversals are simply push'ing and/or pop'ing from the back or the front of the list. Search functionality with a single linked list is inefficient, the links only go in one direction, that's the nature of the list structure. But I can't see how searches are required with what you have so far shown.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
#include <iostream>

#include "single_linked_list.h" // <-- see above reference and modify as required

int main()
{
    SINGLE_LL<std::string> s1, s2;
    s1.pushFront("xyz"); // or read string from text file word by word
    s1.pushFront("abc");
    
    s2.pushFront("fun");
    s2.pushFront("sad");
    s2.pushFront("book");
    s2.pushFront("123");
    s2.pushFront("678");
    s2.pushFront("1000");
    
    SINGLE_LL<SINGLE_LL<std::string>> s3;
    s3.pushFront(s1);
    s3.pushFront(s2);
    
    std::cout << "          List s1 has: " << s1.getNoItems() << " items\n";
    std::cout << "          List s2 has: " << s2.getNoItems() << " items\n";
    std::cout << "List of lists s3 has: " << s3.getNoItems() << " items\n";
    
    std::cout << "s1: " << s1 << '\n';
    std::cout << "s2: " << s2 << '\n';
    std::cout << "s3: " << s3 << '\n';
    
    return 0;
}




          List s1 has: 2 items
          List s2 has: 6 items
List of lists s3 has: 2 items
s1: abc xyz
s2: 1000 678 123 book sad fun
s3: 1000 678 123 book sad fun abc xyz
Program ended with exit code: 0
closed account (48T7M4Gy)
DUPLICATE POST

http://www.cplusplus.com/forum/beginner/221652/
Metalman488 (60)
Search functionality with a single linked list is inefficient


You're right about me not needing to search it and singly lists are probably good enough, but I have to use doubly linked lists for this. I was going to take a look at that link again, but I don't see it anymore.
Metalman488 (60)
Ok so I've made a lot of progress on most of this. I did end up creating a template for my linked list class and I now have a list of lists that I can properly fill and print out (forwards and reverse). The issue that I am having now is that I have to go through and delete any nodes that contain numbers. I have made a delete function that accepts a string, then deleted the node containing the string if that node contains numbers. It works, but only for one linked list. I cannot figure out how to use it with my list of lists.

I ended up getting it to print by making the node its own class within the template and then overloading the << operator.

(And kemort, I think I understand why you got onto me for duplicating now. That other post was originally supposed to just be a different problem I was having on the same program, not a duplicate, but it did end up turning into a duplicate, so I will try to avoid that in the future.)
closed account (48T7M4Gy)
If you have a list of, lists of strings, you should be able to 'extract/display/add/delete/modify' a single list (ie a node) from the list of lists. The node here contains data in the form of a list of strings.

Once you have done that you should be able to process the extracted list as just any other simple list, node by node. The node this time contains data in the form of a single string.

Look carefully at what my code above does, s1 and s2 are two lists of strings. s3 is a list of 2 lists, list s1 and list s2.

There are only two templated classes - Node and SINGLE_LL.

Remember that a number can be a number or a <string>
Metalman488 (60)
I don't understand how you can just run cout << s3 like that. Do you have << overloaded? Because that was the only way to get it to print the lists of lists with cout like that.

I've been trying do something kind of like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
template <class M>
void LinkedList<M>::toDelete(LinkedList<LinkedList<string> > L)
{
	Node<M> *n = L.head;
	LinkedList<string> line = n;
	Node<M> *p = line.head;
		while(n != NULL)
		{

				while(p != NULL)
				{
					if(isdigit(p->data[1]))
						line.deleteNode(p->data);
					p = p->next;
				}
				n = n->next;
		}

}


but that doesn't work at all. I'm just getting confused on how I would extract a list to be able to perform function on it, then move onto the next list.

When i do that if(isdigit(p->data)) bit when I only have one list (on a different program I use to test things), it works just fine and it does what I want, but the list isn't templated on that tester program.

I've made an iterator class, but when I try to create an iterator object like
LinkedList<string>::iterator it;
it tells me that it cannot be resolved
Last edited on
Metalman488 (60)
So now i have added two functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template <class M>
void LinkedList<M>::Passer()
{
	Node<M> *n = head;

	while(n != NULL)
	{
		cout << "Test: " << n->data << endl;
		LinkedList<string> line;
		line.deleteIf(n->data);
		n = n->next;

	}

}

and
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template<class M>
void LinkedList<M>::deleteIf(LinkedList<string> L)
{
	Node<M> *temp = L.head;

	while(temp != NULL)
		{
		if(isalpha(temp->data[1]))
			return;
		else if(isdigit(temp->data[1]))
				L.deleteNode(temp->data);

		temp = temp->next;
		}
}


In the main function I pass the list of lists to the passer function. I have an equation that multiplies the number of nodes by (8+8+sizeof(string)) to determine the memory used by the list and I can tell by the decrease in memory used after these functions that they do delete the amount of nodes that they should, but when I try to print the list of lists AFTER the functions, it doesn't display anything, not even the memory.

Any idea why this might be happening and how to fix it?

EDIT: I think it has something to do with my delete function because I went to my tester program and the delete function works perfectly IF I am printing normally. If I try to print in reverse, it messes up. It did still display one node, but not the other that it should have displayed. However, I tried to see what happens if I try to print my lists of lists normally instead of in reverse and it didn't do any good.

Here is my delete function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
template <class M>
void LinkedList<M>::deleteN(string delItem)
{
	counter--;

	Node<M>* temp;
	Node<M>* prev = NULL;

		if (head->data == delItem)
		{
			temp = head->next;
			delete head;
			head = temp;
		}
		else
		{
			temp = head;

			while(temp != NULL && temp->data != delItem)
			{
				prev = temp;
				temp = temp->next;
			}

			if(temp)
			{
				prev->next = temp->next;
				delete temp;
			}
		}


}
Last edited on
Metalman488 (60)
Ok I am really having trouble with this. Now I am thinking that it may not be deleting the correct nodes, it's just decrementing my count correctly. This is the only explanation I can think of because if these functions were working correctly, then the list of lists would print out correctly. I don't know why they aren't giving me any errors if they are incorrect, but I can't think of anything else.

I would really appreciate someone's help on this. This is really stressing me out.
closed account (48T7M4Gy)
@OP
Yes, the << operator is overloaded for both the Node and SINGLE_LL classes.

Instead of processing the words once they're in the list why not process them before they go in?

Maybe this throws light on deleting nodes https://visualgo.net/en/list
Metalman488 (60)
Instead of processing the words once they're in the list why not process them before they go in?


That's what I did originally, but apparently I'm not supposed to do that. I'll take a look at that link you posted.

I do have a new delete function though, this one works in my tester program when I try to print in reverse, but I still have no luck on my list of lists.
Here it is:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
template <class M>
void LinkedList<M>::deleteN(string delItem)
{
	counter--;

	Node<M> *Curr;
	Node<M> *Trail;

	bool fnd;

	if (head == NULL)
	{
		cout << "List is empty!" << endl;
	}

	else if (head->data == delItem)
	{
		Curr = head;
		head = head->next;

		if(head != NULL)
			head->prev = NULL;
		else
			tail = NULL;

		delete Curr;
	}

	else
	{
		fnd = false;
		Curr = head;

		while(Curr != NULL && !fnd)
			if(Curr->data == delItem)
				fnd = true;
			else
				Curr = Curr->next;

		if(Curr == NULL)
			cout << "Item to be deleted is not here!" << endl;
		else if (Curr->data == delItem)
		{
			Trail = Curr->prev;
			Trail->next = Curr->next;

			if(Curr->next != NULL)
				Curr->next->prev = Trail;

			if(Curr == tail)
				tail = Trail;

			delete Curr;
		}

	}
}
Last edited on
closed account (48T7M4Gy)
OK. If you have to there is no reason you can't have relevant read and break up/tidy up methods in List.
Metalman488 (60)
OK. If you have to there is no reason you can't have relevant read and break up/tidy up methods in List.


I'm not sure what you mean. If you are talking about breaking up/tidy up the strings, I can do some of that. I found out that the only symbols will be commas and maybe apostrophes and I am allowed to do away with those before they go in, and I am also allowed to separate the letters from numbers before they go in (abc123 to abc 123). All I have to do is delete any nodes that contain numbers (they will be strings).

And I did go through all those slides on that link you sent me. Thanks for sending that to me, it was pretty informative, but I'm still not sure how to apply it to a list of lists.
Last edited on
closed account (48T7M4Gy)
All I have to do is delete any nodes that contain numbers (they will be strings).
Perhaps iterate through the list and if any Node contains data where the string is made up of all digits (because you have already separated them out, even though they are stored as strings rather than numbers) then delete that Node.
Metalman488 (60)
That's exactly what I was thinking and that's how I do it in my tester program. The part I can't figure out it how to do that with a list of lists.
I use this in my tester program:
1
2
3
4
5
6
7
 
Node *n = head;
	while (n != NULL)
	{
		if (isdigit(n->data[1]))
			deleteN(n->data);
		n=n->next;
	}

and it works fine, but I can't seem to figure out how to do that in my templated list of lists. The Passer and deleteIf functions a few posts above were my attempts at doing that.
Pages: 12