Напиши на C++ реализацию ориентированного взвешенного графа. Учти, что реализация списка смежности следующая: class ListNode //элемент списка
{
public:
int data;
ListNode* prev, * next;
public:
ListNode(int data)
{
this->data = data;
this->prev = this->next = NULL;
}
};
class LinkedList //список
{
public:
ListNode* head;

public:
LinkedList() //1.Инициализация
{
head = NULL;
}

void freeMemory() //2.Освобождение памяти
{
if (head == NULL)
return;

ListNode* current = head;

ListNode* nextNode;

do
{
nextNode = current->next;
delete current;
current = nextNode;
} while (current != head);
head = NULL;
}

void addSorted(int data) //3.Добавление элемента в порядке возрастания
{
ListNode* newNode = new ListNode(data);

if (head == NULL) //если список пустой
{
head = newNode;
newNode->next = newNode->prev = newNode;
}
else if (data < head->data) //если новый элемент меньше головы списка
{

newNode->next = head;
newNode->prev = head->prev;
head->prev->next = newNode;
head->prev = newNode;
head = newNode;
}
else if (data > head->prev->data) //если новый элемент больше хвоста списка
{
newNode->next = head;
newNode->prev = head->prev;
head->prev->next = newNode;
head->prev = newNode;
head->prev = newNode;
}
else //если новый элемент располагается где-то в середине списка
{
ListNode* current = head->next;

while (current != head && current->data < data) //поиск элемента, значение которого больше нового
{
current = current->next;
}

newNode->next = current;
newNode->prev = current->prev;
current->prev->next = newNode;
current->prev = newNode;
}
}

void removeBefore(int data) //4.Удаление элемента перед каждым вхождением заданного
{
if (head == NULL)
{
return;
}


if (head->data == data)
{
if (head->prev->data == head->next->data)
{
head = NULL;
return;
}
else
{
ListNode* nodeToRemove = head->prev;
nodeToRemove->prev->next = head;
head->prev = nodeToRemove->prev;
delete nodeToRemove;
}
}

ListNode* current = head->next;

while (current != head)
{
if (current->data == data)
{
ListNode* nodeToRemove = current->prev;
nodeToRemove->prev->next = current;
current->prev = nodeToRemove->prev;
delete nodeToRemove;
}

current = current->next;
}
}

void remove(int data) //Удаление заданного элемента
{
if (head == NULL)
{
return;
}

if (head->data == data)
{
if (head->prev->data == head->next->data && head->data == head->next->data)
{
head = NULL;
return;
}
else
{
ListNode* nodeToRemove = head;
head->next->prev = head->prev;
head->prev->next = head->next;
head = head->next;
delete nodeToRemove;
}
}

ListNode* current = head->next;

while (current != head)
{
if (current->data == data)
{
ListNode* nodeToRemove = current;
current->next->prev = current->prev;
current->prev->next = current->next;
current = current->next;
delete nodeToRemove;
}
else
current = current->next;
}
}

bool search(int data) //5.Поиск заданного элемента по значению
{
if (head == NULL)
return false;

ListNode* current = head;

do
{
if (current->data == data)
return true;

current = current->next;
} while (current != head);

return false;
}

void print() //6.Печать
{
if (head == NULL)
return;

ListNode* current = head;

do
{
cout << current->data << endl;
current = current->next;
} while (current != head);

cout << endl;
}

LinkedList difference(LinkedList list1, LinkedList list2) //7.Дополнительная операция – разность двух списков
{
if (head != NULL)
{
LinkedList result;

ListNode* current = list1.head;

do
{
if (list2.search(current->data) == false)
result.addSorted(current->data);
current = current->next;
} while (current != list1.head);
return result;
}
}
};