Double linked cyclical list c++

Question

I want to create double linked cyclical list for the little game I am making. I want it to be a list because of the speed it offers when it comes to adding and deleting new elements. If i wanted to use a dynamical table, any kind of adding/deleting operation would require me to rewrite entire table and that would slow down the program severely (atleast from my understanding). The only problem with that solution is the fact, that I do not fully understand how to do such a list ;)

struct parts{
    char name;
    parts *next, *prev;
    parts *connected;
};

void add_part(struct parts **head, struct parts **tail, char name) 
{
    struct parts *a;
    a = (struct parts*)malloc(sizeof(struct parts));
    a->name = name;
    if ((*head) == NULL && (*tail) == NULL)
    {
        *head = a;
        *tail = a;
        a->next = NULL;
        a->prev = NULL;
    }
    else
    {
        a->next = *head;
        a->prev = NULL;
    }
}

void display(parts *head) {
    parts *temp = head;
    while (temp != NULL){
        cout << temp->name << endl;
        temp = temp->next;
    }
}

int main ()
{
    char names[] = "ABCDEFGHIJKLMNOPRSTUWXYZ";
    segmenty *head = NULL;
    segmenty *tail = NULL;
    int count_parts;
    cin >>count_parts;

    for (int i=0; i < count_parts && i<24; i++){
        add_part(&head, &tail, names[i]);
    }
    display(head);
    return 0;
}

What I want user to be able to do is to type in the amount of elements he wants and then I want to name each element with a letter from the alphabet and put them in my list so that every element is connected to elements before and after it and tail is connected to head(I want the list to be cyclical). Unfortunately my pointer skills are kind of lacking... *connected is a pointer i want to use for elements that are currently on the ground (only one element can touch the ground at once) for uses such as deleting or adding the new element e.g. if the element hits the trap i want to delete that one specific element, not any other one.

Answer 1

Unless you have to practice and demonstrate pointer skills, review the std::list container described here: std::list - cppreference.com. Fundamentally, the struct parts and all pointer manipulation would be gone. The std::list container can be declared as storing a single char per element. It also does all of the pointer manipulation and housekeeping for you. The connected pointer is discussed following the std::list code sample.

If you find after testing with storing a single char that a string is better, then modify the typedef line declaring the std::list to contain a std::string instead.

Reference to the remove functions: std::list::remove, remove_if.

Reference to the insertion functions: std::list::insert. Insertion is not demonstrated here, but there are eight different overloaded versions.

Four methods with constant time complexity:
1. Add to the front or end of the list, use: std::list::push_front and std::list::push_back.
2. Remove a single element from the front or back: std::list::pop_front and std::list::pop_back.

An example declaration and simple operations follow. The std::list is shown below for clarity, but the std:: is not necessary to compile and build (e.g. using namespace std; is present):

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

//
// Other headers as needed, then a sample main...
//
main (int argc, char * argv[])
{
    const int ciNamesMax = 26;
    char names[ciNamesMax] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 
                              'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 
                              'U', 'V', 'W', 'X', 'Y', 'Z' };


    typedef std::list <char> tdCharNames;
    tdCharNames theNames(names, names + ciNamesMax);


    //
    // Print the list contents with zero modifications to the elements
    //
    cout << "The doubly linked list of chars contains the following values.";
    cout << endl;
    int j = 1;
    for (tdCharNames::iterator i = theNames.begin(); i != theNames.end(); i++) 
    {
       cout << "Element " << j << " is: " << (*i) << endl;
       j++;
    }

    //
    // Use the built-in remove function in two different ways to demonstrate
    // ease of removing an element or elements.
    //
    theNames.remove('B');

    //
    // Note that the C++11 lambda function is used as the predicate to 
    // remove the 'G' and 'P' elements.
    //
    theNames.remove_if( [](char c) { return (c == 'G' || c == 'P'); } );
    j = 1;
    for (tdCharNames::iterator i = theNames.begin(); i != theNames.end(); i++) 
    {
       cout << "Element " << j << " is: " << (*i) << endl;
       j++;
    }

} // end main

The connected pointer inside the struct parts above would then become a declared single char variable, whose value is obtained however necessary (e.g. input from the user and cin). Then the connected variable would be passed to the std::list::remove function. For example, here is a code snippet:

char connected;
cout << "Enter the ground location (A-Z): ";
cin >> connected;

//
// Other logic, user messages, error checking, and so on.
// Then, call the std::list::remove method as desired.
//
theNames.remove(connected);

Example of switching to storing a std::string:

const int ciNamesMax = 26;
std::string names[ciNamesMax] = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", 
                                 "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", 
                                 "U", "V", "W", "X", "Y", "Z" };


//
// May want to modify the typedef name to better indicate std::string.
// Leaving the typedef as before to demonstrate the simplicity of changing
// the element type being stored.  Keep in mind that the lambda and other 
// logic looking for a char may be affected.  It is up to the reader to test
// and adjust the implementation accordingly.
//
typedef std::list <std::string> tdCharNames;
tdCharNames theNames(names, names + ciNamesMax);