Linked List - access 3rd node onwards

[swanvalkyrie]

Hi All,

I haven't done C++ for a while but started getting back into it. I am experimenting with linked lists.

I need to be able to display what is in the third node onwards. Keep in mind I have a scrappy solution of using say front+2 but it doesn't show the correct output. Can I say something like front[2] as the list is displaying so it will start from the 3rd node?

[salem c]

Are you wanting to roll your own class, or use something pre-existing?
http://www.cplusplus.com/reference/list/list/

> Can I say something like front[2] as the list is displaying so it will start from the 3rd node?
Sure, if you make your own [] operator to hide the detail.

> Keep in mind I have a scrappy solution of using say front+2
Maybe use this -> http://www.cplusplus.com/reference/iterator/advance/

[swanvalkyrie]

Thanks but i'm not sure how I would incorporate that. I have a queue that will display all items in the queue. I want it to display from the third one onwards.

When I use link->n + 2 it actually adds an additional node when displaying in cout that I never entered. It does start from the second node, but it adds a new tail one which shouldn't be there

Edit: Sorry i am still learning lists/nodes but i got it working up until this point.

[salem c]

Post your code, and don't forget to use the [code][/code] tags.

[jonnin]

in a standard pointer based linked list,
head->next->next.data is the third item.
you need to check all the chains for nulls, in case the list has 1-2 items or is totally empty etc.
you can take the above as a pointer and then just iterate the rest of the list..

tmp = head->next->next;
while(tmp)
cout << tmp.data <<endl;
tmp = tmp->next;

or possibly to avoid the checks by hand... //this is the way to do it, but you have to understand the above to get here.
tmp = head;
while(tmp)
{
if(counter++ >2)
cout << tmp.data <<endl;
tmp = tmp->next;
}

if your list class overloads [] then you can use [] but at some point you need to understand the pointer chains and all to get it working. If your list is really a vector or something, you can use [] and forget pointers, but then it isnt a list, its a mask for a vector, and that has both advantages and disadvantages. You can tie a list to a vector and have the advantages of both, but it takes a bit of work to get that idea right.

[doug4]

Not to be too nit-picky, but in a standard pointer-based linked list, you need to dereference the pointer to access the data.

So, @jonnin's post should contain the following statements:

head->next->next->data

and

cout << tmp->data << endl;

[jonnin]

pick away... and you are totally right!

[salem c]

@doug4
Well that is, until you try to access the third element of a list with only two elements.

[jonnin]

he was referring to my post which addressed that (and then bungled the syntax).

[swanvalkyrie]

Here is my code, again it's really not great with the insert section. Lines 182-186 i'm just using this as a testing section to see what data is being returned.

/*

	* C++ Program to Implement Priority Queue

	*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>


using namespace std;


/*

 * Node Declaration

 */

struct node         //created a node structure

{

	int priority;   //apart of node structure is integer priority

	int patient;       //part 2 of node structure is integer patient

	struct node* link;  //part 3 of node structure is link pointer to next node

};

/*

 * Class Priority Queue

 */

class Priority_Queue

{

private:

	node* front;   //create front node pointer to signify front of node list

public:

	Priority_Queue()

	{

		front = NULL;  //setting front to null

	}

	/*

	 * Insert into Priority Queue

	 */

	void insert(int patient, int priority)   //these values are from previous user input

	{

		node* tmp, * q;  // declaring pointer nodes tmp and q

		tmp = new node;  // creating a new node in the list called tmp -- TMP USED FOR NEW NODE CREATION

		tmp->patient = patient;    //In the new node, create a new value in patient segment equal to 'patient' entered by user

		tmp->priority = priority;   //In the new node, create a new value in priority segment equal to 'priority' entered by user

		
	

		if (front == NULL || priority > front->priority)    //If the front node is empty or the prority (entered by user) is less than the front node looking at priority

		{

			tmp->link = front;    // tmp node should point to link that the front node is linking to

			front = tmp;          // front is equal to tmp -- front moves to a new node at the front of queue
								  //so if the users value is less than the top of the queue, new node is new front of queue
		}

		else 

		{

			q = front;     //q is equal to front

			while (q->link != NULL && q->link->priority >= priority) //while q looking at link not null and priority is <= new priority

				q = q->link;   //q moves to next node looking at link

			tmp->link = q->link;   //tmp looking at link equals what q to link is

			q->link = tmp;   // q link becomes equals tmp to become next node in line

		}

	}

	/*

	 * Delete from Priority Queue

	 */

	void del()			//delete from Priority Queue

	{

		node* tmp;		//create tmp pointer to node

		if (front == NULL)		//if front of queue is equal to null

			cout << "Queue is already empty\n";	 //display empty queue

		else              //If the queue is not empty

		{

			tmp = front;	//tmp is assigned front

			cout << "Deleted item is: " << tmp->patient << endl;	//display deleted patient is tmp (looking at patient in front of queue)

			front = front->link;		//front equal front looking at link (becomes new front of queue)

			free(tmp);			//empties tmp

		}

	}

	/*

	 * Print Priority Queue

	 */

	void display()

	{

		node* ptr;			//create ptr pointer node
		node* secondptr;
		ptr = front;		//set ptr to front of queue
		secondptr = front + 2;
	
		

		if (front == NULL)		//if front of queue is null

			cout << "Queue is empty\n";			//display queue empty

		else

		{
			cout << "Queue is :\n\n";			//display queue is

			cout << "Priority       PatientNo\n\n";		//display headers priority and patient

			while (ptr != NULL)		//while ptr is not null

			{

				cout << ptr->priority+2<< "                 " << ptr->patient+2<< endl;	//display ptr priority and ptr patient
				
				ptr = ptr->link;				//ptr equals ptr looking at link to next node

			}

			

			cout << "+++++++++++++++++\n\n" << endl;
			cout << front->patient << endl;

			cout << "++++++++++++++++\n\n" << endl;


			cout << "-------------Emergency Room------------\n" << endl;
			cout << "Priority       PatientNo\n";

			cout << front->priority << "                 " << front->patient << endl;
			cout << front->priority + 1 << "                 " << front->patient + 1  << endl;
			cout << "-----end-------" << endl;
		}

	}

};

