Array of Linked Lists

[SSDEEZ]

I've made a class defining a list. I know STL has a list function but I went ahead and coded the whole thing.

I want to make an array of linked lists and be able to insert nodes at a specific position in the array.

I also have an insert function that can determine if the list is empty and insert after the head, traverse the whole list and insert at the end or if a node is already in the list, unlink it, relink the previous and the next together, and move it to the end.

so far I have:

list l;

list array[4];

int k = 0;
cout << "input a number 0-4" << endl;
cin >> k;

for(int i = 0; i < 4; ++i){

    if(array[i] == k){
         
          //insert node after the head node in position k
          // this is what i am unsure about how do you map this?

     } 

}

[deleted account xyzzy]

You likely would be better off recreating a very rudimentary linked list class setup, there is a lot of LL mechanics you need to consider:

// C++ has MUCH better alternatives than this.  Why reinvent a flat wheel?

// this example simply illustrates what is needed to implement a linked list

// this really is not a complete linked list.

#include <iostream>

enum { nIsSmaller, nIsLarger, nIsSame };

// Data class to put into the linked list
// Any class in this linked list must support two methods:
// Show (displays the value) and Compare (returns relative position)
class Data
{
public:
    Data(long val) : myValue(val) { }
   ~Data() { }

public:
   long Compare(const Data&);

public:
   void Show() { std::cout << myValue << std::endl; }

private:
   long myValue;
};

// forward declarations
class Node;
class HeadNode;
class TailNode;
class InternalNode;

// ADT representing the node object in the list
// every derived class must override Insert and Show
class Node
{
public:
   Node() { }
   virtual ~Node() { }

public:
   virtual Node* Insert(Data* theData) = 0;

public:
   virtual void Show() = 0;
};

// This is the node which holds the actual object
// In this case the object is of type Data
// We'll see how to make this more general when
// we cover templates
class InternalNode : public Node
{
public:
   // all the constructor does is to initialize
   InternalNode(Data* theData, Node* next) : myData(theData), myNext(next) { }
   ~InternalNode() { delete myNext; delete myData; }

public:
   virtual Node* Insert(Data* theData);

public:
   virtual void Show()
   {
      myData->Show();   // delegate!
      myNext->Show();
   }

private:
   Data* myData; // the data itself
   Node* myNext; // points to next node in the linked list
};

// Tail node is just a sentinel
class TailNode : public Node
{
public:
   TailNode() { }
   ~TailNode() { }

public:
   virtual Node* Insert(Data* theData);
   virtual void Show() { }
};

// Head node has no data, it just points
// to the very beginning of the list
class HeadNode : public Node
{
public:
   HeadNode();
   ~HeadNode() { delete myNext; }

public:
   virtual Node* Insert(Data* theData);

public:
   virtual void Show() { myNext->Show(); }

private:
   Node* myNext;
};

// I get all the credit and do none of the work
class LinkedList
{
public:
   LinkedList();
   ~LinkedList() { delete myHead; }

public:
   void Insert(Data* theData);

public:
   void ShowAll() { myHead->Show(); }

private:
   HeadNode* myHead;
};

// test driver program
int main()
{
   Data* pData;
   int val;
   LinkedList ll;

   // ask the user to produce some values
   // put them in the list
   for (;;)
   {
      std::cout << "What value? (0 to stop): ";
      std::cin >> val;

      if (!val)
      {
         std::cout << "\n";
         break;
      }

      pData = new Data(val);
      ll.Insert(pData);
   }

   // now walk the list and show the data
   ll.ShowAll();

   // ll falls out of scope and is destroyed!
}

// Compare is used to decide where in the list
// a particular object belongs.
long Data::Compare(const Data& theOtherData)
{
   if (myValue < theOtherData.myValue)
   {
      return nIsSmaller;
   }

   if (myValue > theOtherData.myValue)
   {
      return nIsLarger;
   }
   else
   {
      return nIsSame;
   }
}

