Skip to content

Instantly share code, notes, and snippets.

@dgodfrey206
Created December 4, 2014 03:51
Show Gist options
  • Save dgodfrey206/5c0158901fd6018e1653 to your computer and use it in GitHub Desktop.
Save dgodfrey206/5c0158901fd6018e1653 to your computer and use it in GitHub Desktop.
Circular linked list
#include <iostream>
template <class T>
class circular_linked_list
{
struct node;
node* tail{nullptr}, **back_ptr{&tail}, **front_ptr{nullptr};
int m_size{0};
template <class U>
friend void Display(circular_linked_list<U> const&);
public:
circular_linked_list() = default;
circular_linked_list(int);
circular_linked_list(circular_linked_list const&);
T& front() const
{
if (m_size == 1)
return tail->data;
if (m_size > 1)
return tail->next->data;
return tail->data;
}
T& back() const { return tail->data; }
int size() const { return m_size; }
bool empty() const { return !m_size; }
void push_back(T const&);
node* erase(T const&);
};
template <class T>
struct circular_linked_list<T>::node
{
friend class circular_linked_list<T>;
node(T const& data = T(), node* next = nullptr)
: data(data)
, next(next)
{}
template <class U>
friend void Display(circular_linked_list<U> const&);
private:
T data{0};
node* next{nullptr};
};
template <class T>
circular_linked_list<T>::circular_linked_list(int size)
: m_size(0)
{
while (size--)
push_back(0);
}
template <class T>
circular_linked_list<T>::circular_linked_list(circular_linked_list<T> const& other)
: m_size(other.m_size)
{
for (node* pos = other.tail; pos != nullptr; pos = pos->next)
push_back(pos->data);
}
template <class T>
void circular_linked_list<T>::push_back(T const& value)
{
node* new_last = new node{value, tail};
if (empty())
{
tail = new_last;
front_ptr = &tail;
}
else
{
if (size() == 1)
{
tail->next = new_last;
tail = new_last;
}
else
{
node* pos = tail;
while (pos->next != tail)
pos = pos->next;
pos->next = new_last;
}
}
++m_size;
}
template <class T>
typename circular_linked_list<T>::node* circular_linked_list<T>::erase(T const& value)
{
node** p = &tail;
auto remove = [] (node** p)
{
node* temp = *p;
*p = (*p)->next;
delete *temp;
};
if (!*p)
return nullptr;
if ((*p)->data == value)
remove(p);
else
{
for (p = &(*p)->next; *p != tail && (*p)->data != value; )
p = &(*p)->next;
if ((*p)->data == value)
remove(p);
else
return nullptr;
}
--m_size;
return tail;
}
template <class T>
void Display(circular_linked_list<T> const& list)
{
std::cout << list.front();
//if (begin->next == list.tail)
// std::cout << list.tail->data;
}
int main()
{
circular_linked_list<int> list;
list.push_back(1);
list.push_back(3);
Display(list);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment