Using nodes and Linked List

[CS Student]

favorite




Okay, so I am trying to create a "linked list" and I'm running into trouble and I'm a little confused on how I am supposed to implement "nodes".

A collection of nodes that point to each other is considered a linked list, right? I'm trying to create a function that accepts an array along with it's size, and i'm supposed to take each element, and be able to sort it as I put it into a list, then put it back into the array ordered. How am I even supposed to do this? I know that a node holds a certain element, and a pointer to the next node. Is there already a structure in the STL, or do I have to make it from scratch?

Can anybody help me get started? (aside or addition to what I've already got). I also don't know how to go from elements of an array to elements of a node and how to sort them in order. I'm working with ints right now and im hoping to move to templates. Help would be much appreciated! Thanks :)

EDIT) This is a header file by the way...

using namespace std;

/***********************************************
 * NODE
 ***********************************************/
struct Node
{
   int data;
   Node * pNext;
};

/***********************************************
 * INSERTION SORT
 * Sort the items in the array
 **********************************************/
//template <class T>
void sortInsertion(int array[], int num)
{
   // Make sure we can list the elements unsorted
   cout << "Testing sortInsertion()...\n\n";
   cout << "Unsorted:\n";
   for (int i = 0; i < num; i++)
      cout << "num "<< i + 1 << ": " << array[i] << endl;
   cout << endl;
   cout << "Sorted:\n";

   // Okay, make the head of the list...
   Node *pHead;

   // Loop through each element and insert it into the list, depending on order
   for (int i = 0; i < num; i++);

   // Loop through each node, and transfer each element into the array.
   for(const Node *p = pHead; p; p = p -> pNext)
   {
      int i = 0;
      array[i] = p -> data;
      i++;
   }
}

[coder777]

There's already a list as standard container:

http://www.cplusplus.com/reference/list/list/?kw=list

and a sort function:

http://www.cplusplus.com/reference/algorithm/sort/?kw=sort

but I guess you're supposed to do it yourself.

To insert an element use the loop on line 35. Iterate as long as p->data < array[i] otherwise insert the node

[CS Student]

Oh ok thanks! That really helps!

[CS Student]

Would I loop through each element in the array, then compare it? ex)

for (int i = 0; i < num; i++)
{
   if (array[i] > p -> data)
      insert data
}