Doubly circular link list implementation

Question

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;
 friend class LinkList;
};
Node::Node(int d):data(d)
{
}
//template <class Object>
class LinkList
{
void create();
public:
 //LinkList();
 LinkList():head(NULL),tail(NULL),current(NULL)
 {create();}
 int base;
 //LinkList(const LinkList & rhs, const LinkList & lhs);
 ~LinkList(){delete current;}
 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* head;
 Node* tail;
};
void LinkList::print()
{
 Node *nodePt =head->next;
 while(nodePt != head)
 {
 cout<<"print function"<<endl;
 cout<<nodePt->data<<endl;
 nodePt=nodePt->next;
 }
}
//element at current
void LinkList::create()
{
 current = head = tail = new Node(0);
 current->next = current->prev = current;
}
const Node& LinkList::back()const
{
 return *current;
}
//element after current
const Node& LinkList::front() const
{
 return *current ->next;
}
void LinkList::move()
{
 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;
}
void LinkList::remove(const Node& a)
{
 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> 
#include "LinkedList.h"
using namespace std;
int main()
{
 int n;
 cout<<"How many Nodes would you like to create"<<endl;
 cin>>n;
 LinkList list1 ;
 list1.print();
 for(int loop = 0;loop < n;++loop)
 {
 list1.insert(loop);
 }
 list1.print();
}

Answer 1

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))
 // , head(current) You don't actually need head/tail
 // , 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;
 }
};

• Loki Astari: @YoungHyunYoo: Have a look at: codereview.stackexchange.com/a/126007/507