How to do a linked list of linked lists?

[48T7M4Gy]

Write it up as a method.

void List::delete_numbers()
{
    Node *n = head;
	while (n != NULL)
	{
		if (isdigit(n->data[1]))
			deleteN(n->data);
		n=n->next;
	}

}

[Metalman488]

So now i have added two functions

template <class M>
void LinkedList<M>::Passer()
{
	Node<M> *n = head;

	while(n != NULL)
	{
		cout << "Test: " << n->data << endl; //This is just to make sure that n-> data is what I think it is.
		LinkedList<string> line;
		line.deleteIf(n->data);
		n = n->next;

	}

}

and

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;
		}
}

Isn't that what what I was doing with my Passer and deleteIf functions?
The problem I am having is how to implement that with the list of lists. I'm thinking I need to use a function to pass each node from the main list (the node contains a list) to my begone function which then is supposed to do what you have above for the sublist that was passed to it, then when it's done the Passer function is supposed to pass it the next sublist and do the same thing.

I'm just not sure if I am doing it correctly.

[48T7M4Gy]

Why not have a list method that returns a node just like a pop() method?

[Metalman488]

I'm not sure what a pop() method is... I'll try to look it up

EDIT: The pop() functions I see online are void functions and they just delete the head node.

[48T7M4Gy]

You need a method similar to a pop() method but instead of the node being removed from the list it returns a pointer to the node you want to work on. In fact you should be able to design a method that returns a pointer to any node anywhere in the list.

[48T7M4Gy]

This method pops a Node from the front of the list. And the Node is deleted. It returns a bool value to denote success or failure and the node is returned a aItem.

bool popFront(T &aItem)
    {
        if (isEmpty())
        {
            return false;
        }
        else if (head == tail)
        {
            aItem = head->item;
            //delete head;
            head = tail = nullptr;
        }
        else
        {
            aItem = head->item;
            Node<T>* temp = head;
            head = head->next;
            delete temp;
        }
        no_nodes--;
        return true;
    }

I modified my earlier main as follows:

#include <iostream>
#include "single_linked_list.h"

int main()
{
    SINGLE_LL<std::string> s1, s2;
    s1.pushFront("xyz");
    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';
    
    //NOW EXTRACT DATA FROM THE LIST OF LISTS
    SINGLE_LL<std::string> s4;
    s3.popFront(s4);
    std::cout << "s4: " << s4 << '\n';
    
    SINGLE_LL<std::string> s5;
    s3.popFront(s5);
    std::cout << "s5: " << s5 << '\n';
    
    return 0;
}

And the output is:

         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
Node destructor
s4: fun sad book 123 678 1000
s5: xyz abc
Program ended with exit code: 0

s4 and s5 are (reverse) copies of s1 and s2 which is what you would expect in retrieving the two lists. (Forget about efficiency and memory usage, the original is deleted anyway via the pop.)

[48T7M4Gy]

You can now process s4 and s5 nodes as previous discussion.

[Metalman488]

I just don't really see how to apply that to my current code since the lists aren't hardcoded like that.

And I've been messing with my code a bit...
I added
cout << "Current: " << Curr->data << endl;
right before all
delete Curr;
lines so that I would be able to see which nodes it is trying to delete. And it says that it is only deleting the strings containing numbers like it's supposed to! It just won't print the list!
It just prints out
x
Then stops. I added
cout<< "while loop finished" << endl;
to the end of my while loop in my print function to see how many times it tried to print out the nodes and I see that it only runs once to print the 1st node of the main list.
If I remove "123" from the "a aa aaa123" line, then it will run twice. Once for the line containing x and once for "a aa aaa". So it looks to me like the problem is something to do with pointers when I delete a node. It looks like when there is a number, the pointers for the main list somehow get screwed up.

[48T7M4Gy]

@ MetalMan, I think we might be at crossed purposes and we're talking about different aspects of your program.

I suggest you post your latest code and tackle each problem you are having one at a time in a sequence that suits.

There are a number of conventional aspects, particularly methods, about lists and I think you might be going off track. Making a linked list has a few knotty problems but they don't take long to resolve. Similarly if you are using a templated list class, most problems are resolved very easily.

By the way push just puts an object onto the list and pop takes one off. These are 'conventional' linked (and other) list terms and methods.

[Metalman488]

Oh ok. Sorry I keep going from problem to problem. I guess I keep getting past them and forget to update it on here.

As of now, I have the program deleting the nodes I need it to delete and I have it displaying everything after the delete.

It started working after I changed
line.deleteIf(n->data);
to
(n->data).deleteIf();
So I guess the issue was how I was passing each sublist to the deleteIf function.

Now I have that part working, but I have a new, hopefully simple, issue with the output
If I have a file that looks like:

123
abc
456
def
789
ghi

it prints it out like

ghi

def

abc

and I need it to be printed like this:

ghi
def
abc

Here is my print function:

void LinkedList<M>::displayR()
{
	int counter = 0;
		Node<M> *f = tail;
		while(f != NULL)
		{
			counter++;
			output << f-> data << "\n";
			f = f -> prev;
		}
}

And here is the overloaded << operator function:

ostream &operator << (ostream &stream, LinkedList<T> P)
{
	Node<T> *n = P.head;
	while(n != NULL)
	{
		stream << n->data << " ";
		n = n->next;
	}
	return stream;
}

[48T7M4Gy]

I might be wrong but I get the impression that your delete numbers process is not deleting the node properly. It appears there's a 'hidden' endl, '\n' somewhere.

[Metalman488]

I've had a few people look at my delete function and say that they are pretty sure it is deleting the node. I am looking to see if there are any extra endl or '\n' but so far I haven't found any.
I was thinking of adding something to the print function to tell it not to print empty lines, but I haven't had much luck there.
I tried added these

if(f->data != NULL)
      cout << f->data << "\n";

and

if(f->data != '\n')
      cout << f->data << "\n";

and

if(f->data != " ")
      cout << f->data << "\n";

but none of those do any good.
My delete function looks like this:

void LinkedList<M>::deleteN(M& 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;
			}
	}
}

[48T7M4Gy]

This is what I have been comparing yours too and why I was confident about templated lists within lists. Word processing for another day :)

// single_link_node.h
#ifndef SINGLE_LINK_NODE_H
#define SINGLE_LINK_NODE_H

template <typename T> class SINGLE_LL;

template <class T> class Node{
private:
    Node* next;
    T item;
    
public:
    Node(){};
    ~Node(){ std::cout << "Node destructor\n"; }
    Node(T aItem):item(aItem), next(nullptr){};
    
    friend class SINGLE_LL<T>;
};

#endif 

[48T7M4Gy]

// single_linked_list.h
#ifndef SINGLE_LINKED_LIST_H
#define SINGLE_LINKED_LIST_H

#include <iostream>
#include <sstream>

#include "single_link_node.h"

template <class T> class SINGLE_LL{
private:
    Node<T> *head;
    Node<T> *tail;
    size_t no_nodes;
    
public:
    SINGLE_LL():head(nullptr), tail(nullptr), no_nodes(0){};
    
    ~SINGLE_LL()
    {
        Node<T>* temp = head;
        
        while(!isEmpty())
        {
            temp = head;
            head = temp->next;
            temp = nullptr;
            no_nodes--;
        }
        delete temp;
        temp = nullptr;
    }
    
    void pushFront(T aValue)
    {
        Node<T>* new_node = new Node<T>(aValue);
        
        if(isEmpty())
        {
            head = tail = new_node;
        }
        else
        {
            Node<T>* temp = head;
            new_node->next  = temp;
            head = new_node;
        }
        no_nodes++;
    }
    
    void pushBack(T aValue)
    {
        Node<T>* new_node = new Node<T>(aValue);
        
        if(isEmpty())
        {
            head = tail = new_node;
        }
        else
        {
            tail->next  = new_node;
            tail = new_node;
        }
        no_nodes++;
    }
    
    bool popFront(T &aItem)
    {
        if (isEmpty())
        {
            return false;
        }
        else if (head == tail)
        {
            aItem = head->item;
            //delete head;
            head = tail = nullptr;
        }
        else
        {
            aItem = head->item;
            Node<T>* temp = head;
            head = head->next;
            delete temp;
        }
        no_nodes--;
        return true;
    }
    
    bool popBack(T &aItem)
    {
        if (isEmpty())
        {
            return false;
        }
        else if (head == tail)
        {
            aItem = head->item;
            //delete head;
            head = tail = nullptr;
        }
        else
        {
            aItem = head->item;
            
            Node<T>* cursor = head;
            
            for(auto temp = head; temp != tail; temp = temp->next)
            {
                cursor = temp;
            }
            delete cursor->next;
            tail = cursor;
            cursor->next = nullptr;
        }
        no_nodes--;
        return true;
    }
    
    size_t getNoItems()
    {
        return no_nodes;
    }
    
    bool isEmpty() const
    {
        return head == nullptr;
    }
    
    bool delete_item(T &aItem)
    {
        // CASE 1 - IF THE LIST IS EMPTY
        if( head == nullptr)
            return false;
        
        // CASE 2 - IF THE LIST IS NOT EMPTY
        Node<T> *current;
        Node<T> *prev = nullptr;
        
        current = head;
        while(current != nullptr) // TRAVERSE THE LIST
        {
            if(current->item == aItem)
                break;
            else
            {
                prev = current;
                current = current->next;
            }
        }
        
        if(current == head)
        {
            Node<T> *temp = head;
            head = temp->next;
            delete head;
            --no_nodes;
            return true;
        }
        
        if (prev->next != nullptr)// NOT REACHED END OF LIST
        {
            prev->next = current->next;
            delete current;
            current = nullptr;
            no_nodes--;
            return true;
        }
        else
            return false; // REACHED END OF LIST
    }
    
    std::string displayFirst()
    {
        return this->displayNth(0);
    }
    
    std::string displayLast()
    {
        return this->displayNth(no_nodes - 1);
    }
    
    std::string displayNth(size_t n)
    {
        std::stringstream out;
        Node<T> *temp = head;
        
        if( this->isEmpty() or n < 0 or n > no_nodes )
        {
            out << "INVALID REQUEST";
        }
        else
        {
            size_t iter = 0;
            
            while(iter < n)
            {
                temp = temp->next;
                iter++;
            }
            out << n << "-th data item is: " << temp->item;
        }
        return out.str();
    }
    
    friend std::ostream& operator<<(std::ostream &out,
                                    const SINGLE_LL<T> &rhs)
    {
        if( !rhs.isEmpty() )
        {
            Node<T>* temp = rhs.head;
            
            while(temp != nullptr)
            {
                out << temp->item;
                temp = temp->next;
                
                if(temp != nullptr)
                    out << ' ';
            }
        }
        else
            out << "LIST IS EMPTY";
        
        return out;
    }
    
    SINGLE_LL& operator= (const SINGLE_LL& rhs)
    {
        Node<T>* temp;
        
        if(this != &rhs)
        {
            temp = rhs.head;
            
            while(temp != nullptr)
            {
                this->pushFront(temp->item);
                temp = temp->next;
            }
        }
        return *this;
    }
};
#endif 

