#include <iostream>

using namespace std;

typedef unsigned int uint;

==== Односвязный список (однонаправленный список)

template <class T>

struct ListItem

{

T val;

ListItem* next;

};

template <class T>

class List

{

private:

ListItem<T>* _head;

uint _count;

public:

List();

List(const List<T>& obj);

void clear();

~List() { clear(); };

List& operator=(const List<T>& obj);

T& operator[](uint index);

uint getCount() { return _count; }

bool isEmpty() { return _count == 0; }

void insert(uint index, const T& item);

void addHead(const T& item);

void addTail(const T& item);

void remove(uint index);

void print();

};

template<class T>

List<T>::List(): _head{nullptr}, _count{} {}

template<class T>

List<T>::List(const List<T>& obj)

{

if (!obj._count)

_head = nullptr;

else

{

ListItem<T>* prev;

ListItem<T>* temp;

ListItem<T>* src = obj._head;

for (uint i = 0; i < obj._count; i++)

{

temp = new ListItem<T>;

temp->val = src->val;

temp->next = nullptr;

if (!i)

_head = temp;

else

prev->next = temp;

prev = temp;

src = src->next;

}

}

_count = obj._count;

}

template<class T>

void List <T>::clear()

{

if (_count > 0)

{

while (_head)

{

ListItem<T>* temp = _head;

_head = _head->next;

delete temp;

}

_count = 0;

}

}

template<class T>

List<T>& List<T>::operator=(const List<T>& obj)

{

if (this == &obj)

return *this;

clear();

if (obj._count > 0)

{

ListItem<T>* prev;

ListItem<T>* temp;

ListItem<T>* src = obj._head;

for (uint i = 0; i < obj._count; i++)

{

temp = new ListItem<T>;

temp->val = src->val;

temp->next = nullptr;

if (!i)

_head = temp;

else

prev->next = temp;

prev = temp;

src = src->next;

}

_count = obj._count;

}

return *this;

}

template<class T>

T& List<T>::operator[](uint index)

{

if (index >= _count)

return _head->val;

ListItem<T>* temp = _head;

int i = 0;

while (i++ < index)

temp = temp->next;

return temp->val;

}

template<class T>

void List<T>::insert(uint index, const T& item)

{

if (index >= _count)

return;

ListItem<T>* temp = new ListItem<T>;

temp->val = item;

if (!index)

{

if (!_count)

{

_head = temp;

_head->next = nullptr;

}

else

{

temp->next = _head;

_head = temp;

}

}

else

{

ListItem<T>* prev = _head;

int i = 0;

while (i++ < index)

prev = prev->next;

temp->next = prev->next;

prev->next = temp;

}

++_count;

}

template<class T>

void List <T>::addHead(const T& item)

{

insert(0, item);

}

template<class T>

void List<T>::addTail(const T& item)

{

ListItem<T>* temp = new ListItem<T>;

temp->val = item;

temp->next = nullptr;

if (!_count)

_head = temp;

else

{

ListItem<T>* tail = _head;

int i = 0;

while (tail->next)

tail = tail->next;

tail->next = temp;

}

++_count;

}

template<class T>

void List<T>::remove(uint index)

{

if (index >= _count)

return;

ListItem<T>* temp;

if (!index)

{

temp = _head;

_head = _head->next;

delete temp;

}

else

{

ListItem<T>* prev = _head;

int i = 0;

while (i++ < index - 1)

prev = prev->next;

temp = prev->next;

prev->next = temp ? temp->next : nullptr;

delete temp;

}

--_count;

}

template<class T>

void List<T>::print()

{

std::cout << "List:\n";

if (_count == 0)

std::cout << "is empty\n";

ListItem<T>* temp = _head;

while (temp)

{

std::cout << temp->val << " ";

temp = temp->next;

}

std::cout << "\n\n";

}

void main()

{

List<int> list;

list.addTail(12);

list.addTail(34);

list.addTail(76);

list.addTail(16);

list.print();

cout << list[1] << "\n\n";

list.addHead(123);

list.print();

list.remove(0);

list.print();

}

////////////////////////////////////////////////////////////////////////////////

--- Двусвязный список

template<class T>

class Item

{

private:

T _data;

Item<T>* _prev;

Item<T>* _next;

template<class T>

friend class List;

};

template<class T>

class List

{

private:

Item<T>* _head;

Item<T>* _tail;

uint _count;

public:

List();

List(const List& obj);

~List();

uint getCount();

Item<T>* getItem(uint id);

T getItemValue(uint id);

void showAll();

void deleteAll();

void deleteItem(uint id);

void addToHead(T x);

void addToTail(T x);

void insertAfter(uint id, T data);

void insertBefore(uint id, T data);

void swap(uint id1, uint id2);

T& operator[](uint id);

List<T>& operator=(const List<T>& obj);

List<T> operator+(const List<T>& obj); // слияние

List<T> operator-(); // инверсия

};

template<typename T>

List<T>::List()

{

_head = _tail = nullptr;

_count = 0;

}

template<typename T>

List<T>::List(const List& obj)

{

_head = _tail = nullptr;

_count = 0;

Item<T>* temp = obj._head;

while (temp != nullptr)

{

addToTail(temp->_data);

temp = temp->_next;

}

}

template<typename T>

List<T>::~List()

{

deleteAll();

}

template<typename T>

uint List<T>::getCount()

{

return _count;

}

template<typename T>

Item<T>* List<T>::getItem(uint id)

{

if (id < 1 || id > _count)

{

cout << "Incorrect position!!!\n";

return nullptr;

}

Item<T>* temp;

int i;

if (id <= _count / 2)

{

temp = _head;

i = 1;

while (i != id)

{

temp = temp->_next;

i++;

}

}

else

{

temp = _tail;

i = _count;

while (i != id)

{

temp = temp->_prev;

i--;

}

}

if (temp == nullptr)

return nullptr;

else

return temp;

}

template<typename T>

T List<T>::getItemValue(uint id)

{

Item<T>* temp = getItem(id);

if (temp == nullptr)

return 0;

else

return temp->_data;

}

template<typename T>

void List<T>::showAll()

{

if (_count == 0)

{

cout << "No print! No Items!\n";

return;

}

Item<T>* temp = _head;

for (int i(0); i < _count; i++)

{

cout << temp->_data << " | ";

temp = temp->_next;

}

cout << "\n\n";

}

template<typename T>

void List<T>::deleteAll()

{

while (_count != 0)

deleteItem(1);

}

template<typename T>

void List<T>::deleteItem(uint id)

{

if (id < 1 || id > _count)

{

cout << "Incorrect position!!!\n";

return;

}

int i = 1;

Item<T>* del;

Item<T>* prevDel;

Item<T>* afterDel;

if (id <= _count / 2)

{

del = _head;

i = 1;

while (i != id)

{

del = del->_next;

i++;

}

}

else

{

del = _tail;

i = _count;

while (i != id)

{

del = del->_prev;

i--;

}

}

prevDel = del->_prev;

afterDel = del->_next;

if (prevDel != nullptr && _count != 1)

prevDel->_next = afterDel;

if (afterDel != nullptr && _count != 1)

afterDel->_prev = prevDel;

if (id == 1)

_head = afterDel;

if (id == _count)

_tail = prevDel;

delete del;

--_count;

}

template<typename T>

void List<T>::addToHead(T x)

{

Item<T>* temp = new Item<T>;

temp->_prev = nullptr;

temp->_data = x;

temp->_next = _head;

if (_head != nullptr)

_head->_prev = temp;

if (_count == 0)

_head = _tail = temp;

else

_head = temp;

_count++;

}

template<typename T>

void List<T>::addToTail(T x)

{

Item<T>* temp = new Item<T>;

temp->_prev = _tail;

temp->_data = x;

temp->_next = nullptr;

if (_tail != nullptr)

_tail->_next = temp;

if (_count == 0)

_head = _tail = temp;

else

_tail = temp;

_count++;

}

template<typename T>

void List<T>::insertAfter(uint id, T _data)

{

if (id<1 || id>_count)

{

cout << "Incorrect position!!!\n";

return;

}

if (id == _count)

{

addToTail(_data);

return;

}

Item<T>* target = getItem(id);

Item<T>* afterTarget = target->_next;

Item<T>* temp = new Item<T>;

temp->_prev = target;

temp->_data = _data;

temp->_next = afterTarget;

target->_next = afterTarget->_prev = temp;

_count++;

}

template<typename T>

void List<T>::insertBefore(uint id, T _data)

{

if (id<1 || id>_count)

{

cout << "Incorrect position!!!\n";

return;

}

if (id == 1)

{

addToHead(_data);

return;

}

Item<T>* target = getItem(id);

Item<T>* beforeTarget = target->_prev;

Item<T>* temp = new Item<T>;

temp->_prev = beforeTarget;

temp->_data = _data;

temp->_next = target;

beforeTarget->_next = temp;

target->_prev = temp;

_count++;

}

template<typename T>

void List<T>::swap(uint id1, uint id2)

{

if (id1<1 || id1>_count || id2<1 || id2>_count)

{

cout << "Incorrect position!!!\n";

return;

}

if (id1 == id2)

return;

Item<T>* a = getItem(id1);

Item<T>* b = getItem(id2);

T temp = a->_data;

a->_data = b->_data;

b->_data = temp;

}

template<typename T>

T& List<T>::operator[](uint id)

{

Item<T>* temp = getItem(id);

return temp->_data;

}

template<typename T>

List<T>& List<T>::operator=(const List<T>& obj)

{

if (this == &obj)

return *this;

this->~List();

Item<T>* temp = obj._head;

while (temp != 0)

{

addToTail(temp->_data);

temp = temp->_next;

}

return *this;

}

template<typename T>

List<T> List<T>::operator+(const List<T>& obj)

{

List<T> result(*this);

Item<T>* temp = obj._head;

while (temp != 0)

{

result.addToTail(temp->_data);

temp = temp->_next;

}

return result;

}

template<typename T>

List<T> List<T>::operator-()

{

List result;

Item<T>* temp = _head;

while (temp != 0)

{

result.addToHead(temp->_data);

temp = temp->_next;

}

return result;

}

void main()

{

List<int> list;

list.addToTail(101);

list.addToTail(102);

list.addToTail(103);

list.showAll();

List<int> list2;

list2 = list;

list.showAll();

List<int> res;

res = list + -list2;

res.showAll();

res.insertAfter(6, 123123);

res.showAll();

res.insertAfter(1, 123123);

res.showAll();

res.insertBefore(2, 100000);

res.showAll();

res.swap(2, 5);

res.showAll();

res.deleteItem(1);

res.showAll();

}