Linked lists

Discussion in 'C++' started by coolio2006, Aug 25, 2006.

  1. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    I understand that. I know it's just 2 nodes behind, but in terms of making the code go 2 nodes behind, that's a little tricky. Technically, the user needs to enter the length of the node and the size of the longlink - so it could be 20 nodes and longlink is every 6.
     
  2. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    Here is my code to make it better to understand (Hopefully)

    Code:
    node *newnode = current;
    node *temp = current; 
    node *start = current;
    int number = 0;
    int num = 0; 
    for (int i = 1; i < length; i++) // this function is just ensuring the node before the deleted node points to 2 nodes in front 
    {
    temp = temp -> shortlink;
    }
    
    
    
    if (newnode -> num == x)
    {
    number = current -> longlink -> num; // here as you can see i want to store the longlink value of the deleted node into the variable number
    current = current -> shortlink;
    temp -> shortlink = start -> shortlink;
    delete newnode;
    length--;
    }
    
    
    else
    
    while (newnode -> shortlink -> num != start -> num)
    {
    if (newnode -> shortlink -> num == x)
    {
    temp = newnode -> shortlink; 
    number = temp -> longlink -> num; // here as you can see i want to store the longlink value of the deleted node into the variable number
    newnode -> shortlink = newnode -> shortlink -> shortlink;
    delete temp;
    length--;
    }
    newnode = newnode -> shortlink;
    }
    
    
    if (newnode -> shortlink -> shortlink -> num == length && newnode -> shortlink -> num == x)
    {
    delete newnode -> shortlink -> shortlink;
    newnode -> shortlink = start;
    length--;
    }
    
    
    
    
    
    
    for (int z = 1; z < length; z++) // this function goes through each node to see if any of the long links are pointing to the deleted node
    {
    // if i put a cout statement exactly here to cout number - it recognises the number variable fine
    if (longlinker -> longlink -> num == x) // if i've found it // once it looks into this if statement - number isn't recognised - why?
    {
    longlinker -> longlink -> num = number; // then i want to update the longlink of this which stores number 
    }
    else
    {
    longlinker = longlinker -> shortlink; // otherwise keep iterating
    }
    }
     
  3. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    I'm really stuck now :( some of the long links of the nodes that were referncing to the delete node now have ridiculous long link numbers :( (like 14155566)
     
  4. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    The problem i got now is the following, and i'd REALLY be grateful if someone could assist me with this. Lets say i have 6 nodes and the long link is 3, then 1 points to 2 and 4, 2 points to 3 and 5, 3 points to 4 and 6 etc .....
    When i delete node 1 and 2, then nodes 4 and 5 are longlinking back to 0 (for some reason). Can someone help me please? Code is here:

    Code:
    node *newnode = current;
    node *temp = current; 
    node *start = current;
    node *longlinker = current;
    int number = 0; 
    
    
    for (int i = 1; i < length; i++)
          {
          temp = temp -> shortlink;
          }
    
    if (newnode -> num == x)
    {
    start = start -> shortlink;
    number = current -> longlink -> num;
    current = current -> shortlink;
    temp -> shortlink = start; 
    delete newnode;
    length--;
    cout << "longlink for 1 is"  << number << endl;
    }
    else
    
    for (int p = 1 ; p < length; p++)
    {
    if (newnode -> shortlink -> num == x)
    {
    		temp = newnode -> shortlink;
    		number = temp -> longlink -> num;
    		newnode -> shortlink = newnode -> shortlink -> shortlink;
    		delete temp;
    		length--;
    }
    
    else 
    newnode = newnode -> shortlink;
    }
     
    Last edited: Aug 27, 2006
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Still I dont get what problem you are facing. Its just the delete of a node from a link list then I have already given a code snippet to achieve the same and you can customize it to add extra information like short link and long link. Mine is just a simple where only one pointer exists and thats short link according to your problem and that is the next node.
     
  6. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    Your code works fine (the sample), but that's only because each node is only linked to it's next node. My scenario is a little more complicated. Lets take this for instance, a list of 6 nodes and longlinks of 3: so the design looks like the following:

    1 ----> 2( shortlink) && 1 ----> 4(longlink)
    2 ----> 3( shortlink) && 1 ----> 5(longlink)
    3 ----> 4( shortlink) && 1 ----> 6(longlink)
    4 ----> 5( shortlink) && 1 ----> 1(longlink)
    5 ----> 6( shortlink) && 1 ----> 2(longlink)
    6 ----> 1( shortlink) && 1 ----> 3(longlink)

    Shortlinks are working fine. Now in that scenario, if i deleted node 1, that means nothing shall point to it . We must oberve though node 1 has a shortlink to 1 and a longlink to 4. Anyway, as you can see there, node 4 has a longlink to node 1, but node 1 is deleted, therefore this is wrong. So what i need to be able to do is, node 4 must point to the long link of the delete nodes long list. After deleting node 1, it should now look like




    2 ----> 3( shortlink) && 1 ----> 5(longlink)
    3 ----> 4( shortlink) && 1 ----> 6(longlink)
    4 ----> 5( shortlink) && 1 ----> 4(longlink) ( 4's longlink must point to itself because 1's longlink was 4
    5 ----> 6( shortlink) && 1 ----> 2(longlink)
    6 ----> 2( shortlink) && 1 ----> 3(longlink) (notice 6's shortlink is now 2 - this works fine).


    My output is giving me this:

    2 ----> 3( shortlink) && 1 ----> 5(longlink)
    3 ----> 4( shortlink) && 1 ----> 6(longlink)
    4 ----> 5( shortlink) && 1 ----> 0(longlink) (this should not be pointing to 0, it should be 4)
    5 ----> 6( shortlink) && 1 ----> 2(longlink)
    6 ----> 2( shortlink) && 1 ----> 3(longlink)

    Hopefully that clarifies my situation atm, and i'd really be grateful for some assistance.
     
  7. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    Ok so it's all deleting the nodes fine and updating the links, except when i go to remove the 1st node - it has a problem. Could someone please examine what i'm doing wrong.

    Code:
    void ring::remove(int x)
    {
    
    node *newnode = current;
    node *temp = current; 
    node *start = current;
    node *longlinker = NULL;
    node *shortdata = current; // this references to the first deleted node and will need it for testing longlink functionality
    int number = 0; 
    
    
    for (int i = 1; i < length; i++) // this for loop is used for creating the short link - for .e.g if node 4 is deleted, then node 3 points to 5 and not 3
          {
          temp = temp -> shortlink;
          }
    
    if (newnode -> num == x)
    {
    start = start -> shortlink;
    //number = current -> num;
    current = current -> shortlink;
    //number = temp -> num; 
    temp = start;
    newnode = start;
    length--;
    }
    else
    
    
    for (int p = 1 ; p < length; p++)
    {
    if (newnode -> shortlink -> num == x)
    	{
    		temp = newnode -> shortlink;
     		number = temp -> shortlink -> num;
            	newnode -> shortlink = newnode -> shortlink -> shortlink;
                longlinker = newnode -> shortlink;
    		//delete newnode;		
    		length--;
    	}
    else 
    newnode = newnode -> shortlink;
    }
    
    for (int y = 1; y <= length; y++)
    {
    if (longlinker -> longlink -> num == temp -> num)
    {
    longlinker -> longlink -> num = temp -> longlink -> num;
    }
    else
    longlinker = longlinker -> shortlink;
    }
    
    }
     
  8. coolio2006

    coolio2006 New Member

    Joined:
    Aug 25, 2006
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
  9. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    This sounds quite an interesting Linked list and so thought of programming it. Here is the code for you to see.

    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>
    #include <string.h>
    
    /*
     * Program for single linked list which inserts / deletes
     * data into linked list. The structure of linked list is 
     * complex. Instead of just having a link to the shortlink 
     * pointer it even stores a refernce to other link
     *
     *
     */
    
    // Structure templates
    struct list
    {
    	int no;
    	struct list *shortlink;
    	struct list *longlink;
    };
    typedef struct list node;
    
    node *head = NULL;
    
    void init(node*);
    void InsertNode();
    void DeleteNode();
    void DisplayList();
    
    void main()
    {
    	char ch = 'n';
    	int opt;
    	do
    	{
    		printf("\nEnter your option\n");
    		printf("\n1. Insert a node\n");
    		printf("\n2. Delete a particular node\n");
    		printf("\n3. Display all the nodes\n");
    		printf("\n4. Exit the application\n");
    		scanf("%d",&opt);
    		switch(opt)
    		{
    		case 1:
    			InsertNode();
    			DisplayList();
    			break;
    		case 2:
    			DeleteNode();
    			DisplayList();
    			break;
    		case 3:
    			DisplayList();
    			break;
    		case 4:
    			ch = 'y';
    			break;
    		}
    	}while(ch != 'y');
    	printf("\nDone by \"SHABBIR\"\n");
    	getch();
    }
    
    void init(node *current)
    {
    	printf("\nEnter number\n");
    	scanf("%d",&current->no);
    	current->shortlink = NULL;
    	current->longlink = NULL;
    }
    
    void InsertNode()
    {
    	node *newnode;
    	
    	newnode=(node*)malloc(sizeof(node));
    
    	init(newnode);
    
    	if(head == NULL)
    	{
    		head = newnode;
    	}
    	else
    	{
    		node *current = head;
    		node *longlinkedNode = NULL;
    
    		// Move to the end of the link list
    		for(int i = 1; current->shortlink!=NULL ; i++)
    		{
    			if(i % 2 == 0)
    			{
    				longlinkedNode = current;
    			}
    			current=current->shortlink;
    		}
    
    		if(current->shortlink==NULL)
    		{
    			newnode->shortlink = current->shortlink;
    			newnode->longlink = longlinkedNode;
    
    			current->shortlink = newnode;
    		}
    	}
    }
    
    void DeleteNode()
    {
    	node* current = head;
    	int rno;
    	node *newnode,*temp;
    
    	printf("\nEnter the number whose node you want to delete\n");
    	scanf("%d",&rno);
    	newnode=current;
    
    	if(current->no==rno)
    	{
    		// Deleting the first node
    		newnode=current;
    		current=current->shortlink;
    		free(newnode);
    		head = current;
    		return;
    	}
    	else
    	{
    		node* longlinkedNode = NULL;
    
    		for(int i = 1; newnode->shortlink->shortlink!=NULL; i++)
    		{
    			if(i % 2 == 0)
    			{
    				longlinkedNode = current;
    			}			// Checking condition for deletion of
    			// all nodes except first and last node
    			if(newnode->shortlink->no==rno)
    			{
    				temp=newnode->shortlink;
    				newnode->shortlink=newnode->shortlink->shortlink;
    				longlinkedNode->longlink = temp->longlink;
    				free(temp);
    				head = current;
    				return;
    			}
    			newnode=newnode->shortlink;
    		}
    		if(newnode->shortlink->shortlink==NULL && newnode->shortlink->no==rno)
    		{
    			// Checking condition for deletion of last node
    			free(newnode->shortlink);
    			longlinkedNode->longlink = newnode->shortlink->longlink;
    			newnode->shortlink=NULL;
    			head = current;
    			return;
    		}
    	}
    }
    
    void DisplayList()
    {
    	node* current = head;
    
    	while(current!=NULL)
    	{
    		printf("\n %d ",current->no);
    		current=current->shortlink;
    	}
    }
    
    I dont think it was that different a code from what I have posted.
     
  10. anoop4real

    anoop4real New Member

    Joined:
    Dec 18, 2006
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    Hell o I am new member of this site. I am having some problems with linked lists. I want the solution for the problem described below can you help me with the code .
    We have to open a new text file and do these operations in that
    for eg:Name and mark of a student
    Add Node .
    Delete Node -
    Insert Node - Same as Add Node, but takes an additional parameter of the location in which this new node is to be inserted
    Sort Nodes -
    Display Nodes - Should display the whole list in Name1 (mark), Name 2 (mark)... format.
    Save Nodes - This will output the curent list and save it into the same mark.txt file
    Exit - Exits the Application.
    I need it on Wednesday
     
  11. coderzone

    coderzone Super Moderator

    Joined:
    Jul 25, 2004
    Messages:
    736
    Likes Received:
    38
    Trophy Points:
    28
    Try putting your query in a seperate thread on the forum.
     
  12. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Exactly.
     
  13. shahzadmasih

    shahzadmasih New Member

    Joined:
    Dec 19, 2006
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    Hi, This post is very informative, however I would like some specific information. If someone can help me then please send me a private message. Best Regards,
     
  14. shahzadmasih

    shahzadmasih New Member

    Joined:
    Dec 19, 2006
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    Confine links to signatures only
     
    Last edited by a moderator: Dec 19, 2006
  15. shahzadmasih

    shahzadmasih New Member

    Joined:
    Dec 19, 2006
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
  16. DaWei

    DaWei New Member

    Joined:
    Dec 6, 2006
    Messages:
    835
    Likes Received:
    5
    Trophy Points:
    0
    Occupation:
    Semi-retired EE
    Location:
    Texan now in Central NY
    Home Page:
    http://www.daweidesigns.com
    Nice monologue.
     
  17. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    shahzadmasih, Confine links to signatures only
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice