Skip to content

Instantly share code, notes, and snippets.

@dgodfrey206
Last active August 29, 2015 14:10
Show Gist options
  • Save dgodfrey206/b82394310893f5cdc72f to your computer and use it in GitHub Desktop.
Save dgodfrey206/b82394310893f5cdc72f to your computer and use it in GitHub Desktop.
My version of a linked list
#include <iostream>
#include <stdexcept>
template <class T>
class LinkedList;
template <class T>
class ListElement
{
friend LinkedList<T>;
private:
ListElement(T const&, ListElement<T>*);
T datum;
ListElement<T>* next;
};
template <class T>
ListElement<T>::ListElement(T const& datum, ListElement<T>* next)
: datum(datum)
, next{next}
{ }
template <class T>
class LinkedList
{
public:
LinkedList() = default;
LinkedList(LinkedList const&);
LinkedList& operator=(LinkedList const&);
bool empty() const { return !head; }
void push_front(T const&);
void push_back(T const&);
void clear();
void remove(T const&);
T left_sibling(T const&) const;
T right_sibling(T const&) const;
void display() const;
std::size_t size() const { return m_size; }
private:
ListElement<T> *head {nullptr}, *tail {nullptr};
std::size_t m_size{0};
};
template <class T>
LinkedList<T>::LinkedList(LinkedList<T> const& other)
: head{nullptr}
, tail{nullptr}
{
for (auto ptr = &other.head; *ptr; ptr = &(*ptr)->next)
push_back((*ptr)->datum);
}
template <class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList<T> const& other)
{
if (this != &other)
{
clear();
for (auto ptr = &other.head; *ptr; ptr = &(*ptr)->next)
push_back((*ptr)->datum);
}
return *this;
}
template <class T>
void LinkedList<T>::push_front(T const& datum)
{
ListElement<T>* temp = new ListElement<T> {datum, head};
if (!head)
tail = temp;
head = temp;
++m_size;
}
template <class T>
void LinkedList<T>::push_back(T const& datum)
{
ListElement<T>* temp = new ListElement<T> {datum, nullptr};
if (!head)
head = temp;
else
tail->next = temp;
tail = temp;
++m_size;
}
template <class T>
T LinkedList<T>::right_sibling(T const& datum) const
{
ListElement<T>* ptr = head;
for (; ptr && ptr->datum != datum; ptr = ptr->next)
{}
if (ptr)
return ptr->next->datum;
throw std::invalid_argument("Invalid argument");
}
template <class T>
T LinkedList<T>::left_sibling(T const& datum) const
{
if (empty())
throw std::invalid_argument("Invalid argument");
if (size() == 1)
return head->datum;
ListElement<T>* prev = nullptr;
for (ListElement<T>* ptr = head; ptr && ptr->datum != datum; )
{
prev = ptr;
ptr = ptr->next;
}
return prev->datum;
}
template <class T>
void LinkedList<T>::clear()
{
while (head)
{
ListElement<T>* temp {head};
head = head->next;
delete temp;
--m_size;
}
tail = nullptr;
}
template <class T>
void LinkedList<T>::remove(T const& datum)
{
auto ptr = &head;
while (*ptr && (*ptr)->datum != datum)
ptr = &(*ptr)->next;
if (!*ptr)
throw std::invalid_argument("Could not find element");
auto next = (*ptr)->next;
delete *ptr;
*ptr = next;
}
template <class T>
void LinkedList<T>::display() const
{
auto ptr = &head;
while (*ptr)
{
std::cout << (*ptr)->datum << " ";
ptr = &(*ptr)->next;
}
std::cout << '\n';
}
int main()
{
LinkedList<int> list1, list2;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment