Linked List Move Method

This is a discussion on Linked List Move Method within the C++ Programming forums, part of the General Programming Boards category; Below I have attached 4 methods from my linked list class. 1) find 2)remove 3)retrieve 4) Insert. what I'm trying ...

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    2

    Linked List Move Method

    Below I have attached 4 methods from my linked list class.


    1) find 2)remove 3)retrieve 4) Insert.

    what I'm trying to do is write code that will let me MOVE the position of a node to another position in the linked list.

    Anyone got a clue??

    regards

    Tim


    Code:
    
    SeqItemType Sequence::retrieve(int index)
    {
    
    if ((index < 1) || (index > size())){
    // can't delete something that isn't there
    }
    ListNode *cur = find(index);
    return cur->item; 
    } 
    
    
    
    void Sequence::insert(int index, SeqItemType newItem)
    {
    
    if ((index < 1) || (index > (size()+1))){
    // if index is out of bounds don't do anything
    }
    else
    { 
    // otherwise create new node and place newItem in it
    ListNode *newPtr = new ListNode();
    
    // increment the size attribute
    length++;
    // store the data item in the new node
    newPtr->item = newItem;
    
    // if the index is 1, insert new node at beginning of list
    if (index == 1)
    { 
    newPtr->next = head;
    head = newPtr;
    }
    else
    { 
    ListNode *prev = find(index-1);
    newPtr->next = prev->next;
    prev->next = newPtr;
    
    }
    } 
    }
    
    
    void Sequence::remove(int index) 
    { 
    
    ListNode *cur;
    
    if ((index < 1) || (index > size())){
    
    }
    else
    { 
    // remove the first node in the list
    if (index == 1)
    { 
    cur = head;
    head = head->next; 
    
    }
    else{
    ListNode *prev = find(index-1); 
    
    cur = prev->next;
    prev->next = cur->next;
    } 
    
    // clean things up!
    length--;
    cur->next = NULL;
    delete cur;
    }
    
    }
    
    
    ListNode *Sequence::find(int index){
    
    if ((index <1) || (index >size())){
    return 0;
    }
    else{
    ListNode *cur = head;
    for(int skip =1; skip<index; ++skip)
    cur=cur->next;
    return cur;
    }
    }

  2. #2
    Rabble Rouser Slacker's Avatar
    Join Date
    Dec 2005
    Posts
    116
    The best way to figure out linked list operations is to get a handful of spare change and play it out on a table or desk. To move a node from just after A to just after B, you do this:
    Code:
    void move ( ListNode *a, ListNode *b )
    {
      ListNode *c = a->next; // Node to move
      a->next = c->next; // Close the gap where c was
      c->next = b->next; // Insert c in front of b's next link
      b->next = c; // Connect c to b
    }
    Alternatively, if the position of c is the only thing you care about, you can just swap the data:
    Code:
    #include <algorithm>
    
    void move ( ListNode *a, ListNode *b )
    {
      std::swap ( a->next->item, b->next->item );
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 06:46 PM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 08:11 AM
  5. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 07:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21