Solved

linked list problem

Posted on 2004-04-18
14
694 Views
Last Modified: 2010-04-15
I wanna simualate the SCAN disk algorithm
for example this is the linked list, two pointers disk_q_head,l disk_q_tail pointer to the head and tail of the linked list
17->23->3->18->50->6->NULL;
i wanna pick 23 when executed first time: 17->3->18->50->6->NULL;
then 50 :17->3->18->6->NULL
then there are no more in that direction and go to 99:
then change the direction to 18: 17->3->6->NULL..ans so on...
typedef struct disk_rec disk;

struct disk_rec {
      int            proc;
      int            track;
      disk            *next;
      ReadOrWrite      type;
};
...

  disk *x, *target, *curr;
   x = curr = target = disk_q_head;
   int foundtarget = 0;
   while(x != NULL && x->track > diskhead)
   {
     if (foundtarget == 0)
     {
      target = x;
      foundtarget = 1;
      break;

     }
     if (foundtarget == 1)
     {
       if(target->track > x->track)
           target = x;
       else
           break;
      }
      x = x->next;
   }
   while(curr->next != target)
       curr = curr->next;
   curr->next = target->next;
   free(target);
When the target is the max and need to go to disk end, how can I know it , and what's with the above code....can't work it out...
thanks for help
0
Comment
Question by:redsar
  • 7
  • 6
14 Comments
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
>When the target is the max and need to go to disk end, how can I know it
Iterate through the list and if there is no entry > diskhead, you need to do to the end of the list

>what's with the above code....can't work it out...
pls elaborate
0
 
LVL 45

Assisted Solution

by:sunnycoder
sunnycoder earned 50 total points
Comment Utility
  while(x != NULL && x->track > diskhead)    ...... this loop will break as soon as you encounter a value less than diskhead ... probably this is not what you want ... keep loop condition to be while ( x!= NULL) and inside the loop if x->track < diskhead then continue !!!
   {
     if (foundtarget == 0)
     {
      target = x;
      foundtarget = 1;
      break;

     }
     if (foundtarget == 1)
     {
       if(target->track > x->track)
           target = x;
       else
           break;
      }
      x = x->next;
   }
The method you are using is O(n^2) .... you traverse the entire list every time !!! The idea of splitting the list into sorted order was superior ... it will take only O(nlogn) time
0
 
LVL 9

Accepted Solution

by:
ankuratvb earned 50 total points
Comment Utility
I still say that keeping the list sorted always by modifying your insert function would be a better option.

Then,you have 2 options:

1. singly linked list:

Keeping the list ordered shouldnt be a problem.
Delete nodes larger than current position and insert into another list.
Sort the remaining nodes in descending order and insert onto the other list.

2. doubly linked list:

Using doubly linked list,sorting in reverse order would be simpler.

0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
Here,you are scanning the entire list everytime a request is to be selected.
If you have the list sorted,traverse till the track number becomes greater than the current position,then delete all subsequent nodes from the original list.This(deletion) can be done in O(1) time.

Form a list of the deleted nodes.This can also be done in O(1) time as you just have to point to the start of the deleted nodes.

Reverse the list and attach to the first list.
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
>If you have the list sorted,traverse till the track number becomes greater than the current
>position,then delete all subsequent nodes from the original list.This(deletion) can be done in O(1)
>time.
1. Sorting implies minimum O(n^2)
2. Deletion of one node is O(1) ... since you can have O(n) node to delete, deletion will be O(n)

>Form a list of the deleted nodes.This can also be done in O(1) time as you just have to point to
>the start of the deleted nodes.
>Reverse the list and attach to the first list.
Reversing is again O(n)
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
You dont have to delete all nodes one by one.

Just set the next pointer of the last node that has track number less than current position to NULL.

Setting a pointer takes O(1) time.
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
>1. Sorting implies minimum O(n^2)

1. Sorting implies minimum O(nlog(n))
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
and how about freeing the memory ?
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
>and how about freeing the memory ?

We dont need to free memory right now coz we will be inserting them back into the list after reversing them.

For e.g.
if this is the original list:
Current poistion:10
17->23->3->18->50->6->NULL;
Sorted would be:(i say dont sort it when u need it,keep it sorted as u insert nodes)

3->6->17->18->23->50->NULL;

Traverse till u have track numbers less than 10:
set the next pointer of the last such node to NULL and save the address of the next node in another variable.
So,now you have two lists:
3->6->NULL
and
17->18->23->50->NULL;

Now reverse the first list and attach to the end of the second.

Since,we will be attaching the deleted nodes again into the list,we dont need to free the mem. allocated to them.
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
>We dont need to free memory right now coz we will be inserting them back into the list after reversing them
then why add the overhead of "deleting" ... or was it just a misnomer
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
I guess my english is getting worse by the day. :~)

What i meant by deleting was to remove a number of nodes from one list and make them into another list.

I guess splitting would've been a better word.


0
 

Author Comment

by:redsar
Comment Utility
thanks for the help...I'm totally lost, but anyway thanks a lot.
I get yours idea, but I just can't extend it into code....
0
 
LVL 9

Expert Comment

by:ankuratvb
Comment Utility
C'mon redsar,thats not fair.You are not supposed to accept an answer until your prolem is solved.

If its the code you cant understand,i'll try again.

Give us a chance.

I request sunny on the OP's behalf to unaccept the answers of this question as well as the other question:

http://oldlook.experts-exchange.com:8080/Programming/Programming_Languages/C/Q_20957942.html
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
ankur,

I would be happy to open both the questions if redsar shows some interest.
0

Featured Post

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now