Created
December 16, 2012 04:29
-
-
Save yefim/4303323 to your computer and use it in GitHub Desktop.
Doubly Linked list implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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