Linked List of linked lists trouble

Question

I am having trouble implementing this with the class I have. So far as a linkedlist of type int or string it works great, but I am not sure how to navigate the list if I initialize it like

linkedlist<linkedlist<int>> nums;

From my program it seems that the head of each secondary list would be an entry in the primary, but my question is how would I navigate it?. For example how would I print all the values of each linkedlist, I am sure I am making this more difficult than it it, but any help would be appreciated.

/* Node Class */
template <typename T>
class Node {
    public:
        T data;
        Node* next;
        Node* previous;
        Node(T data);
        Node();
        T getData();
};

template <typename T>
Node<T>::Node() {
    this->next = NULL;
    this->previous = NULL;
}

template <typename T>
Node<T>::Node(T data) {
    this->data = data;
}

template <typename T>
T Node<T>::getData() {
    return this->data;
}

/* Linked List: */
template <typename T>
class linkedlist {
    private:
        Node<T>* head;
        Node<T>* tail;
        int list_size;
    public:
        linkedlist();
        T getHead();
        T getTail();
        int size();
        void addnodetail(T);
        void addnodehead(T);
        void push(T);
        T pop();
        //T* peek();
        bool isEmpty() const {
                return head == NULL;
            }
        //T* get(int index);
        void printlist();
        void printListBackwards();
        ~linkedlist();
};

template <typename T>
linkedlist<T>::linkedlist() {
    this->head = NULL;
    this->tail = NULL;
    this->list_size = 0;
}

template <typename T>
T linkedlist<T>::getHead() {
    return this->head->data;
}

template <typename T>
T linkedlist<T>::getTail() {
    return this->tail->data;
}

template <class T>
int linkedlist<T>::size() {
    return this->list_size;
}

template <typename T>
void linkedlist<T>::addnodetail(T input) {
    Node<T>* newnode = new Node<T>(input);
    newnode->next = NULL;
    newnode->previous = NULL;

    if (this->head == NULL) {
        this->head = newnode;
        this->tail = this->head;
        this->list_size = this->list_size + 1;
    } else {
        this->tail->next = newnode;
        newnode->previous = this->tail;
        this->tail = newnode;
        this->list_size = this->list_size + 1;
    }
}

template <typename T>
void linkedlist<T>::addnodehead(T input) {
    Node<T>* newnode = new Node<T>(input);
    newnode->next = NULL;
    newnode->previous = NULL;

    if (this->head == NULL) {
        this->head = newnode;
        this->tail = this->head;
        this->list_size = this->list_size + 1;
    } else {
        this->head->previous = newnode;
        newnode->next = this->head;
        this->head = newnode;
        this->list_size = this->list_size + 1;
    }
}

template <typename T>
void linkedlist<T>::push(T input) {
    this->addnodehead(input);
}

template <typename T>
T linkedlist<T>::pop() {
    Node<T>* temp = this->head;
   // T* temp = this->head;
    this->head = this->head->next;
    this->head->previous = NULL;
    this->list_size = this->list_size - 1;
    return temp->data;
}
/*
template <class T>
T* MyList<T>::peek() {
    return this->head;
}


template <class T>
T* MyList<T>::get(int index) {
    if (index == 0) {
        return this->head;
    } else if (index == this->list_size - 1) {
        return this->tail;
    } else if (index < 0 || index >= this->list_size) {
        return NULL;
    }
    if (index < this->list_size / 2) {
        T* temp = this->head;
        int i = 0;
        while (temp) {
            if (i == index) { return temp; }
            i++;
            temp = temp->next;
        }
    } else {
        T* temp = this->tail;
        int i = this->list_size - 1;
        while (temp) {
            if (i == index) { return temp; }
            i--;
            temp = temp->previous;
        }
    }
    return NULL;
}*/

template <typename T>
void linkedlist<T>::printlist() {
    cout << "HEAD:  ";
    Node<T>* temp = this->head;
    while(temp) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "\b\b\b\b  :TAIL" << endl;
}

template <class T>
void linkedlist<T>::printListBackwards() {
    cout << "TAIL:  ";
    Node<T>* temp = this->tail;
    while(temp) {
        cout << temp->data << " -> ";
        temp = temp->previous;
    }
    cout << "\b\b\b\b  :HEAD" << endl;
}

