Doubly linked list

[XodoX]

I read that you can use a while loop to read the input from a text file and create a doubly linked list? How do I do that? I would appreciate if someone could show me. Thank you!

[pseudorandom21]

Well if you're completely new to C++ I strongly suggest reading up on the "ifstream" class.

http://cplusplus.com/reference/iostream/ifstream/

Then you can easily do something like:

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

int main()
{
   const char *fileName = "C:/myFile.txt";
   ifstream inFile(fileName);//Automatically opens the file.
   string inputLine;
   while( getline(inFile,inputLine) ){
      cout << inputLine << endl;
   }
   inFile.close();
}

This example doesn't include error checking.

[XodoX]

Hi,

I saw that. But how do you load this into the doubly linked list and the input file, like integers, into the nodes? I don't get it... I thought this would load everything into one node.

[VernonDozier]

Well, can you create a doubly linked list from something OTHER than a file? If not, then don't worry about the file. Learn about doubly linked lists. If you already know how to use a doubly linked list, but you don't know how to read from a file, then forget about linked lists and learn to read from a file. If you can do both of those, but don't know how to combine the two, that's a completely different question. Which category are you in?

>> I thought this would load everything into one node.

You though WHAT would load everything into one node? What are you referring to? And if it's a "linked list", one would assume there's going to be more than one node.

[XodoX]

I do not know how to create a linked list by loading data from an input file.

And, well, I quoted him, so I obviously meant the code he posted that reads it from the file and will, I guess, load it into the list.

The books I am using to learn this do not have any examples. Just a inked list example, delete a node, and insert. But I have no idea how to create one by using the while loop to read from the file. I need an example to visualize this.

[VernonDozier]

>> I do not know how to create a linked list by loading data from an input file.
>> And, well, I quoted him, so I obviously meant the code he posted that reads it from the file and will, I guess, load it into the list.

It's not obvious at all that you were quoting him. What is obvious is that if you were quoting him and thought that his code had anything to do with a linked list, then you don't understand linked lists at all, so you are clearly in that category. His code dealt with how to read from a file. So as mentioned, don't worry about the file for now. Now, do you know how to set up a SINGLE linked list (i.e. as opposed to a DOUBLE linked list?) If not, don't worry about the double linked lists. Learn about single linked lists. It comes down to this. We have no idea what you're really stuck on from your post. We could completely waste our time writing a guide to how to write a double linked list and find that you knew all of it and just didn't know how to read an integer from a file.

Here's a very rough template to get you started...

#ifndef NULL
#define NULL 0
#endif

struct node 
{
  int data;
  node *next;
  node *prev;
};


int main()
{
    node* root = NULL;
    node* tail = NULL;
    node* aNode = new node;
    aNode->data = 5;
    aNode->prev = NULL;
    aNode->next = NULL;
    root = aNode;
    tail = aNode;
    aNode = new node;
    aNode->data = 7;
    aNode->prev = root;
    root->next = aNode;
    aNode->next = NULL;
    tail = aNode;

    // you now have a doubly linked list with two nodes: 5->7

    // more code here

    return 0;
}

So does this look familiar? Do you know what this code does? We have no idea what your knowledge is and where exactly you are stuck. You have to tell us.

[doug65536]

Sounds an awful lot like he wants us to do his homework assignment for him.
Sometimes I feel tempted to post a really sophisticated answer with templates and policy classes and inheritance so it is perfectly clear to the teacher that there's no way he wrote it.

[VernonDozier]

>> Sounds an awful lot like he wants us to do his homework assignment for him.

Sure does.

>> Sometimes I feel tempted to post a really sophisticated answer with templates and policy classes and inheritance so it is perfectly clear to the teacher that there's no way he wrote it.

The temptation is understandable, but keep in mind that someone other than the OP might come along with a similar problem and find this thread and look at that sophisticated answer and think that's a REAL answer. This second person could be a newbie and have a better attitude and try to make sense of a solution that (deliberately on your part) doesn't make sense, yet the newbie, being a newbie, wouldn't know that. End result is Daniweb gets cluttered up with low-quality answers and the person who didn't deserve to have their head messed with has their head messed with.

But again, I do understand the temptation and I'm sure I've done it at least once.

[EskayJoe]

Long back I had written this complete program.... posting here...for your quesry u may like to see the save() and the loadlist() function which saves the list in memory to a file and also reads the data in a text file and populates a linked list in memory... hope that is what u look for

#include <cstdlib>
#include <iostream>
#include<fstream>
#include<conio.h>
#include<process.h>
#include <stdlib.h>

using namespace std;

typedef struct node
{
	int data;   // stores the node data
	node *next,*prev;// 2 ptrs(ptr vars),will have mem add,holding node type
}NODE;

// GLOBAL VARS

	NODE *first,*last;//  Global ptrs,will have mem add,holding
											// node type
	long nodecount=0;//global var to keep count of nodes created

// FUNCTION PROTOTYPES

	void addathead(NODE*);
	void addattail(NODE*);
	void deletenode(NODE*);
	void addafter(NODE*,NODE*);
	void addbefore(NODE*,NODE*);
	NODE* search(int);
	void deleteall();
	void display();
	int inputdata();
	NODE* create();//create a blank node
	NODE* create(int);//create a populated node,with the int passed
	void deletelast();
	void save();
	void loadlist();//create a list as per the data in a file

int main(int argc, char *argv[])
{

	first=last=NULL;// initing ptrs to NULL
	while(1) // infinite loop
	{
		system("cls");
		char choice;
		cout<<"\n\n\t\t\tDOUBLE LINK LIST MENU";
		cout<<  "\n\t\t\t=====================";
		cout<<  "\n\t\t\t1. Add a Record at Head";
		cout<<  "\n\t\t\t2. Add a Record at Tail";
		cout<<  "\n\t\t\t3. Add a Record by Search after a Node";
		cout<<  "\n\t\t\t4  Add a Record by Search before a Node";
		cout<<  "\n\t\t\t5. Get Record Count";
		cout<<  "\n\t\t\t6. Delete Selected Record";
		cout<<  "\n\t\t\t7. Display Records";
		cout<<  "\n\t\t\t8. Delete All records";
		cout<<  "\n\t\t\t9. Delete Last record";
		cout<<  "\n\t\t\ts. Save list to file";
		cout<<  "\n\t\t\tr. Load a list";
		cout<<  "\n\t\tPress Q to quit anytime";

		cout<<  "\n\t\tPlease Enter Choice (1 - 9)";choice=getche();
		switch(choice)
		{
			case '1':NODE *temp;
						int num;
						num=inputdata();
						temp=create(num);
						addathead(temp);temp=NULL;break;
			case '2':
						num=inputdata();
						temp=create(num);
						addattail(temp);temp=NULL;break;
			case '3':NODE *newnode,*addnodeafter;
						num=inputdata();
						newnode=create(num);
						cout<<"\n\n\t\tEnter data after which to add node :";cin>>num;
						addnodeafter=search(num);
						addafter(addnodeafter,newnode);
						newnode=addnodeafter=NULL;
						break;
			case '4':
						NODE *addnodebefore;
						num=inputdata();
						newnode=create(num);
						cout<<"\n\n\t\tEnter data before which to add node :";cin>>num;
						addnodebefore=search(num);
						addbefore(addnodebefore,newnode);
						newnode=addnodebefore=NULL;
						break;
			case '5':cout<<"\n\n\t\tTotal "<<nodecount<<" Records,Press a key to continue ...";
						getch();break;
			case '6':cout<<"\n\n\t\tEnter data for  which to delete node :";cin>>num;
						temp=search(num);
						deletenode(temp);temp=NULL;break;
			case '7':display();break;
			case '8':deleteall();break;
			case '9':deletelast();break;
			case 's':save();break;
			case 'r':loadlist();break;
			case 'q':deleteall();exit(0);break;
			case 'Q':deleteall();exit(0);break;

			default	: {cout<<"\n\n\t\tInvalid Choice ! Press a key to continue ...";
						getch();}
		}
	}
  system("PAUSE");
  return EXIT_SUCCESS;
}

//************************************************************************
NODE* create(int num)  // function returns a pointer(add) of NODE type(add of new node)
						// null if node not created
						//function is passed the value with which node to be populated
{
	NODE *temp;
	temp=new NODE;
	if(temp)  // Mem allocated sucessfully,ie temp not NULL
	{

		temp->data=num;
		temp->next=NULL;//new node doesnt pt anywhere yet,till anothernode created
		temp->prev=NULL;
		return temp;
	}
	else
	{
		cout<<"\n\n\t\tOut of memory ! Press a key to continue ...";getch();
		return NULL;
	}
}

NODE* create()  // function returns a pointer(add) of NODE type(add of new node)
						// null if node not created,node data made=0
{
	NODE *temp;
	temp=new NODE;
	if(temp)  // Mem allocated sucessfully,ie temp not NULL
	{

		temp->data=0; //no data passed ,by default init to zero
		temp->next=NULL;//new node doesnt pt anywhere yet,till anothernode created
		temp->prev=NULL;
		return temp;
	}
	else
	{
		cout<<"\n\n\t\tOut of memory ! Press a key to continue ... ";getch();
		return NULL;
	}
}

int inputdata() //Function inputs data from user and returns that data
{
	int num;
	cout<<"\n\n\n\t\tEnter the integer data to add to list : ";cin>>num;
	return num;
}

void addathead(NODE *temp)// this function is passed pointer(an add of type NODE)
								  //and it links that node at the beg of list
{
	if(temp)//add passed is not NULLL
	{
		if(first==NULL)//node being linked is the first node in the list
		{
			first=last=temp;
		}
		else
		{
			temp->next=first;
			first->prev=temp;
			first=temp;

		}
    nodecount++;
    cout<<"\n\n\t\tAdded data to list. Press a key to continue ...";getch();

	}else
	{
	    cout<<"\n\n\t\tOut of Memory error. Node could not be added ! Press a key to continue ...";getch();
	}

}

void addattail(NODE *temp)// this function is passed pointer(an add of type NODE)
								  //and it links that node at the end of list
{
	if(temp)//add passed is not NULLL
	{
		if(first==NULL)//node being linked is the first node
		{
			first=last=temp;
		}
		else
		{
			temp->prev=last;
			last->next=temp;
			last=temp;
		}
	nodecount++;
    cout<<"\n\n\t\tAdded data to list. Press a key to continue ...";getch();
	}

	else
	{
	    cout<<"\n\n\t\tOut of Memory error. Node could not be added ! Press a key to continue ...";getch();
	}
}

NODE* search(int searchdata)//returns pointer to (add of )node with givendata
									 //returns NULL for no match/no node exists
{
	NODE *temp=first;
	if(temp) //if first node exists
	{
		while(temp)// runs untill temp becomes NULL
		{
			if (temp->data==searchdata)
			{
				return temp; // return the add of node where match found
			}
			else
			{
				temp=temp->next;// go to next node
			}
		}
		cout<<"\n\n\t\t Data not Found ! Press a key to continue ... to continue...";getch();
		return temp ; // will return NULL at the end of last node
	}
	else
	{
		cout<<"\n\n\t\tNo Node Exists ! Press a key to continue ...";getch();
		return NULL;
	}
}

void addafter(NODE *nodetoaddafter,NODE *newnod)
	//function is passed a ptr to a NODE(add of),the node after which to add
	//node(nodetoaddafter),and the add of the node to be
	//added(newnod)
{
	if(nodetoaddafter)// NULL is not passed as the node to add after
	{
		NODE *temp;
		temp=nodetoaddafter;
		if(nodetoaddafter!=last)//node after which to add is not the last node
		{
			newnod->prev=nodetoaddafter;
			newnod->next=nodetoaddafter->next;
			temp->next=newnod;
		}
		else
		{
			newnod->prev=nodetoaddafter;
			newnod->next=nodetoaddafter->next;
			temp->next=newnod;
			last=newnod;
		}
		nodecount++;
		cout<<"\n\n\t\tAdded data to list. Press a key to continue ...";getch();
	}
	else
	{
	    cout<<"\n\n\t\tOut of Memory error. Node could not be added ! Press a key to continue ...";getch();
	}

}

void addbefore(NODE *nodetoaddbefore,NODE* newnode)
{
	//fn is passed a ptr to a NODE(add of)	//,the node before which to add
	//node(nodetoaddbefore),and the add of the node to be
	//added(newnode)
	if(nodetoaddbefore)// NULL is not passed as the node to add before
	{
		NODE *temp=nodetoaddbefore;
		if(nodetoaddbefore!=first)//node before which to add is not the first node
		{
			temp->prev->next=newnode;
			newnode->next=temp;
			newnode->prev=temp->prev;
			temp->prev=newnode;
		}
		else
		{
			temp->prev->next=newnode;
			newnode->next=temp;
			newnode->prev=temp->prev;
			temp->prev=newnode;
			first=newnode;
		}
		nodecount++;
		cout<<"\n\n\t\tAdded data to list. Press a key to continue ...";getch();
	}
	else
	{
	    cout<<"\n\n\t\tOut of Memory error. Node could not be added ! Press a key to continue ...";getch();
	}

}

void deletenode(NODE *nodetobedeleted)
	//the add of node to be deleted is passed
{
	if(nodetobedeleted)//add passed is not NULL
	{
		if(nodetobedeleted==first && nodetobedeleted==last)//only node
		{
			delete nodetobedeleted;
			first=last=NULL;

		}
		else if(nodetobedeleted==first)
		{
			NODE *temp=first;
			first=first->next;
			delete temp;
			first->prev=NULL;
		}
		else if(nodetobedeleted==last)
		{
			NODE *temp=last;
			last=last->prev;//last changes
			last->next=NULL;
			delete temp;temp=NULL;
		}
		else // none of above,node in between
		{
			nodetobedeleted->prev->next=nodetobedeleted->next;
			nodetobedeleted->next->prev=nodetobedeleted->prev;
			delete nodetobedeleted;nodetobedeleted=NULL;
		}
		nodecount--;
        cout<<"\n\n\t\tDeleted ! Press a key to continue ...";getch();
	}
	else
	{
	    cout<<"\n\t\tcould not delete,Press a key to continue ... !";getch();
	}

}
void display() //displays all the nodes in the list
{
	NODE *temp;
	temp=first;
	cout<<"\n\n\n";
	while(temp)
	{
		cout<<endl<<"\t\t\t"<<temp->data;
		temp=temp->next;
	}
	cout<<"\n\n\t\t "<<nodecount<<" records displayed ,Press a key to continue .....";getch();
}

void deleteall()//deletes all the nodes in the list,sets global ptrs to
					  // to NULL
{
	int count=nodecount;
	cout<<"\n\n\t\t"<<count<<" existing records will be deleted ! (y/n) " ;char choice=getch();
	if((choice=='Y'|| choice=='y'))
	{

        NODE *temp;
        temp=first;

        while(temp)
        {
            first=first->next;
            delete temp;nodecount--;
            temp=first;
        }
        first=last=NULL;
        nodecount=0;
        cout<<"\n\n\t\t"<<count<<" records deleted. Press a key to continue ..." ;getch();
	}

}

void deletelast() // deletes the last node
{
	NODE *t=last;
	deletenode(t);
}

void save() // This saves the list in memory to a file joshi,bin in the
				//current directory of the executable.it is to be noted that
				//at  the end of file NULL or 0 is stored,by default
				//this had created a bug while trying to read the file
				// see loadlist()
{
	fstream listfile;
	listfile.open("list.dls",ios::out) ;
	NODE *temp;
	temp=first;
	while(temp!=NULL)
	{
		listfile.write((char*)temp,sizeof(int));
		temp=temp->next;
	}
    listfile.close();
	cout<<"\n\n\n\t\tLink list has been saved in file list.dls in current folder.";
	cout<<"\n\n\t\tPress a key to continue ... ";getch();

}
void loadlist()
{
    if(!(first==NULL)) //list not empty in memory
    {
        deleteall();//delete existing list in memory
    }

	fstream listfile;
	listfile.open("list.dls",ios::in) ;
	listfile.seekg(0);//set file ptr at the beg of file

    while(!listfile.eof())
    {
        NODE *temp=create();//create a blank node
        if(temp) //memory allocation successful
        {
            listfile.read((char*)temp,sizeof(temp->data));// read the start data to temp

            // now,if the file was empty it still has null at the end
            // so 0 is read
            if (temp->data==NULL)// if file is empty or we are at end;
            {
                cout<<"\n\n\t\tFile is empty OR End of File reached ...";
                cout<<"\n\n\t\t Press a key to continue ... !";getch();
                delete temp;// no need to load a list now
            }
            else
            {
                //valid data read

                cout<<"\n\n\t\tdata read from file :"<<temp->data;
                addattail(temp); //addattail caters to the node being added to an empty list

            }
        }
        else
        {
            cout<<"\nUnable to load list,Out of memory ! Press a key to continue ...";getch();
        }

    }
    listfile.close();

}