Circular Doubly Linked List

[hadoken50]

Hi, for this assignment, I am to implement a program that would read a series of cities from a text file and put it into a sorted circular doubly linked list while also using head and tail as sentinel nodes. I have already done this assignment by using a singly linked list and now I'm supposed to convert it into a circular doubly linked list. Now, I'm having some trouble trying to actually link the back pointer to the previous node in the linked list. I get the whole concept of the doubly linked list but I just have a hard time of actually trying to implement it.

//file that includes all the functions for citylist
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include "CityList.h"
#include "City.h"
using namespace std;

/**************************************************
Constructor
This function allocates an empty node to act as a
sentinel node: it makes the code shorter and the
processing of the list faster.
**************************************************/
CityList::CityList()
{
	head = new ListNode;
	head->back = tail;
	
	tail = new ListNode;
	tail->forw = head;


	count = 0;
}


/**************************************************
Display the value stored in each node of
the linked list
**************************************************/
void CityList::displayForwardList() const
{
	ListNode *nodePtr = head->forw;
	ListNode *backPtr = tail->back;
	while (nodePtr)
	{
		cout << setw(10) << nodePtr->data.getState();
		cout << setw(10) << nodePtr->data.getYear();
		cout << setw(20) << nodePtr->data.getCity();
		cout << endl;

		nodePtr = nodePtr->forw;
	}
	
	cout << endl << "Printing backwards" << endl;
	cout << "_____________________" << endl;
	while (backPtr)
	{
		cout << setw(10) << backPtr->data.getState();
		cout << setw(10) << backPtr->data.getYear();
		cout << setw(20) << backPtr->data.getCity();
		cout << endl;

		backPtr = backPtr;
	}
}
/**************************************************
Insert a new node into a sorted list and
keeps the list sorted while also checking
for duplicates
**************************************************/
bool CityList::insertNode(City dataIn)
{
	ListNode *newNode;
	ListNode *nodePtr = head->forw;
	ListNode *holder = head;
	ListNode *prevNode = head;
	ListNode *dataPtr;
	CityList list;

	// Allocate a new node and store dataIn there.
	newNode = new ListNode;
	newNode->data = dataIn;
	newNode->forw = head;
	newNode->back = tail;
		//head = newNode;
		tail = newNode;

	if (list.searchList(dataIn.getCity(), dataIn))
	{
		cout << dataIn.getCity() << " is already in the list" << endl;
		deleteNode(dataIn.getCity());
		return false;
	}

	// Skip all nodes whose value is less than num.
	while (nodePtr != NULL && nodePtr->data.getCity() < dataIn.getCity())
	{
		prevNode = nodePtr;
		nodePtr = nodePtr->forw;
	}

	// Check for duplicates and if true, reject 

	// Update links to insert the new node
	prevNode->forw = newNode;
	newNode->forw = nodePtr;
	newNode->back = prevNode;
	tail->back = newNode->back;
	count++;

	/*head->back = newNode->back;
	newNode->back = head->back;*/
	//newNode->back = nodePtr;


	cout << right << "Back: " << newNode->back->data.getCity() << "  Forward:  " << newNode->data.getCity()<<endl;

	return true;
}

[keskiverto]

This function allocates an empty node

A node. One node.

CityList::CityList()
{
	head = new ListNode; // ok, one
	head->back = tail; // error, tail is undefined
	tail = new ListNode; // error, two is not one 

ListNode *nodePtr = head->forw;
while ( nodePtr )
{
  nodePtr = nodePtr->forw;
}

Even in singly linked circular list there should be no end, or the list would not be circular.
The "head and tail as sentinel nodes" does not fit to the concept of circular list. Something is odd here.


In a doubly linked list each node points both to node before and to node after them. If you can maintain one set of links, then it should be trivial to maintain the other too. Just more work.

// Insert X between A and B
insertAfter( ListNode * pos, const Foo & data ) {
  Foo * node = new Foo( data );
  node->forw = pos->forw; // X.forw = B
  node->forw->back = node; // B.back = X
  pos->forw = node; // A.forw = X
  node->back = pos; // X.back = A
}