1
\$\begingroup\$

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();
}
\$\endgroup\$
7
\$\begingroup\$

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;
    }
};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.