# Thread: Suggestions on how to traverse a linked list of linked lists as if it is a 2D-Vector?

1. ## Suggestions on how to traverse a linked list of linked lists as if it is a 2D-Vector?

Hi All,

I've already had some help on this forum, I'm so glad I found it -- I'm working on an assignment and I'm just struggling with a concept as I'm quite a newcomer with C++.

We are being taught to use doubly-linked lists rather than arrays (therefore the method to traverse between lists to access data is rather inefficient as it involves starting from the beginning each time) - and I'd like some suggestions on how to get started, as I can't think of the right way to do it... maybe to utilise a "row number" for the horizontal lists... I'm not sure.

Anyway, suggestions are very welcome, and I will post my code (it's all in one cpp file). Essentially I need to be able to traverse the list up and down so that I can see all the spaces to the immediate left, top and bottom of a position in one of the rows.

The function "calculate_metrics" alllll the way at the bottom is what I'm up to - I'm so close to getting it all functional!

Code:
```#include <iostream>
#include <fstream>
#include <list>
#include <ctype.h>
#include <cstdlib>

using namespace std;

class row
{
private:

list<char> row_chars;
int row_number;

public:

row(int number)
{
row_number = number;
}

void store_chars(char ch);
void new_row();
void print_row();
bool is_match(char data);
void clear_row();
bool is_char_valid();
bool is_outside_maze(char findData);
bool check_counts(int hash, int s, int f);
int get_row_number();
};

void load_maze(list<row> &maze_rows, row &row_chars, const string &filein);
void print_maze(list<row> &maze_rows);
bool find_char(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows);
int count_char(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows);
bool is_maze_valid(list<row>::iterator &itr, list<row> &maze_rows);
bool is_outside(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows);
int test_maze(list<row> &maze_rows);
void calculate_metrics(list<row> &maze_rows);

int main (int argc, char *argv[])
{
string filein;
list<row> maze_rows;

row row_chars(1);

//Make sure a maze file was provided

if (argc != 2)
{
cout << "Must supply 1 argument to this program\n";
return 0;
}

filein = argv[1];

//Running the tests on the lists...

if(test_maze(maze_rows) == 0)
{
cout << "Unable to load maze " << filein << " \n";
exit(0);
}

print_maze(maze_rows);

//Calculate and print the maze metrics...

calculate_metrics(maze_rows);

return 0;
}

void row::store_chars(char ch)
{
row_chars.push_back(ch);
}

void row::new_row()
{
row_number++;
}

void row::print_row()
{
for(list<char>::iterator list_iter = row_chars.begin();
list_iter != row_chars.end(); list_iter++)
cout << *list_iter;
}

bool row::is_match(char data)
{

//Return false if it cannot find the provided char in the row

for(list<char>::iterator list_iter = row_chars.begin();
list_iter != row_chars.end(); list_iter++)
{
if(*list_iter == data)
return true;
}
return false;
}

void row::clear_row()
{
row_chars.clear();
}

bool row::is_char_valid()
{
//Return true if all the chars match up with one of the specified characters
for(list<char>::iterator list_iter = row_chars.begin();
list_iter != row_chars.end(); list_iter++)
{
if(*list_iter == '#' || *list_iter == 's' || *list_iter == 'f'
|| *list_iter == ' ' || *list_iter == '\n')
continue;
else
return false;
}
return true;
}

bool row::is_outside_maze(char findData)
{
//Return true if the char is outside the maze
int hash_count, s_count, f_count;

hash_count = s_count = f_count = 0;

for(list<char>::iterator list_iter = row_chars.begin();
list_iter != row_chars.end(); list_iter++)
{
if(*list_iter == '#')
hash_count++;
if(*list_iter == 's')
s_count++;
if(*list_iter == 'f')
f_count++;
if(check_counts(hash_count, s_count, f_count))
continue;
else
return true;
}
return false;
}

bool row::check_counts(int hash, int s, int f)
{
if((s > 0 || f > 0) && hash == 0)
return false;
else
return true;
}

int row::get_row_number()
{
return row_number;
}

void load_maze(list<row> &maze_rows, row &row_chars, const string &filein)
{
ifstream fin;
char ch;

//open stream to filein
fin.open(filein.c_str());
if (!fin)
{
cerr << "Unable to load maze " << filein << " \n";
exit(0);
}

while (!fin.eof())
{
fin.get(ch);
row_chars.store_chars(ch);
if(ch == '\n')
{
maze_rows.push_back(row_chars);
row_chars.clear_row();
row_chars.new_row();
}
}

fin.close();
}

void print_maze(list<row> &maze_rows)
{
for(list<row>::iterator list_iter = maze_rows.begin();
list_iter != maze_rows.end(); list_iter++)
list_iter->print_row();
}

bool find_char(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows)
{
// Check if char is found in list

for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++)
{
if (itr->is_match(findData))
return true;
}
return false;
}

int count_char(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows)
{
// Check how many times the char occurs in the row

int data_count = 0;

for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++)
{
if (itr->is_match(findData))
data_count++;
}
return data_count;
}

bool is_maze_valid(list<row>::iterator &itr, list<row> &maze_rows)
{
// Testing if chars in the maze are valid

for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++)
{
if (itr->is_char_valid())
continue;
else
{
cout << "invalid character in maze\n";
return false;
}
}
return true;
}

bool is_outside(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows)
{
//Testing if char is placed inside or outside of the maze

for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++)
{
if (itr->is_outside_maze(findData))
return true;
}
return false;
}

int test_maze(list<row> &maze_rows)
{

list<row>::iterator list_iter;

//Testing to see if 's' is contained in the maze...
if(!find_char('s', list_iter, maze_rows))
{
cout << "Error - no start found in maze";
return(0);
}

//Testing to see if 'f' is contained in the maze...
if(!find_char('f', list_iter, maze_rows))
{
cout << "Error - no finish found in maze";
return(0);
}

//Testing to see if maze contains valid characters...
if(!is_maze_valid(list_iter, maze_rows))
{
return(0);
}

//Testing to see if there is only one 's' and 'f'
// contained in the maze...
if(count_char('s', list_iter, maze_rows) != 1)
{
cout << "Error - multiple start found in maze\n";
return(0);
}
if (count_char('f', list_iter, maze_rows) != 1)
{
cout << "Error - multiple finish found in maze\n";
return(0);
}

//Testing to see if 's' or 'f' is declared
// outside of the maze...
if(is_outside('s', list_iter, maze_rows))
{
cout << "Error - start declared outside of maze\n";
return(0);
}
if(is_outside('f', list_iter, maze_rows))
{
cout << "Error - finish declared outside of maze\n";
return(0);
}
return(1);
}

void calculate_metrics(list<row> &maze_rows)
{
/*Calculate the total number of branches in the maze*/
/*Calculate the total number of dead ends in the maze*/

cout << "\nNumber of branches in maze is " << branches << "\n";
cout << "Number of dead-ends in maze is " << dead_ends << "\n";
}```

2. Essentially I need to be able to traverse the list up and down so that I can see all the spaces to the immediate left, top and bottom of a position in one of the rows.
A very interesting problem.

My ideas:
-Store your column in a variable (the only way you'll know if you're on the space directly above another is if you count how many spaces you were over)
-Make the doubly-linked list into a 4-link list (ie, store pointers to the left, right, top and bottom in each node) (this means ditching the STL but if you have to access the immediate top, left, right, and bottom spaces a lot it will speed things up)

3. Sounds to me like you are using the wrong container for the job at hand.

4. Originally Posted by Bubba
Sounds to me like you are using the wrong container for the job at hand.
Yeah. The STL is nifty but you should not be constrained by it because you don't know how to write a custom data structure. Try a graph or "4-link" list as bernt says.

5. Thanks for the suggestions guys - I ended up doing it quite a slow way, without needing to define my own list. To be honest I'm simply not up to that level yet, I've had a bit of Java experience but I only started properly trying to learn C++ yesterday...

It did end up working though, and passed all the functionality tests in the submission program for the assignment. No doubt the next assignment will be a lot harder and probably will require me to learn how to correctly define lists an such :P