[48T7M4Gy]

// test_single_linked_list_02.h

//Tests List of lists idea

#include <iostream>
#include "single_linked_list.h"

int main()
{
    SINGLE_LL<int> a, b;
    
    for(int i = 0; i < 5; ++i)
        a.pushFront(i);
    
    for(int i = 10; i < 25; ++i)
        b.pushFront(i);
    
    std::cout << a.getNoItems() << '\n';
    std::cout << b.getNoItems() << '\n';
    
    SINGLE_LL< SINGLE_LL<int> > x;
    x.pushFront(a);
    x.pushFront(b);
    std::cout << x.getNoItems() << '\n';
    std::cout << x.displayFirst() << '\n';
    std::cout << x.displayLast() << '\n';
    
    
    SINGLE_LL<std::string> s1, s2;
    s1.pushFront("xyz");
    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';
    
    //NOW EXTRACT DATA FROM THE LIST OF LISTS
    SINGLE_LL<std::string> s4;
    s3.popFront(s4);
    std::cout << "s4: " << s4 << '\n';
    
    SINGLE_LL<std::string> s5;
    s3.popFront(s5);
    std::cout << "s5: " << s5 << '\n';
    
    // ** TEST DELETE METHOD **
    std::string str;
    while(
          std::cout << "Enter a string to delete from list s2 <q to quit>: "
          && std::cin >> str
          && str != "q"
          )
    {
        std::cout
        << "Before deletion: " << s2 << '\n';
        
        if(s2.delete_item(str))
            std::cout << "After deletion: " << s2 << '\n';
        else
            std::cout << "No change because" << str << " not found\n";
    }

    return 0;
}

5
15
2
0-th data item is: 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
1-th data item is: 4 3 2 1 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
Node destructor
s4: fun sad book 123 678 1000
s5: xyz abc
Enter a string <q to quit>: 1000
Before deletion: 1000 678 123 book sad fun
Node destructor
After deletion: 678 123 book sad fun
Enter a string <q to quit>: 678
Before deletion: 678 123 book sad fun
Node destructor
After deletion: 123 book sad fun
Enter a string <q to quit>: 123
Before deletion: 123 book sad fun
Node destructor
After deletion: book sad fun
Enter a string <q to quit>: fun
Before deletion: book sad fun
Node destructor
After deletion: 
Enter a string <q to quit>: q
Program ended with exit code: 0

[Metalman488]

That is some very informative code that I can use for future reference.

I did finally get my code to do what I wanted it to do, and I figured out why it was printing things out the way it was. It was because each line was a sublist (a linkedlist of strings) and so when the only node inside of it is a number and that node gets deleted, that means that that linked list is empty, but it's still there. All I ended up doing was adding an isEmpty() function and then (if !isEmpty()) to the print statement and now it no longer prints the empty lines. I know i should probably delete the empty lists, but I was told it was ok if I didn't, so I'm not going to.

Thank you so much for all your help and patience!

[48T7M4Gy]

:)