Thread: Linked List print out

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

    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 );
    	}
    }

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    Disturbed Boy gustavosserra's Avatar
    Join Date
    Apr 2003
    Posts
    244
    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?
    Nothing more to tell about me...
    Happy day =)

  3. #3
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    I don't think that should matter. Both L1 and L2 are seperate lists.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  4. #4
    Disturbed Boy gustavosserra's Avatar
    Join Date
    Apr 2003
    Posts
    244
    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!
    Nothing more to tell about me...
    Happy day =)

  5. #5
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    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?
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  6. #6
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    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

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  7. #7
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  2. Replies: 13
    Last Post: 05-08-2006, 11:14 AM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM