insert to sorted position linked list

Question

Hello, I have question quite much related to this one I asked a while ago

http://stackoverflow.com/questions/3743764/place-a-value-in-the-sorted-position-immediately

I wonder if you can use the same approach in that you step backward in a linked list to find the position it should be inserted into.

If it is possible how do you loop a linked list backward? I can't figure it out because it seems not possible since it should be a double linked listed then if I'm not wrong? Anyway I'm working with singly linked list.

EDIT

I think I'm going for the look forward approach, this is what I made so far. I'm stuck at that point in how I should save the previous (key, value). Here's the code so far of what's done. The for-loop is used to look for the position I want to insert to. And I have peek forward, which will break in case it reach the end.

OK so far, now I want to insert the value to the correct position. It is here I'm stuck. How should it be done? Now when I insert keys: 2, 1, 0, 3, it will only print out 1, 3

struct my_list
{
  /* a pointer to the first element of the list */
  struct list_link* first;
};

struct list_link
{
   int key;                // identifies the data
   double value;           // the data stored
   struct list_link* next; // a pointer to the next data
};

struct list_link* create(int key, double value, struct list_link* next)
{
   // creates the node;
   struct list_link * new_link;
   new_link = new struct list_link;

   // add values to the node;
   new_link->key = key;
   new_link->value = value;
   new_link->next = next;

   return new_link; // Replace this, it is just to be able to compile this file
}

void list_insert(struct my_list* my_this, int key, double value)
{
   if(my_this->first == NULL)   // add if list empty
      my_this->first = create(key, value, my_this->first);   
   else
   {      
      struct my_list* curr;
      struct my_list* prev;         
      struct my_list start;

      start.first = my_this->first;
      curr = my_this;

      cout << "Too be appended: ";
      cout << key << " " << value << endl;
      for(curr->first = my_this->first; 
          key > curr->first->key; 
          curr->first = curr->first->next)
      {
         if(curr->first->next == NULL) //peek at front if empty
            break;
      }
      cout << "append here " << key << " > " << 
          curr->first->key << endl << endl;
      //perform some surgery
      if(curr->first->next == NULL)
      {     
         curr->first->next = create(key, value, my_this->first->next);
      }
      else
      {       
         curr->first = start.first; //move back to start of list
         my_this->first = create(key, value, my_this->first);
      }      
   }  
}

Answer 1

No a singly linked list cannot go backwards.

Answer 2

You can't traverse a singly-linked list backward, but you can keep a pointer to the last two elements you have seen instead of just one.

So, traverse the list from the front, and keep two pointers: current, and previous. If the element you are inserting is less than current, then update previous to point to it.

Answer 3

Here's my understanding of what you're asking: when you search for an insert position in a singly linked list you find it by discovering that you've gone one node too far, then, how to go back?

Well, there are two main solutions:

• peek one node ahead while searching (a different viewpoint of the same idea is to keep a "trailing" pointer), or

• make sure that there's an artifical tail-node (so that you always have a real next node), and that there are no other "external" pointers into the list than your search pointer. Insert your new node after the node with higher value. Swap the contents of the two nodes.

The second solution is a little brittle because of the assumption of no other "external" pointers into the list. But it's sort of ingenious. I learned it from Donald Knuth's "The Art of Computer Programming".

Alternatively to these singly linked list solutions, you can just double-link your list.

Cheers & hth.,

Answer 4

You can use recursion to traverse a singly linked list backwards.

void traverse_backwards(NODE node)
{
    if (node->next != null && !node->is_marked)
    {
        node->is_marked = 1;
        traverse_backwards(node->next);
    }
    else
    {
        // logic goes here
    }
}

Answer 5

Its easier to take an example

10 -> 20 -> 30 -> NULL

Traverse the list with two pointers: (i) currentNode and (ii) nextNode.

Start with currentNode = NULL and nextNode = <10>. Move both of them forward in a loop as long as nextNode->key < insertkey is true.

Upon exit from loop (example: for insertKey == 25, currentNode = <20>, nextNode = <30>):

1. create newNode with newNode->key = insertKey and newNode->value = insertValue

2. "Insert" newNode between currentNode and nextNode by doing

   2.1 currentNode->next = newNode

   2.2 newNode->next = nextNode