Напиши на 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;
        }
    }
};