template <typename T>
linkedlist<T>::~linkedlist() {
    for(Node<T>* p;!isEmpty();){
        p = head->next;
        delete head;
        head = p;
    }
}

EDIT with copy constructor

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include <ctype.h>
using namespace std;

using namespace std;



/*struct AdjListNode
{
    int dest;
    struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList
{
    struct AdjListNode *head;  // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
    struct AdjListNode* newNode =
            (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;

    // Create an array of adjacency lists.  Size of array will be V
    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

     // Initialize each adjacency list as empty by making head as NULL
    int i;
    for (i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
    // Add an edge from src to dest.  A new node is added to the adjacency
    // list of src.  The node is added at the begining
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since graph is undirected, add an edge from dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->V; ++v)
    {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl)
        {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}
*/

/* Node Class */
template <typename T>
class Node {
    public:
        T data;
        Node* next;
        Node* previous;
        Node(T data);
        Node();
        T getData();
};

template <typename T>
Node<T>::Node() {
    this->next = NULL;
    this->previous = NULL;
}

template <typename T>
Node<T>::Node(T data) {
    this->data = data;
    this->next = NULL;
}

template <typename T>
T Node<T>::getData() {
    return this->data;
}

/* Linked List: */
template <typename T>
class linkedlist {
    private:
        Node<T>* head;
        Node<T>* tail;
        int list_size;
    public:
        linkedlist();
        linkedlist(linkedlist& object);
        T getHead();
        T getTail();
        int size();
        void addtail(const T& input);
        void addhead(const T& input);
        void push(T);
        T pop();
        //T* peek();
        bool isEmpty() const {
                return head == NULL;
            }
        //T* get(int index);
        void printlist();
        void printListBackwards();
        ~linkedlist();
};

template <typename T>
linkedlist<T>::linkedlist() {
    this->head = NULL;
    this->tail = NULL;
    this->list_size = 0;
}

template <typename T>
linkedlist<T>::linkedlist(linkedlist &object){
    if(object.head == NULL){
        head == NULL;
    }
    else {
        head = new Node<T>(object.head->data);
        Node<T>* temp = head;
        Node<T>* objecthead = object.head;
        Node<T>* current = objecthead;
        while(current->next != NULL){
            temp->next = new Node<T>(current->next->data);
            current = current->next;
            temp = temp->next;
        }
    }
}

template <typename T>
T linkedlist<T>::getHead() {
    return this->head->data;
}

template <typename T>
T linkedlist<T>::getTail() {
    return this->tail->data;
}

template <class T>
int linkedlist<T>::size() {
    return this->list_size;
}

template <typename T>
void linkedlist<T>::addtail(const T& input) {
    Node<T>* newnode = new Node<T>(input);
    newnode->next = NULL;
    newnode->previous = NULL;

    if (this->head == NULL) {
        this->head = newnode;
        this->tail = this->head;
        this->list_size = this->list_size + 1;
    } else {
        this->tail->next = newnode;
        newnode->previous = this->tail;
        this->tail = newnode;
        this->list_size = this->list_size + 1;
    }
}

template <typename T>
void linkedlist<T>::addhead(const T& input) {
    Node<T>* newnode = new Node<T>(input);
    newnode->next = NULL;
    newnode->previous = NULL;

    if (this->head == NULL) {
        this->head = newnode;
        this->tail = this->head;
        this->list_size = this->list_size + 1;
    } else {
        this->head->previous = newnode;
        newnode->next = this->head;
        this->head = newnode;
        this->list_size = this->list_size + 1;
    }
}

template <typename T>
void linkedlist<T>::push(T input) {
    this->addhead(input);
}

