-
Linked List print out
hey all,
there I was, thinking I have linked list pretty much figured out, and here I am now; confused with a very simple problem (i think). Anyways, below is a code, where I am trying to create two seperate linked lists, abd later print them out. If I do just one, everything works fine, but when I do two, I get everything twice, basically instead of getting 0 1 2 3 4 I get 0 1 2 3 4 0 1 2 3 4.
any suggestions?
axon
Code:
#include <iostream>
using namespace std;
struct Node {
Node *pNext;
Node *pPrev;
int nData;
};
Node *pHead, *pTail;
void AppendNode( Node *pNode);
//appends node to end of list
void InsetNode(Node *pNode, Node *pAfter);
//insert node into the list after pAfter
void RemoveNode(Node *pNode);
//Remove specified node from list
void DeleteAllNodes();
//Delete the entire list
int main()
{
Node *L1;
Node *L2;
//add items to linked list
for ( int i = 0; i< 5; i++ ) {
L1 = new Node;
L1->nData = i;
AppendNode( L1 );
}
for ( i = 0; i< 5; i++ ) {
L2 = new Node;
L2->nData = i;
AppendNode( L2 );
}
//display all nodes
cout << "-----------==LIST 1==--------------" << endl << endl;
for ( L1 = pHead; L1 != NULL; L1 = L1->pNext ) {
cout << L1->nData << endl;
}
cout << "-----------==LIST 2==--------------" << endl << endl;
for ( L2 = pHead; L2 != NULL; L2 = L2->pNext ) {
cout << L2->nData << endl;
}
return 0;
}
//========================================
void AppendNode( Node *pNode)
{
if ( pHead == NULL ) {
pHead = pNode;
pNode->pPrev = NULL;
} else {
pTail->pNext = pNode;
pNode->pPrev = pTail;
}
pTail = pNode;
pNode->pNext = NULL;
}
//========================================
void InsetNode(Node *pNode, Node *pAfter)
{
pNode->pNext = pAfter->pNext;
pNode->pPrev = pAfter;
if ( pAfter->pNext != NULL ) {
pAfter->pNext->pPrev = pNode;
} else {
pTail = pNode;
}
pAfter->pNext = pNode;
}
//========================================
void RemoveNode(Node *pNode)
{
if ( pNode->pPrev == NULL ) {
pHead = pNode->pNext;
} else {
pNode->pPrev->pNext = pNode->pNext;
}
if ( pNode->pNext == NULL ) {
pTail = pNode->pPrev;
} else {
pNode->pNext->pPrev = pNode->pPrev;
}
}
//========================================
void DeleteAllNodes()
{
while ( pHead != NULL ) {
RemoveNode( pHead );
}
}
-
Code:
for ( L1 = pHead; L1 != NULL; L1 = L1->pNext ) {
cout << L1->nData << endl;
}
cout << "-----------==LIST 2==--------------" << endl << endl;
for ( L2 = pHead; L2 != NULL; L2 = L2->pNext ) {
cout << L2->nData << endl;
}
L1 and L2 begin with pHead, is this correct?? Shouldn´t be different?
-
I don't think that should matter. Both L1 and L2 are seperate lists.
-
But if I understood well your program, each linked list must have their own head node. To be more accurate, I see a linked list as a head node, and a some other nodes that follows.
My englosh is very poor, so I can not explain you better.You are constructing the 2 lists on the same head!
-
I see what he means...change your code to this:
Code:
#include <iostream>
using namespace std;
struct Node {
Node *pNext;
Node *pPrev;
int nData;
};
Node *pHead, *pTail;
void AppendNode( Node *pNode);
//appends node to end of list
void InsetNode(Node *pNode, Node *pAfter);
//insert node into the list after pAfter
void RemoveNode(Node *pNode);
//Remove specified node from list
void DeleteAllNodes();
//Delete the entire list
int main()
{
Node *L1;
Node *L2;
//add items to linked list
for ( int i = 0; i< 5; i++ ) {
L1 = new Node;
L1->nData = i;
AppendNode( L1 );
}
//display all nodes
cout << "-----------==LIST 1==--------------" << endl << endl;
for ( L1 = pHead; L1 != NULL; L1 = L1->pNext ) {
cout << L1->nData << endl;
}
DeleteAllNodes();
for (int i = 0; i< 5; i++ ) {
L2 = new Node;
L2->nData = i;
AppendNode( L2 );
}
cout << "-----------==LIST 2==--------------" << endl << endl;
for ( L2 = pHead; L2 != NULL; L2 = L2->pNext ) {
cout << L2->nData << endl;
}
int x;
cin>>x;
return 0;
}
//========================================
void AppendNode( Node *pNode)
{
if ( pHead == NULL ) {
pHead = pNode;
pNode->pPrev = NULL;
} else {
pTail->pNext = pNode;
pNode->pPrev = pTail;
}
pTail = pNode;
pNode->pNext = NULL;
}
//========================================
void InsetNode(Node *pNode, Node *pAfter)
{
pNode->pNext = pAfter->pNext;
pNode->pPrev = pAfter;
if ( pAfter->pNext != NULL ) {
pAfter->pNext->pPrev = pNode;
} else {
pTail = pNode;
}
pAfter->pNext = pNode;
}
//========================================
void RemoveNode(Node *pNode)
{
if ( pNode->pPrev == NULL ) {
pHead = pNode->pNext;
} else {
pNode->pPrev->pNext = pNode->pNext;
}
if ( pNode->pNext == NULL ) {
pTail = pNode->pPrev;
} else {
pNode->pNext->pPrev = pNode->pPrev;
}
}
//========================================
void DeleteAllNodes()
{
while ( pHead != NULL ) {
RemoveNode( pHead );
}
}
Maybe that makes it clearer? Also, are you ever deleteing your nodes that you allocated with the new operator?
-
Yes, that would work Jawib, but what I'm trying to do is to make a very simple linked list program, so I can practice link list manipulation with multiple lists. I want to do such functions as recursivelly adding two linked list together and such. So, I don't want to delete L1 before I initialize L2.
axon
-
The program works exactly as advertised. You create 'two' lists, which happen to be identical, and it prints them. The list is defined by its head and tail pointers. Everything in between is in the list. Now, you put everything in between the same head and same tail pointers. You have not created two lists, just one. L1 and L2, in your printing algorithm are synonyms for each other. They do exactly the same thing. The way your code is set up, you cannot have mutiple lists. There are two options to fix this:
1) Pass the head/tail pointers as parameters to your functions. That way you can have separate sets of head/tail pointers for each list.
2) Make the list a class (recommended). This way, each instance of the class would track its own resources, and keep track of its own head/tail pointers.