# Doubly circular link list implementation

I am supposed to be creating a doubly circular linked list, but I am now have problems creating the actual linked list. Is there a problem with the classes? Also, for the assignment, the list is suppose to be a template class, but now I just want to get the code to work.

#include <iostream>
#include <string>
#include <iomanip>
#include <stdio.h>

using namespace std;
//template <class Object>

//template <class Object>
class Node
{
//friend ostream& operator<<(ostream& os, const Node&c);
public:
Node( int d=0);
void print(){
cout<<this->data<<endl;
}
//private:
Node* next;
Node* prev;
int data;

};
Node::Node(int d):data(d)
{

}

//template <class Object>
{
void create();
public:
{create();}
int base;

const Node& front() const;//element at current
const Node& back() const;//element following current
void move();
void insert (const Node & a);//add after current
void remove (const Node &a);
void print();
private:
Node* current;//current
Node* tail;
};

{
{
cout<<"print function"<<endl;
cout<<nodePt->data<<endl;
nodePt=nodePt->next;
}
}
//element at current

{
current = head = tail = new Node(0);
current->next = current->prev = current;
}

{
return *current;
}
//element after current
{
return *current ->next;
}

{
current = current ->next;
}
//insert after current
void LinkList :: insert(const Node& a)
{
Node* newNode= new Node();
newNode->prev=current;
newNode->next=current->next;
newNode->prev->next=newNode;
newNode->next->prev=newNode;
current=newNode;
}
{
Node* oldNode;
oldNode=current;
oldNode->prev->next=oldNode->next;
oldNode->next->prev=oldNode->prev;
delete oldNode;
}

//main file
#include <iostream>
#include <string>
#include <iomanip>
#include <stdio.h>

using namespace std;

int main()
{
int n;
cout<<"How many Nodes would you like to create"<<endl;
cin>>n;

list1.print();
for(int loop = 0;loop < n;++loop)
{
list1.insert(loop);
}
list1.print();
}


You have done the correct thing by putting a sentinel element into the list.
This makes adding/removing and generally manipulating the list trivial because you don't need to handle NULL links in the list.

But you have done it using a two phase create.

1. You have to construct your list.
2. You have to call create to initialize it.

This is a very bad idea. Your object should be fully constructed at the end of the constructor. That way users can not incorrectly initialize your class.

There is also a bug in your create. You create a node but you don;t link it to anything:

void LinkList::create()
{
Node start(0);  // This node is destroyed at the end of the function.
}


What you should be doing is:

LinkedList::LinkedList()
: current(new Node(0, NULL, NULL))
// , tail(current)      since it is circular these are beside each other.
{
current->prev = current;
cureent->next = current;
}


Also your code can delete the sentinel and thus cause all sorts of problems. You should not allow the deletion of the sentinel and your other functions should check for a list with just a sentinel in them (this is the empty list).

Why are you giving back references to the Node? This is an internal implementation detail. Return a reference to the value (or throw an exception if the list is empty). By returning a node you are binding your self to use a specific implementation (take a leaf out of the standard library and just return a reference to the value).

const Node& LinkList::back()const


Same comment again:

const Node& LinkList::front() const


Not sure I have seen this functionality in a list before. It seems to allow you to move the head around inside the list.

void LinkList::move()


So this is why you have to return the node above?

void LinkList :: insert(const Node& a)


I would rather have insert_front/insert_back/insert_at functionality.

Remove has some issues:

void LinkList::remove(const Node& a)


Two problems:

1. You don't update current (so it points at the deleted node).
2. You allow the sentinel to be deleted.
If you delete the last node the easy insertion/deletion breaks down.

This is what I would do:

class LL
{
struct Node {
int value;
Node* next;
Node* prev;
Node() // Sentinel
: next(this)
, prev(this)
{}
Node(int val, Node* prev, Node* next)
: value(val)
, next(next)
, prev(prev)
{
prev->next = this;
next->prev = this;
}
~Node()
{
prev->next = next;
next->prev = prev;
}
};
Node* current;
LL()
: current(new Node)
{}
~LL()
{
while(!empty())
{
delete current->next;
}
delete current;
}
bool empty() const { return current == current->next;}
void insert_front()
{
new Node(current, current->next);
}
void insert_back()
{
new Node(current->prev, current);
}
void delete_front()
{
if (!empty())
delete current->next;
}
void delete_back()
{
if (!empty())
delete current->prev;
}
int& front()
{
if (empty()) {throw empty_exception();}
return current->next->value;
}
int& back()
{
if (empty()) {throw empty_exception();}
return current->prev->value;
}
};