Skip to content

Instantly share code, notes, and snippets.

@sjgriffiths
Created January 7, 2018 20:11
Show Gist options
  • Save sjgriffiths/84ad5a79dc9f8a6b77e9442af6836f84 to your computer and use it in GitHub Desktop.
Save sjgriffiths/84ad5a79dc9f8a6b77e9442af6836f84 to your computer and use it in GitHub Desktop.
Double-ended singly-linked list (C++)
/**
DESLinkedList.h
Implements a class template of a double-ended
(front-and-end-pointered) singly-linked list.
@author Sam Griffiths
www.computist.xyz
*/
#pragma once
#include <iostream>
template <typename T>
class DESLinkedList
{
private:
struct Node
{
T data;
Node *next;
Node(const T &data) : data(data), next(nullptr) {}
};
Node *front;
Node *back;
public:
//The front or back of the list can be used
enum End { FRONT, BACK };
//Default constructor initialises empty list
DESLinkedList() : front(nullptr), back(nullptr) {}
//Destructor deletes all elements
~DESLinkedList()
{
while (!empty())
{
Node *n = front->next;
delete front;
front = n;
}
}
//Returns true if there are no elements in the list
bool empty() const { return front == nullptr; }
//Adds the given element to the given end of the list
void add(const T &elt, End end)
{
Node *newNode = new Node(elt);
if (empty())
front = back = newNode;
else switch (end)
{
case FRONT:
newNode->next = front;
front = newNode;
break;
case BACK:
back->next = newNode;
back = newNode;
break;
}
}
//Removes the element at the given end of the list
void remove(End end)
{
Node *node = nullptr;
switch (end)
{
case FRONT:
node = front;
front = node->next;
delete node;
break;
case BACK:
//NOT IMPLEMENTED
//This can be implemented if needed by iterating over
//the list to the penultimate element. However, this
//is undesirably linear in complexity. It's wise to
//use a doubly-linked list instead.
break;
}
}
//Returns the element at the given end of the list
T &peek(End end)
{
Node *node = (end == FRONT) ? front : back;
return node->data;
}
//Outputs the list to the stream
friend std::ostream& operator<<(std::ostream &os, const DESLinkedList &l)
{
Node *n = l.front;
while (n)
{
os << n->data << " ";
n = n->next;
}
return os;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment