Double Linked List

gistfile1.txt

#include <iostream>
using namespace std;
struct Elem
{
	int data; // მონაცემი
	Elem * next, *prev;
};
class List
{
	Elem * Head, *Tail;
	int Count;
public:
	List();
	~List();

	int GetCount();
	// Получить элемент списка
	Elem* GetElem(int);

	void DelAll();

	void Del(int pos = 0);
	// ჩაამატე ელემენტი პირველ ადგილზე თუ პარამეტრი არაა მითითებული
	void Insert(int pos = 0);

	void AddTail(int n);

	void AddHead(int n);

	void Print();

	void Print(int pos);

};
List::List()
{
	// თავიდან სია ცარიელია
	Head = Tail = NULL;
	Count = 0;
}
List::~List()
{
	// ყველა ელემენტის წაშლა
	DelAll();
}
void List::AddHead(int n)
{
	// ახალი ელემენტი
	Elem * temp = new Elem;
	// წინა არ არსებობს
	temp->prev = 0;
	// მონაცემის შეყვანა
	temp->data = n;
	// შემდეგი - ყოფილი თავი
	temp->next = Head;
	// თუ ელემენტები არსებობს
	if (Head != 0)
		Head->prev = temp;
	// თუ ელემენტი პირველია, მაშინ ის ერთდროულად თავიცაა და კუდიც
	if (Count == 0)
		Head = Tail = temp;
	else
		// სხვა შემთხვევაში ახალი ელემენტი ხდება - სათავო
		Head = temp;
	Count++;
}
void List::AddTail(int n)
{
	// ახალი ელემენტის შექმნა
	Elem * temp = new Elem;
	// შემდეგი არ არსებობს
	temp->next = 0;
	// მონაცემის შეყვანა
	temp->data = n;
	// წინა - ყოფილი კუდი
	temp->prev = Tail;
	// თუ ელემენტები არსებობს
	if (Tail != 0)
		Tail->next = temp;
	// თუ ელემენტი პირველია, მაშინ ის ერთდროულად თავიცაა და კუდიც
	if (Count == 0)
		Head = Tail = temp;
	else
		// სხვა შემთხვევაში ახალი ელემენტი ხდება - კუდი
		Tail = temp;
	Count++;
}
void List::Insert(int pos)
{
	// თუ პარამეტრი არ გადმოეცა ან 0-ის ტოლია, მაშინ მოითხოვე ის
	if (pos == 0)
	{
		cout << "Input position: ";
		cin >> pos;
	}
	// თუ ის 1-მდეა ან  Count-ზე მეტია
	if (pos < 1 || pos > Count + 1)
	{
		// არასწორი პოზიცია
		cout << "Incorrect position !!!\n";
		return;
	}
	// თუ ჩაემატა სიის ბოლოში
	if (pos == Count + 1)
	{
		// მონაცემის ჩამატება
		int data;
		cout << "Input new number: ";
		cin >> data;
		// დამატება სიის ბოლოში
		AddTail(data);
		return;
	}
	else if (pos == 1)
	{
		// მონაცემის ჩამატებ
		int data;
		cout << "Input new number: ";
		cin >> data;
		// დამატება სიის დასაწყისში 
		AddHead(data);
		return;
	}
	// მთვლელი
	int i = 1;
	// თავიდან გადაიზომება n - 1 ელემენტი
	Elem * Ins = Head;
	while (i < pos)
	{
		// ელემენტთან მიღწევა
		// რომლიც წინაც ჩაემატება
		Ins = Ins->next;
		i++;
	}
	// ელემენტთან მიღწევა
	// რომლის მერეც უნდა ჩაემატოს
	Elem * PrevIns = Ins->prev;
	// ახალი ელემენტის შექმნა
	Elem * temp = new Elem;
	// მონაცემის შეყვანა
	cout << "Input new number: ";
	cin >> temp->data;
	// კავშირის აწყობა
	if (PrevIns != 0 && Count != 1)
		PrevIns->next = temp;
	temp->next = Ins;
	temp->prev = PrevIns;
	Ins->prev = temp;
	Count++;
}
void List::Del(int pos)
{
	if (pos == 0)
	{
		cout << "Input position: ";
		cin >> pos;
	}
	if (pos < 1 || pos > Count)
	{
		// არასწორი პოზიცია
		cout << "Incorrect position !!!\n";
		return;
	}
	// მთვლელი
	int i = 1;
	Elem * Del = Head;
	while (i < pos)
	{
		// ელემენტთან მიღწევა, 
		// რომელიც უნდა წაიშალოს
		Del = Del->next;
		i++;
	}

	Elem * PrevDel = Del->prev;
	// ელემნტი, წასაშლელი ელემენტის შემდეგ
	Elem * AfterDel = Del->next;
	// თუ წასაშლელი არაა სათავო
	if (PrevDel != 0 && Count != 1)
		PrevDel->next = AfterDel;
	// თუ წასაშლელი არაა კუდი
	if (AfterDel != 0 && Count != 1)
		AfterDel->prev = PrevDel;
	if (pos == 1)
		Head = AfterDel;
	if (pos == Count)
		Tail = PrevDel;
	delete Del;
	Count--;
}
void List::Print(int pos)
{
	// თუ ის 1-მდეა ან  Count-ზე მეტია
	if (pos < 1 || pos > Count)
	{
		// არასწორი პოზიცია
		cout << "Incorrect position !!!\n";
		return;
	}
	Elem * temp;
	// განსაზღვრა, რომელ მხარეს ვიმოძრავებთ უფრო სწაფად
	if (pos <= Count / 2)
	{
		// მთვლელი თავიდან
		temp = Head;
		int i = 1;
		while (i < pos)
		{
			// მოძრაობა სასურველი ელემენტისაკენ
			temp = temp->next;
			i++;
		}
	}
	else
	{
		// მთვლელი კუდიდან
		temp = Tail;
		int i = 1;
		while (i <= Count - pos)
		{
			// მოძრაობა სასურველი ელემენტისაკენ
			temp = temp->prev;
			i++;
		}
	}
	// ელემენტის გამოტანა
	cout << pos << " element: ";
	cout << temp->data << endl;
}
void List::Print()
{
	
	if (Count != 0)
	{
		Elem * temp = Head;
		cout << "( ";
		while (temp->next != 0)
		{
			cout << temp->data << ", ";
			temp = temp->next;
		}
		cout << temp->data << " )\n";
	}
}
void List::DelAll()
{

	while (Count != 0)
		Del(1);
}
int List::GetCount()
{
	return Count;
}
Elem * List::GetElem(int pos)
{
	Elem *temp = Head;

	if (pos < 1 || pos > Count)
	{
		// არასწორი პოზიცია
		cout << "Incorrect position !!!\n";
		return 0;
	}
	int i = 1;
	// სასურველი ელემენტის ძებნა
	while (i < pos && temp != 0)
	{
		temp = temp->next;
		i++;
	}
	if (temp == 0)
		return 0;
	else
		return temp;
}
// სატესტო მაგალითი
void main()
{
	List L;
	const int n = 10;
	int a[n] = { 0,1,2,3,4,5,6,7,8,9 };
	// ელემენტების დამატება
	// ლუწი ინდექსის მქონენი თავში, კენტისა ბოლოში
	for (int i = 0; i < n; i++)
		if (i % 2 == 0)
			L.AddHead(a[i]);
		else
			L.AddTail(a[i]);
	// სიის გამოტანა
	cout << "List L:\n";
	L.Print();
	cout << endl;
	// ელემენტის ჩამატება სიაში
	L.Insert();
	// სიის გამოტანა
	cout << "List L:\n";
	L.Print();
	// სიის მე-2 და მე-8 ელემენტების გამოტანა
	L.Print(2);
	L.Print(8);



	cin.get();
	cin.get();
}