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();
}

Loki Astari · Accepted Answer · 2013-07-12 02:12:49Z

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.

You have to construct your list.
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:

You don't update current (so it points at the deleted node).
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;
    }
};

@YoungHyunYoo: Have a look at: codereview.stackexchange.com/a/126007/507 — Loki Astari
– Loki Astari, Commented Sep 11, 2016 at 10:30

Stack Exchange Network

Doubly circular link list implementation

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Doubly circular link list implementation

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions