Skip to content

Instantly share code, notes, and snippets.

@yefim
Created December 16, 2012 04:29
Show Gist options
  • Save yefim/4303323 to your computer and use it in GitHub Desktop.
Save yefim/4303323 to your computer and use it in GitHub Desktop.
Doubly Linked list implementation
#include <iostream>
#include <string>
#include "doublell.h"
using namespace std;
DoubleLL::DoubleLL()
{
head = NULL;
tail = NULL;
}
DoubleLL::~DoubleLL()
{
while (head)
{
DLink* next = head->next;
delete head;
head = next;
}
}
DLink* DoubleLL::getHead() const
{
return head;
}
DLink* DoubleLL::getTail() const
{
return tail;
}
void DoubleLL::insert(DLink* where, const string& what)
{
DLink* newlink = new DLink();
newlink->data = what;
if (!where)
{
// check if list is empty
if (!tail)
{
newlink->next = NULL;
newlink->prev = NULL;
tail = newlink;
head = newlink;
}
else
{
newlink->next = NULL;
newlink->prev = tail;
tail->next = newlink;
tail = newlink;
}
}
else
{
// check if inserting before head
if (where == head)
{
where->prev = newlink;
newlink->next = where;
newlink->prev = NULL;
head = newlink;
}
else
{
DLink* oldprev = where->prev;
where->prev = newlink;
newlink->next = where;
newlink->prev = oldprev;
oldprev->next = newlink;
}
}
}
string DoubleLL::remove(DLink* where)
{
if (!where)
{
return "";
}
string data = where->data;
// need to check if deleting head and/or tail
if (where == head && where == tail)
{
head = NULL;
tail = NULL;
}
else if (where == head)
{
head = where->next;
head->prev = NULL;
}
else if (where == tail)
{
tail = tail->prev;
tail->next = NULL;
}
else
{
DLink* prev = where->prev;
DLink* next = where->next;
prev->next = next;
next->prev = prev;
}
delete where;
return data;
}
int DoubleLL::size() const
{
if (!tail)
{
return 0;
}
int length = 1;
DLink* current = head;
while (current != tail)
{
current = current->next;
length++;
}
return length;
}
string DoubleLL::nth(int n) const
{
int counter = 0;
DLink* current = head;
while (counter < n)
{
// checks for overflow
if (!current)
{
return "";
}
current = current->next;
}
return current->data;
}
/* File: double.h
* Author: Geoffrey (veg)
* Desc: interface for double linked list class
*/
#ifndef DOUBLELL_H_
#define DOUBLELL_H_
#include <iostream>
struct DLink
{
std::string data;
DLink* prev;
DLink* next;
};
class DoubleLL
{
private:
DLink* head;
DLink* tail;
public:
DoubleLL();
~DoubleLL();
DLink* getHead() const;
DLink* getTail() const;
void insert(DLink* where, const std::string& what);
std::string remove(DLink* where);
int size() const;
std::string nth(int n) const;
};
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment