I'm working on a lab assignment. I've been given a ton of code (5 files worth) that does various things with a linked list. I'm supposed to add a function to split this list into two separate lists by testing whether or not each number is <,=, or > a certain element. I am completely lost and don't understand linked lists at all. I'm also a bit lost on pointers since it's been almost a year since I've looked at programming, but I could probably figure that out if I could just get this linked list thing down.
Here's my SplitLists function so far:
void UnsortedType::SplitLists ()
{
// Pointers for each new list
NodeType* list1Ptr;
NodeType* list2Ptr;
// Define lists and make them empty here somehow.
ResetList ();
ItemType next = GetNextItem ();
temp.ComparedTo (item);
while (GetNextItem() != NULL) // Traverse through the original list
{
if (LESS || EQUAL)
{
list1Ptr=listData;
// Use PutItem
}
else
{
list2Ptr=listData;
}
}
}
In other places in the code, I have GetNextItem, ComparedTo, PutItem, and ResetList that were already given to me. I've spent quite a while searching the internet for something that would help me understand, but I am still really lost. Thanks so much.
Linked lists are pretty simple. In the most basic form, you have a "head" pointer that points to the first node in the list. Each node has a pointer to the next node, the last node points to null generally. If you want to split a linked lists, you'll need do something like:
Iterate through linked list until you're at last node you want before split.
Store this address in temporary variable, end.
Create new LinkedList instance.
Set head of new linked list to end.next. //Starts new linked list
Set end.next to null. //Cuts off old linked at end.
Now you have two linked lists without having to copy any data. Make sure you don't mess up the order of anything, or else you could lose a lot of data.