Node.cpp

#include "Node.h"
#include <stdlib.h>
#include <iostream>
using namespace std;
List::List()
{
	head = new Node;
	tail = new Node(-1, head, 0);
	head->next = tail;
    head->prev = nullptr;
 }
List::List(int n)
{
	head = new Node;
	tail = new Node(-1, head, 0);
	head->next = tail;
    head->prev = nullptr;
	for (int i = 0; i <= n; i++)
	{
		int x = rand() % 100;
		AddToTail(x);
	}
}
List::List(int* a, int n)
{
	head = new  Node;
	tail = new  Node(-1, head, 0);
	head->next = tail;
	for (int i = 0; i < n; i++)
	{
		AddToTail(a[i]);
	}
}
List::~List()
{
	Clear();
	delete head;
	delete tail;
}
List::List(List& s)
{
	head = new  Node;
	tail = new  Node(-1, head, 0);
	head->next = tail;
    head->prev = nullptr;
	Node* q = s.head->next;
	while (q != s.tail)
	{
		AddToTail(q->key);
		q = q->next;
	}
}
List& List::operator= (List& s)
{
	if (this != &s)
	{
		Clear();
		Node* q = s.head->next;
		while (q != s.tail) 
		{
			AddToTail(q->key); 
			q = q->next;
		}
	}
	return *this;
}

// Ìåòîä î÷èñòêè ñïèñêà
void List::Clear() {
    while (!Empty()) {
        DelHead(); // Óäàëÿåì ýëåìåíòû ñ ãîëîâû
    }
}

// Ïðîâåðêà ïóñòîòû ñïèñêà
bool List::Empty() {
    return head == nullptr; // Åñëè ãîëîâà ðàâíà nullptr, ñïèñîê ïóñò
}

// Äîáàâëåíèå óçëà â õâîñò
void List::AddToTail(int x) {
    Node* newNode = new Node(x, tail->prev, tail); // Ñîçäàåì íîâûé óçåë
    if (tail->prev != nullptr) { // Ïðîâåðÿåì, ÷òî ñïèñîê íå ïóñò
        tail->prev->next = newNode; // Ñâÿçûâàåì ïðåäûäóùèé óçåë ñ íîâûì
    }
    tail->prev = newNode; // Îáíîâëÿåì prev äëÿ tail
    newNode->next = tail; // Îáíîâëÿåì next äëÿ íîâîãî óçëà
}

// Äîáàâëåíèå óçëà â ãîëîâó
void List::AddToHead(int x) {
    Node* newNode = new Node(x, nullptr, head); // Ñîçäàåì íîâûé óçåë
    if (head) {
        head->prev = newNode; // Ñâÿçûâàåì íîâûé óçåë ñ ãîëîâîé
    }
    else {
        tail = newNode; // Åñëè ñïèñîê ïóñò, íîâûé óçåë ñòàíîâèòñÿ õâîñòîì
    }
    head = newNode; // Îáíîâëÿåì ãîëîâó
}
void List::AddAfter(Node* p, int x) {
    if (p == nullptr || p == tail) return; // Åñëè óçåë ïóñò èëè ýòî tail, íè÷åãî íå äåëàåì
    Node* newNode = new Node(x, p, p->next); // Ñîçäàåì íîâûé óçåë
    p->next->prev = newNode; // Ñâÿçûâàåì ñëåäóþùèé óçåë ñ íîâûì
    p->next = newNode; // Îáíîâëÿåì next äëÿ óçëà p
}

void List::AddToTail(const List& other) {
    Node* current = other.head->next; // Íà÷èíàåì ñ ïåðâîãî óçëà äðóãîãî ñïèñêà
    while (current != other.tail) {
        AddToTail(current->key); // Äîáàâëÿåì êàæäûé ýëåìåíò â õâîñò
        current = current->next;
    }
}

void List::AddToHead(const List& other) {
    Node* current = other.tail->prev; // Íà÷èíàåì ñ ïîñëåäíåãî óçëà äðóãîãî ñïèñêà
    while (current != other.head) {
        AddToHead(current->key); // Äîáàâëÿåì êàæäûé ýëåìåíò â ãîëîâó
        current = current->prev;
    }
}

// Óäàëåíèå óçëà ïî óêàçàòåëþ
void List::Del(Node* p) {
    if (p == nullptr) return; // Åñëè óçåë ïóñò, íè÷åãî íå äåëàåì
    if (p->prev) {
        p->prev->next = p->next; // Ñâÿçûâàåì ïðåäûäóùèé óçåë ñ ñëåäóþùèì
    }
    else {
        head = p->next; // Åñëè óäàëÿåì ãîëîâó, îáíîâëÿåì ãîëîâó
    }
    if (p->next) {
        p->next->prev = p->prev; // Ñâÿçûâàåì ñëåäóþùèé óçåë ñ ïðåäûäóùèì
    }
    else {
        tail = p->prev; // Åñëè óäàëÿåì õâîñò, îáíîâëÿåì õâîñò
    }
    delete p; // Óäàëÿåì óçåë
}

// Óäàëåíèå ýëåìåíòà ñ õâîñòà
void List::DelTail() {
    if (tail) {
        Del(tail); // Óäàëÿåì õâîñò
    }
}

// Óäàëåíèå ýëåìåíòà ñ ãîëîâû
void List::DelHead() {
    if (head) {
        Del(head); // Óäàëÿåì ãîëîâó
    }
}

// Ïîèñê óçëà ïî êëþ÷ó
Node* List::FindKey(int key) {
    Node* current = head;
    while (current != nullptr) {
        if (current->Key() == key) {
            return current; // Âîçâðàùàåì óçåë, åñëè íàéäåí
        }
        current = current->next;
    }
    return nullptr; // Åñëè íå íàéäåí, âîçâðàùàåì nullptr
}

// Ïîèñê óçëà ïî ïîçèöèè
Node* List::FindPos(int pos) {
    Node* current = head;
    int index = 0;
    while (current != nullptr) {
        if (index == pos) {
            return current; // Âîçâðàùàåì óçåë ïî ïîçèöèè
        }
        current = current->next;
        index++;
    }
    return nullptr; // Åñëè ïîçèöèÿ âíå äèàïàçîíà, âîçâðàùàåì nullptr
}

// Íàõîæäåíèå ìàêñèìàëüíîãî ýëåìåíòà ñïèñêà
Node* List::Max() {
    if (Empty()) return nullptr; // Åñëè ñïèñîê ïóñò, âîçâðàùàåì nullptr
    Node* current = head;
    Node* maxNode = head;
    while (current != nullptr) {
        if (current->Key() > maxNode->Key()) {
            maxNode = current; // Îáíîâëÿåì ìàêñèìàëüíûé óçåë
        }
        current = current->next;
    }
    return maxNode; // Âîçâðàùàåì óçåë ñ ìàêñèìàëüíûì çíà÷åíèåì
}

// Íàõîæäåíèå ìèíèìàëüíîãî ýëåìåíòà ñïèñêà
Node* List::Min() {
    if (Empty()) return nullptr; // Åñëè ñïèñîê ïóñò, âîçâðàùàåì nullptr
    Node* current = head;
    Node* minNode = head;
    while (current != nullptr) {
        if (current->Key() < minNode->Key()) {
            minNode = current; // Îáíîâëÿåì ìèíèìàëüíûé óçåë
        }
        current = current->next;
    }
    return minNode; // Âîçâðàùàåì óçåë ñ ìèíèìàëüíûì çíà÷åíèåì
}
bool List::operator==(const List& other)
{
    Node* current1 = head->next;
    Node* current2 = other.head->next;

    while (current1 != tail && current2 != other.tail) {
        if (current1->key != current2->key) {
            return false; // Åñëè êëþ÷è íå ðàâíû, ñïèñêè íå ðàâíû
        }
        current1 = current1->next;
        current2 = current2->next;
    }
    return current1 == tail && current2 == other.tail; // Ïðîâåðÿåì, ÷òî îáà ñïèñêà äîñòèãëè êîíöà
}

// Ââîä ñïèñêà èç n ýëåìåíòîâ
void List::Scan(int n) {
    Clear(); // Î÷èùàåì òåêóùèé ñïèñîê
    for (int i = 0; i < n; ++i) {
        int value;
        std::cout << "Ââåäèòå ýëåìåíò " << i + 1 << ": ";
        std::cin >> value; // Ââîä çíà÷åíèé
        AddToTail(value); // Äîáàâëÿåì ýëåìåíò â õâîñò
    }
}

// Ïå÷àòü ñïèñêà
void List::Print() {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->Key() << " "; // Âûâîä êëþ÷à óçëà
        current = current->next; // Ïåðåõîä ê ñëåäóþùåìó óçëó
    }
    std::cout << std::endl; // Ïåðåõîä íà íîâóþ ñòðîêó
}
 //Îïåðàòîð âûâîäà
std::ostream& operator<<(std::ostream& r, List& X) {
    X.Print(); // Èñïîëüçóåì ìåòîä Print äëÿ âûâîäà
    return r;
}

// Îïåðàòîð ââîäà
std::istream& operator>>(std::istream& r, List& X) {
    int n;
    std::cout << "Ââåäèòå êîëè÷åñòâî ýëåìåíòîâ: ";
    r >> n; // Ââîä êîëè÷åñòâà ýëåìåíòîâ
    X.Scan(n); // Èñïîëüçóåì ìåòîä Scan äëÿ ââîäà
    return r;
}