#1
  1. Cast down
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Location
    Sweden
    Posts
    321
    Rep Power
    11

    Single LinkedList, adding element to the middle of a list


    I am writing a default/basic LinkedList, I made a function to add a element to the head (the front) and the tail (end) of the list, but how do I add a element in N position, like "3rd in the list" or "7th in the list"? right now I have this function, what it does is start off at head, and loop N times and add the element.. but If the user puts 0, I want the element to become the head of the list, and if the user enters a higher number than the list, then to add it to the tail (I think I have my LinkedList backwards, with 0 being head and all)

    Code:
    int AddN(char* txt, int N)
    {
    	//Will add this to position N, starts from 0 
    	
    	if(N==0) 
    	{	
    		AddHead(txt); //This function adds a new head 
    		return 1; 
    	}
    
    	if(N>=(ListCount()-1)) 
    	{
    		printf("%d\n",N); 
    		AddTail(txt); //adds a new tail 
    		return 1; 
    	}
    
    	CURRENT=HEAD; 
    	for(x=0;x<N;x++)
    	{
    		if(CURRENT->next==NULL)
    			break; 
                           CURRENT=CURRENT->next; 
    	}
    	//Now CURRENT is N... 
    
    	NEW=(LINK)malloc(sizeof(PLAYER)); 
    	if(!NEW)
    		return 0; 
    
    	NEW->next=CURRENT->next;
    	CURRENT->next=NEW; 
    	strcpy(NEW->name,txt); 
    	return 1; 
    }
    I am coding in C, return 1 means sucess, I just want it like AddN("whatever",3) would add "whatever" as 3rd in the list (4th because it's 0 based) and AddN("Whatever",0) make it the front/end of the list.
    Last edited by movEAX_444; July 15th, 2003 at 05:49 PM.
  2. #2
  3. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
  4. #3
  5. Cast down
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Location
    Sweden
    Posts
    321
    Rep Power
    11
    Kind of confusing because It's not C/C++ and It uses classes. But I'll read through it.
  6. #4
  7. Doggie
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2003
    Location
    Seattle, WA
    Posts
    751
    Rep Power
    12
    First you move to where you want the item added. Usually just follow your links x many times. (cur=cur->next)

    Then:
    item newlink=new item;
    newlink->next=cur->next;
    cur->next=newlink;

    This works even if cur->next is NULL, but not if cur is NULL (empty list)

    Does that answer your question? If you're trying to jump instantly to a section in a linked list, then that's a whole 'nother can of worms, and not one I'd try to describe here.
  8. #5
  9. Cast down
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Location
    Sweden
    Posts
    321
    Rep Power
    11
    that's what I have, look:
    Code:
    	CURRENT=HEAD; 
    	for(x=0;x<N;++x)
    	{
    		if(CURRENT->next==NULL)
    			break; 
    		CURRENT=CURRENT->next; 
    	}
    	//Now CURRENT is N... 
    
    	NEW=(LINK)malloc(sizeof(PLAYER)); 
    	if(!NEW)
    		return 0; 
    
    	NEW->next=CURRENT->next;
    	CURRENT->next=NEW; 
    	strcpy(NEW->name,txt);
    problem is, it's 1 above, so this is the output right now if I do AddN("test~~~",1):

    0) head
    1) random
    2) test~~~~~
    3) tail

    when test~~~~ should appear as #1)
    If I do AddN("test~~~",0), then test is put as #1, but what if I want test to be #0)?


    If I do, x=1 instead of x=0, then the numebrs are right, AddN("what",1) will put it as #1, but 0 will leave it as #1 too... not as #0
    Last edited by movEAX_444; July 15th, 2003 at 08:29 PM.
  10. #6
  11. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    that's b/c ur inserting it after current. you assign current->next =NEW, effectively placing NEW after the (nth) element. so either have your for loop quit one element b4 the one you want to replace.
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Posts
    21
    Rep Power
    0
    Code:
    struct LINK
    {
        int  data;
        struct LINK *next;
    };
    
    struct LINK *root = 0;
    
    int main()
    {
        int i;
    
        addbeg(10);
    
        for(i=0; i<10; i++)
            addlast(10+i);
    
        addmid(50, 3);
        addmid(60, 7);
        
        display();
     
        return 0;
    }
    
    addbeg(int number)
    {
        struct LINK *new;
    
        if(root==0)
        {
             root = (struct LINK *)malloc(sizeof(struct LINK));
             root->data = number;
             root->next = 0;
        }
        else
        {
            new = (struct LINK*)malloc(sizeof(struct LINK));
            new->data = number;
            new->next = root;
            root = new;
        }
        return;
    }
    
    addlast(int number)
    {
        struct LINK *trace, *new;
        trace = root;
        
        if(trace==0)
            printf("\nLink is empty.");
        else
        {
            while(trace->next != 0)
                  trace = trace->next;
    
            new = (struct  LINK *)malloc(sizeof(struct LINK));
            new->data = number;
            new->next = 0;
            trace->next = new;
        }
        return;
    }
    
    addmid(int number, int pos)
    {
        int i;
        struct LINK *trace, *new;
      
        trace = root;
    
        if(trace==0)
             printf("\nLink is not created.");
        else
        {
             for(i=1; i<pos; i++)
             {
                  trace = trace->next;
                  if(trace==0)
                        break;
             }
             if(i < pos-1)
                  printf("\nLinks has less than %d items", pos-1);
             else
             {
                  new = (struct  LINK *)malloc(sizeof(struct LINK));
                  new->data = number;
    
                  if(trace->next==0)
                        new->next=0;
                  else
                        new->next = trace->next;
    
                  trace->next = new;
             }         
        }
        return 0;
    }
    
    display()
    {
         struct LINK *trace;
         trace = root;
    
         while(trace != 0)
         {
              printf("\n%d", trace->data);
              trace = trace->next;
         }
         return 0;
    }

IMN logo majestic logo threadwatch logo seochat tools logo