/*

 * Main

 */

int main()

{

	int choice, patient, priority;			//declare choice, patient and priority as integer

	Priority_Queue pq;						//pq as priority queue

	Priority_Queue emergency;						//pq as priority queue


	do

	{

		cout << "1.Insert\n";				//display Insert then newline
		
		cout << "2.Delete\n";				//display Delete nl

		cout << "3.Display\n";				//display Display nl

		cout << "4.Quit\n";					//display Quit nl

		cout << "Enter your choice : ";		//prompt choice

		cin >> choice;						//input into choice variable

		switch (choice)   //dependant on input value select relevant case

		{

		case 1:

			cout << "Input patient number to be added in the queue : ";		//enter patient ID

			cin >> patient;		//user input into patient variable

			cout << "Enter its priority : ";		//enter patient priority

			cin >> priority;				//user input into priority

			pq.insert(patient, priority);	//insert into priority queue, patient and priority


			break;  

		case 2:

			pq.del();			//does del function in PQ

			break;

		case 3:

			pq.display();		//does display function in PQ

			break;

		case 4:

			break;				

		default:			//if no valid numbers are entered then display wrong choice

			cout << "Wrong choice\n";

		}

	}

	while (choice != 4);			//if choice is not equal to four to quit then return 0

	return 0;

}
 

[swanvalkyrie]

I am trying to display the top two highest priorities in the emgncy room (which are greater than 4). I realised there is a far better way to do this with another class or queue maybe, but due to my skills I thought i could get around it another less ideal way. I was going to implement a timer but that's not going to work either.

I have been further working and wasn't sure if the best way to do this is by assininging the 2 people in the emergncy room is just to enter into variables. if the person doesn't fall into the two highest priorities then they go into the waiting list. I've adjusted the code to the below, but I dont think it will work either. Because when the patients are deleted, they are deleted from the top of the node rather than what is in the emergency room. So they can't "shuffle forward" so to speak,

		case 1:

			cout << "Input patient number to be added in the queue : ";		//enter patient ID

			cin >> patient;		//user input into patient variable

			cout << "Enter priority between 1 and 10 : ";		//enter patient priority

			cin >> tmp1;

			if (tmp1 >= 4  && epatient1 == 0)
			{

				tmp1 = epatient1;
			}

			else if (tmp1 >= 4 && epatient1 != 0)
			{
				tmp2 = epatient2;
			}

//			cin >> priority;				//user input into priority

			if (priority <= 0 || priority > 10)

			{
			
			cout << "Priority is not between 1 and 10" << endl;
			cout << "Enter priority between 1 and 10" << endl;
			cin >> priority;

	


			pq.insert(patient, priority);	//insert into priority queue, patient and priority
			}

[keskiverto]

* C++ Program to Implement Priority Queue

Hmm,
http://www.cplusplus.com/reference/queue/priority_queue/

Untested:

#include <queue>
#include <iostream>

struct Patient {
  int id;
  int priority;
  Patient( int id, int prio )
  : id{id}, priority{prio}
  {}
};

bool operator< ( const Patient& lhs, const Patient& rhs ) {
  return lhs.priority < rhs.priority;
}

int main() {
  std::priority_queue<Patient> pq;
  pq.emplace( 42, 10 );
  pq.emplace( 43, 99 );
  pq.emplace( 44, 1 );
  pq.emplace( 40, 10 );

  while ( ! pq.empty() ) {
    std::cout << pq.top().id << '\n';
    pq.pop();
  }
}

[swanvalkyrie]

Thanks keskiverto, I ran the code and the output is the 40 values. If you check out the process of my code they seem to need to go into two different queues. I don't know if i've overthought this but i'm on the wrong track

[keskiverto]

Two queues:

alias PQ = std::priority_queue<Patient>;

void enter( PQ& high, PQ& low, int id, int prio ) {
  if ( prio < 4 ) { // regular patient
    low.emplace( id, prio );
  } else { // emergencies
    high.emplace( id, prio );
  }
}

but with that some days could be all emergencies, not just top 2.

Top two are emergencies regardless of priority:

if ( ! pq.empty() ) {
  std::cout << "Emergencies:\n";
  size_t count = 0;
  while ( ! pq.empty() && count < 2 ) {
    std::cout << pq.top().id << " priority " pq.top().priority << '\n';
    pq.pop(); // treat patient
    ++count;
  }
}
if ( ! pq.empty() ) {
  std::cout << "Others:\n";
  while ( ! pq.empty() ) {
    std::cout << pq.top().id << '\n';
    pq.pop(); // treat patient
  }
}

[jonnin]

just so you know, you can do it with the linked list.

one way to do that is to have a list of lists (or a vector of lists) by priority, eg outerlist[4] is priority 4 people, and it has a list inside that is just a dumb first come first serve ordering. Its still a lot more code than using a tool that is built for this kind of problem, but its doable and a good exercise**

a problem with these is a concept called starvation. if you always have a couple of high priority items, the priority 1 or zero guys will die waiting for treatment. Which is exactly how emergency rooms do work, but its worth a mention.

** actually, this is an opinion thing. Its good practice to do the work, but solving the problem the wrong way is a questionable thing to spend time on. You would learn a lot about linked lists, but not much about the right way to solve problems.