1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

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,293
    Likes Received:
    365
    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,293
    Likes Received:
    365
    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:
    734
    Likes Received:
    37
    Trophy Points:
    0
    Try putting your query in a seperate thread on the forum.
     
  12. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    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:
    Nice monologue.
     
  17. shabbir

    shabbir Administrator Staff Member

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

Share This Page