template <typename T>
T linkedlist<T>::pop() {
    Node<T>* temp = this->head;
    if(temp != NULL){
    this->head = this->head->next;
    this->head->previous = NULL;
    this->list_size = this->list_size - 1;
    return temp->data;
    }
    else{
        cout << "Error:Empty List!";
            exit (EXIT_FAILURE);
    }
}
/*
template <class T>
T* MyList<T>::peek() {
    return this->head;
}


template <class T>
T* MyList<T>::get(int index) {
    if (index == 0) {
        return this->head;
    } else if (index == this->list_size - 1) {
        return this->tail;
    } else if (index < 0 || index >= this->list_size) {
        return NULL;
    }
    if (index < this->list_size / 2) {
        T* temp = this->head;
        int i = 0;
        while (temp) {
            if (i == index) { return temp; }
            i++;
            temp = temp->next;
        }
    } else {
        T* temp = this->tail;
        int i = this->list_size - 1;
        while (temp) {
            if (i == index) { return temp; }
            i--;
            temp = temp->previous;
        }
    }
    return NULL;
}*/

template <typename T>
void linkedlist<T>::printlist() {
    cout << "STACK" << endl;
    cout << "-------------------" << endl;
    Node<T>* temp = this->head;
    while(temp) {
        cout << "\t" << temp->data << endl;
        temp = temp->next;
    }
    //cout << "\b\b\b\b  :TAIL" << endl;
}

template <class T>
void linkedlist<T>::printListBackwards() {
    cout << "TAIL:  ";
    Node<T>* temp = this->tail;
    while(temp) {
        cout << temp->data << " -> ";
        temp = temp->previous;
    }
    cout << "\b\b\b\b  :HEAD" << endl;
}

template <typename T>
linkedlist<T>::~linkedlist() {
    for(Node<T>* p;!isEmpty();){
        p = head->next;
        delete head;
        head = p;
    }
}


#endif // LINKEDLIST_H

Regarding `Node::Node(T data)`: It is a bad idea with a linked list to leave the next pointer uninitialized. It's a common source of bugs. — user4581301, Mar 25 '18 at 20:58
You appear to have left out a copy constructor and assignment operator for `linkedlist`. This is another common source of bugs. Read [What is The Rule of Three?](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) for more information. — user4581301, Mar 25 '18 at 21:00
If you want a linked list of linked lists why not start with `linkedlist> list;`? — user4581301, Mar 25 '18 at 21:02
In `T linkedlist::pop()` you have a fatal bug if the list is empty. — user4581301, Mar 25 '18 at 21:04
@user4581301 I did, for example i tried out this code and expected to print out only c, but instead i get 400 errors. linkedlist> cities; linkedlist dallas; cities.push(dallas); dallas.push("a"); dallas.push("b"); dallas.push("c"); dallas.printlist(); — zavier, Mar 25 '18 at 21:08
I don't see a problem with that code: https://ideone.com/rXSMSj . By the way, don't trust backspace to work in any meaningful fashion on all platforms. You're better off not printing stuff out than trying to take it back later. — user4581301, Mar 25 '18 at 21:15
Ah. [I do see your problem.](https://ideone.com/ZF0Pd0) You need to overload `operator << ` for a `linkedlist` to make `cout << temp->data << " -> ";` work with a `linkedlist`. See [What are the basic rules and idioms for operator overloading?](https://stackoverflow.com/questions/4421706/what-are-the-basic-rules-and-idioms-for-operator-overloading) to help you write `operator <<`. Printing both lists backwards will be a difficult task. — user4581301, Mar 25 '18 at 21:16
@user4581301 sorry i edited the code, now it shows what is giving me an error linkedlist> cities; linkedlist dallas; cities.push(dallas); dallas.push("a"); dallas.push("b"); dallas.push("c"); cities.printlist(); — zavier, Mar 25 '18 at 21:25
`void linkedlist::push(T input)` takes `input` by value. This makes it impossible to push `dallas` into `cities` and then modify `dallas` so that is meaningful to cities. And remember the warning above about the Rule of Three. — user4581301, Mar 25 '18 at 21:26
can you provide any help on that? I know how to overload operators but I am stuck, my end goal is to be able to print the entire linked list of linked lists, should I create a seperate push for lists? — zavier, Mar 25 '18 at 21:28
When you pass by value, you make a copy. This means the `dallas` inside the `cities` is not the same as the `dallas` you change in `main`. More on that here: [What's the difference between passing by reference vs. passing by value?](https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value) I'm afraid your code has too many mistakes to make for a good Stack Overflow question. This is like fighting a hydra. Strike down one bug and two take its place. — user4581301, Mar 25 '18 at 21:31
@user4581301 I am confused, as a primitive type list it works great, earlier you said it was a logic error, now your saying its because my code is buggy, is it a bug or logic error? i am getting confused — zavier, Mar 25 '18 at 21:39
With a primitive data type or an advanced one that is Rule of Three compliant and has `operator <<` support your code works. It cannot handle anything that cannot be printed with `<<` like `linkedlist` or an object that cannot be safely copied like `linkedlist`. Read the link I dropped earlier about the Rule of Three. It is vital that you understand it if you are going to write non-trivial C++ code, so here it is again: https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three — user4581301, Mar 25 '18 at 22:05
Do not be ashamed that linked list is giving you trouble. That's one of the major educational goals of linked list. It teaches many very important lessons about book-keeping in a very small amount of space and time. Virtually no-one gets it right without pain, suffering and [a good debugger](https://en.wikipedia.org/wiki/Debugger). When you get out into industry you'll find that it is almost never used, but what you learn fighting through it and getting it right makes you a much, much better programmer. — user4581301, Mar 25 '18 at 22:09
@zavier -- Your implementation of a linked list requires that the type being used is safely copyable and assignable. Your `linkedlist` class is neither one, which is why `linkedlist>` or similar will not work. Even a `linkedlist` will fail if given this: `{ linkedlist mylist; mylist.push(10); linkedlist mylist2 = mylist;}`, so claiming it works with simple types is just plain false. — PaulMcKenzie, Mar 25 '18 at 22:30
@user4581301 -- *Virtually no-one gets it right without pain, suffering and a good debugger.* -- You can add to that list "tons of help from an experienced programmer". — PaulMcKenzie, Mar 25 '18 at 22:32
@user4581301 can you elaborate on the operator << support? as in overload them with what function, similar to this? or different?(from a custrom String class) {std::ostream& operator<< (std::ostream& os, const String& s) { if (s.getLength() > 0) { for (int i=0; i < s.getLength(); i++) os << s[i]; } else os << ""; return os; }, and thank you for the help so far! made my copy constructor and addressed if i tried to pop from an empty list, so not my original goal but progress! — zavier, Mar 26 '18 at 16:15
`operator << ` should looks something like `std::ostream& operator<<(std::ostream& out, const linkedlist & list) { list.printlist(); return out; }` Covered in better detail here: https://stackoverflow.com/questions/4421706/what-are-the-basic-rules-and-idioms-for-operator-overloading — user4581301, Mar 26 '18 at 16:43
@user4581301 sorry if i am bugging the hell out of you with all the questions, but you have been a great help and I really appreciate it, thoughts on the code? friend std::istream& operator<< (std::istream& os, const linkedlist& list);// template std::ostream& operator<< (std::ostream& os, const linkedlist& list) { Node* temp = list->head; if (temp != NULL) { while(temp) { os << temp->data; temp = temp->next; } } else os << ""; return os; } — zavier, Mar 26 '18 at 16:58
You don't need the `if` and the `else`. You're basically saying if nothing in list, print nothing. The `while` already does this for you. I recommend putting in some spacing so you can tell nodes apart. right now you can't tell three nodes 1, 2, and 3 from one node 123. What you did in `printlist` was a pretty good idea, so I'd just call `printlist`. It's `public` so you don't even need `friend`ship. — user4581301, Mar 26 '18 at 18:25
Another suggestion: Once you get your linked list up and working, consider asking for a review [over at Code Review](https://codereview.stackexchange.com/help/asking). Note I've linked you to their how to ask page. I strongly recommend reading it before posting there. I also recommend reading through some of the critiques of other linked list implementations because odds are good some of it will apply. Also check any ego writing a linked list has left you at the door because the reviews will get picky. That's what they're for. — user4581301, Mar 26 '18 at 18:56
@user4581301 dont worry ego is at an all time low, cant even make a correct linkedlist of linkedlist with my program, so thats my first mountain to cross — zavier, Mar 26 '18 at 19:34

Linked List of linked lists trouble

0 Answers0