Need help linked list

[Cantstrikeout]

I need to make this unordered list an ordered list and I don't know where to start.




#pragma once
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::ostream;

template <class T>
class Node
{
public:
T data;
Node<T>* next;
Node()
{
next = nullptr;
}

Node(T data, Node <T>* next = nullptr)
{
this->data = data;
this->next = next;
}
};

template<class T>
class LinkedList
{
private:
Node<T>* head;

public:
LinkedList() //Constructor that initializes the class object
{
head = nullptr;
}

~LinkedList() //Deallocates any memory allocated in class methods. Called when "delete" is used on a class object.
{
ClearList();
}

void ClearList()
{
Node<T> *tmp = head;
Node<T> *tmp2 = nullptr;

while (tmp != nullptr)
{
tmp2 = tmp;
tmp = tmp->next;
delete tmp2;
}

head = nullptr;
}

void Insert(T data)
{
Node<T> *temp = new Node<T>(data); //Created a new node in dynamic memory

//If the list is empty
if (head == nullptr)
{
//Add it to the beginning and end of the list
head = temp;
}
else
{
//Traverse to the end of the list
Node<T>* tempT = head;

while (tempT->next != nullptr)
{
tempT = tempT->next;
}

//Attach the new node to the end of the
//list
tempT->next = temp;
}
}

void Remove(T data)
{
Node<T> *tmp = head;
Node<T> *tmp2 = nullptr;

while (tmp != nullptr && tmp->data != data)
{
tmp2 = tmp;
tmp = tmp->next;
}

if (tmp == nullptr)
return;
else
{
if (tmp == head)
{
head = head->next;
delete tmp;
}
else
{
//delete the node
tmp2->next = tmp->next;
delete tmp;
}
}

}

friend ostream& operator<<(ostream &os, const LinkedList<T> &list)
{
Node<T> *tmp = list.head;

while (tmp != nullptr)
{
os << tmp->data << endl;
tmp = tmp->next;
}

return os;
}
};



I have this as pseudocode.

method Insert(value <int> data)
{
if (head == NULL)
{
head = new Node(data, NULL)
}
else
{
Node ptr temp = head
Node ptr tempT = NULL
while(temp != NULL and temp.data < data):
{
tempT = temp
temp = temp.next
}
if (temp == NULL)
{
tempT.next = new Node(data, NULL)
}
else if (temp == head)
{
tempT = new Node(data, head)
head = tempT
}
else
{
tempT.next = new Node(data, temp)
}
}
}

[doug4]

Do you mean you want to order the nodes as you insert them, or sort them after you have created the list?

Either way, you need to have an ordering function (like "less-than") which can tell you which element comes first when ordered.

In the first case, when you are inserting elements, you traverse the list looking for the first element in the list that comes after new element. Simply insert the new element into the list at that point. Pay careful attention to corner cases: empty list, before first element, after last element.

In the second case, after you create the list, do a bubble sort on the elements. If two elements are out of order, swap them.

[keskiverto]

do a bubble sort on the elements

There are many sorting algorithms that suite to the job.

The trick, or decision, in sorting a linked list is how to swap elements.

If you have elements in an array, the swap requires a copy/move of elements. That can be expensive on "heavy" element types.

When you have a linked list, you can still do that but you have also option to swap by updating the links. That is more complex to write, but independent of the data element's type.

[doug4]

@keskiverto,

Thanks for pointing that out. For some reason I made the assumption that the OP knew how to manipulate items (specifically swap them) in a linked list. It is highly likely that this was a bad assumption.

You're right--learning how to swap elements in the list is just as valuable as learning how to sort a collection.

@OP,

Swapping elements in a linked list is actually pretty easy, but you have to pay attention to the details. Make sure you keep track what each "next" pointer is pointing to (including the nodes preceding the ones you are swapping), and make sure you end up with the pointers in a sane state. Be aware of corner cases like swapping the first and/or last node in a list.

[dhayden]

Why do you insert at the tail of the list instead of at the head, which is far more efficient:

void Insert(T data)
{
    Node<T> *newNode = new Node<T>(data, head);
    head = newNode;
}

Keep in mind that T could be a big, complex class. To avoid the expense of making copies of T, you should pass it by const reference wherever you need a T.