123 lines
2.2 KiB
C++
123 lines
2.2 KiB
C++
#ifndef _LIST_HPP_
|
|
#define _LIST_HPP_
|
|
#include <iostream>
|
|
#include <string>
|
|
#define listNode ln *
|
|
|
|
template <class T>
|
|
class List
|
|
{
|
|
typedef struct ln
|
|
{
|
|
T data;
|
|
listNode pred;
|
|
listNode succ;
|
|
} ln;
|
|
|
|
private:
|
|
listNode header = new ln;
|
|
listNode trailer = new ln;
|
|
int _size;
|
|
|
|
protected:
|
|
listNode firstInsertN(listNode New);
|
|
listNode lastInsertN(listNode New);
|
|
listNode succInsertN(listNode old, listNode ne);
|
|
listNode predInsertN(listNode old, listNode ne);
|
|
void removeN(listNode i);
|
|
listNode searchN(int value, int n, listNode p);
|
|
|
|
public:
|
|
int size(){return _size;}
|
|
List();
|
|
void clear();
|
|
listNode first() { return header->succ; }
|
|
listNode last() { return trailer->pred; }
|
|
T firstInsert(T New);
|
|
T lastInsert(T New);
|
|
T removeLast();
|
|
listNode succInsert(listNode Old, T New);
|
|
listNode predInsert(listNode Old, T New);
|
|
|
|
int get(int i);
|
|
listNode find(int i);
|
|
|
|
T operator[](int i)
|
|
{
|
|
listNode p = first();
|
|
while (0 < i--)
|
|
p = p->succ;
|
|
return p->data;
|
|
}
|
|
|
|
protected:
|
|
T remove(listNode p);
|
|
};
|
|
|
|
template <class T>
|
|
List<T>::List()
|
|
{
|
|
_size = 0;
|
|
header->data = 0;
|
|
header->succ = trailer;
|
|
header->pred = NULL;
|
|
|
|
trailer->data = 0;
|
|
trailer->succ = NULL;
|
|
trailer->pred = header;
|
|
}
|
|
|
|
template <class T>
|
|
void List<T>::clear()
|
|
{
|
|
while (0 < _size)
|
|
remove(0);
|
|
}
|
|
|
|
template <class T>
|
|
T List<T>::firstInsert(T New)
|
|
{
|
|
listNode temp = new ln;
|
|
temp->data = New;
|
|
temp->pred = header;
|
|
temp->succ = header->succ;
|
|
header->succ = temp;
|
|
temp->succ->pred = temp;
|
|
_size++;
|
|
return New;
|
|
}
|
|
template <class T>
|
|
T List<T>::lastInsert(T New)
|
|
{
|
|
listNode temp = new ln;
|
|
temp->data = New;
|
|
temp->succ = trailer;
|
|
temp->pred = trailer->pred;
|
|
trailer->pred = temp;
|
|
temp->pred->succ = temp;
|
|
_size++;
|
|
return New;
|
|
}
|
|
|
|
template <class T>
|
|
T List<T>::removeLast()
|
|
{
|
|
return remove(trailer->pred);
|
|
}
|
|
|
|
template <class T>
|
|
T List<T>::remove(listNode p)
|
|
{
|
|
if (!_size)
|
|
return 0;
|
|
|
|
T temp = p->data;
|
|
(p->pred)->succ = p->succ;
|
|
(p->succ)->pred = p->pred;
|
|
delete[] p;
|
|
_size--;
|
|
|
|
return temp;
|
|
}
|
|
|
|
#endif |