// the meat of the list
// when you put a new object into the list
// it is passed to the node which figures out
// where it goes and inserts it into the list
Node* InternalNode::Insert(Data* theData)
{
   // is the new guy bigger or smaller than me?
   int result = myData->Compare(*theData);

   switch (result)
   {
   default:
      // by convention if it is the same as me it comes first
   case nIsSame:   // fall through
   case nIsLarger: // new data comes before me
   {
      InternalNode* dataNode = new InternalNode(theData, this);
      return dataNode;
   }

   // it is bigger than I am so pass it on to the next
   // node and let HIM handle it.
   case nIsSmaller:
   {
      myNext = myNext->Insert(theData);
      return this;
   }
   }
}

// if data comes to me, it must be inserted before me
// as I am the tail and NOTHING comes after me
Node* TailNode::Insert(Data* theData)
{
   InternalNode* dataNode = new InternalNode(theData, this);
   return dataNode;
}

// As soon as the head is created
// it creates the tail
HeadNode::HeadNode()
{
   myNext = new TailNode;
}

// Nothing comes before the head so just
// pass the data on to the next node
Node* HeadNode::Insert(Data* theData)
{
   myNext = myNext->Insert(theData);
   return this;
}

// At birth, I create the head node
// It creates the tail node
// So an empty list points to the head which
// points to the tail and has nothing between
LinkedList::LinkedList()
{
   myHead = new HeadNode;
}

// Delegate, delegate, delegate
void LinkedList::Insert(Data* pData)
{
   myHead->Insert(pData);
}

What value? (0 to stop): 5
What value? (0 to stop): 12
What value? (0 to stop): -14
What value? (0 to stop): 124
What value? (0 to stop): -127
What value? (0 to stop): 19
What value? (0 to stop): 0

-127
-14
5
12
19
124

FYI, this is more of a std::set style bit of code than a linked list, the data is sorted on entry.

[SSDEEZ]

I reinvent the flat wheel because I've been forced to...

I can't just abandon the array of linked lists lol

[deleted account xyzzy]

The setup I showed IS using an array. A dynamic array based on pointers used to link data elements, so it can expand at run-time depending on the number of data inputs. The memory layout is not contiguous.

Using a regular compile-time fixed size array will have serious limitations on memory usage and design for what you want to do. Insertion other than at the end will be especially problematical since you will have to reorganize the elements on the fly to shove the new element into place in the array. Deletion will have similar problems.

A regular array from the standpoint of memory layout could be seen as a crude form of linked list, you can transverse the array forwards and backwards using pointer mathematics. Insertion/deletion breaks a regular array, something a linked list is designed for, big time.

[seeplus]

@George, doesn't the destructor for LinkedList have to iterate the list to delete the memory for each node? What about copy constructor/operator= (and move constructor/operator=)? const and noexcept member functions?

Just an observation, but this seems to be over-engineered...

[seeplus]

@SSDEEZ

L2 defines l as type list (presumably your list class - note don't use the same name as used by std::. It can easily become confusing. User-defined types (classes etc) often start with a capital letter) )

L4 defines an array called array of 4 elements each of type list.

Ok so far so good.

Then enter a number 0 - 4. Do you mean 0 - 3 (element index into array)?

You now know which list of the array you're going to be using. What are you going to do with this list - insert, find, delete??

What do you want to do with the array of lists? Why do you want an array of lists?

More info is required on this for further guidance.

[againtry]

Putting that into 'guess' code and hard coding it:

#include "list.h"

int main()
{
    const int NO_LISTS{4}; // or create dynamically

    list array_of_lists[NO_LISTS];

    int list_no{2}; // for arguments sake, or prompt + cin
    int value_to_be_listed{78}; // // for arguments sake, or prompt + cin

    array_of_lists[list_no].insert(value);
    
    return 0;
}

[deleted account xyzzy]

The code looks to be "over-engineered" -- as well as missing several ctors -- mostly because it is rather old, pre-C++11, barely C++98, as well as "found on the internet" code. It isn't code I created.

It certainly isn't code I'd consider even close to being "production" worthy. It is simply a rather crude attempt at demonstrating, badly, how at a minimum a linked list container MIGHT be constructed.

If the designer had half their brain removed.