Thread: 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;
}
}

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 );
}