Thread: two-way cycled list

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    5

    two-way cycled list

    i'm trying to creat a two-wat cycled list. I've created Find Function and Delete Function but i think i have a problem in InsertElement Function and i can't find it.
    Code:
    struct List
    {
    
    struct node
        {
            int data;
            struct node *next;
            struct node *prev;
    
        };
    
    node *head, *current, *a, *b;
    
    List()
    	{
    		head = NULL;
    		current = NULL;
    	}
    
    int insertElem(int x)
        {
             node *newNode = (node*)malloc(sizeof(node));
                if(!newNode)
                    {
                        return 1;
                    }
            newNode->data=x;
    
    		if(head==NULL)
    		{
                newNode->next=head;
    			newNode->prev=head;
    			head = newNode;
    			return 0;
    		}
    		else
    		{
    		    current=head;
    		    while(current->next==head)
    		    {
    
                    current->next = current;
    
                }
    
                current->next=newNode;
                newNode->next = head;
                head->prev=newNode;
                return 0;
    
    
    		}
    
    
        }
    ......
    };

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Please fix your indentation next time you post code so people can actually read and understand it.

    Code:
    node *head, *current, *a, *b;
    Global Variables Are Bad

    Code:
    		if(head==NULL)
    		{
                newNode->next=head;
    			newNode->prev=head;
    			head = newNode;
    			return 0;
    		}
    When you assign the next and prev elements, head is NULL, so you don't actually have a circular list here. That might throw off your subsequent inserts. You probably want head = newNode as the first line in this block.

    Code:
    		    current=head;
    		    while(current->next==head)
    		    {
    
                    current->next = current;
    
                }
    Your loop condition looks backwards. You want to keep while the next element doesn't point to the head of the list (i.e. while current isn't the last node in the list).

    Code:
                current->next=newNode;
                newNode->next = head;
                head->prev=newNode;
                return 0;
    You probably want to set newNode->prev to current here.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    5
    thank you. So now it looks like that, but it still dose't work (only for head it works):
    Code:
    int insertElem(int x)
        {
             node *newNode = (node*)malloc(sizeof(node));
                if(!newNode)
                    {
                        return 1;
                    }
            newNode->data=x;
    
    		if(head==NULL)
    		{
    		    head = newNode;
                head->next=head;
    			head->prev=head;
                return 0;
    		}
    		else
    		{
    		    current=head;
    		    while(current->next!=head)
    		    {
    
                    current->next = current;
    
                }
    
                current->next=newNode;
                newNode->next = head;
                newNode->prev=current;
                head->prev=newNode;
                return 0;
    
    
    		}
    
    
        }
    int findElem(int x)
        {
            current=head;
            if(current==NULL)
            {
                return 1;
            }
            else{
                while(current->next!=head)
                {
                    if(current->data==x)
                    {
                        return 3;
                    }
                    else
                    {
                        current=current->next;
                    }
    
                }
                return 1;
                }
        }
    p.s.
    have to add standard colors to my code, here?

  4. #4
    Registered User
    Join Date
    Mar 2011
    Posts
    5
    ok, i did it in a diffrent way
    Code:
    int insertElem(int x)
        {
            node *newNode = (node*)malloc(sizeof(node));
                if(!newNode)
                    {
                        return -1;
                    }
            newNode->data=x;
    
    		if(head==NULL)
    		{
                head=newNode;
                head->next=head;
    			head->prev=head;
    
                return 0;
    		}
    
    		if(head->next==head)
    		{
    		    head->next=newNode;
    		    head->prev=newNode;
    		    newNode->prev=head;
    		    newNode->next=head;
                return 1;
    		}
    
    		else
    		{
    		    current=head->next;
                head->next=newNode;
                newNode->next=current;
                newNode->prev=head;
                current->prev=newNode;
                return 2;
    		}
    
    
        }
    every function works, but now it eats up the last node (the one, user puts as second one)

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    No, no colors are needed for the code, just code tags and proper indenting. Your indentation problems on this page stem from the fact that half your code uses tabs for indentation and the other half is using spaces. Pick one and stick with it.

    I worked up a small test program around your insert code. Your insert actually inserts all the elements, and nothing is lost. I suspect your print routine isn't quite right. If I insert 1, 2, 3, 4 into your list however, I get the following when I print: 1, 4, 3, 2. Basically, your first node goes in as the head, then each node goes in the second position and pushes the rest towards the back. Is that the behavior you want/expect?

    That also makes me think your print routine is stopping one short of the last element. Post your print routine so we can help you fix it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. c program that accepts and executes commands?
    By Cimposter in forum C Programming
    Replies: 3
    Last Post: 09-30-2009, 02:58 PM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 05:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM