Solved

linked list problem

Posted on 2004-04-18
14
695 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
ID: 10857080
>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
ID: 10857142
  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
ID: 10857385
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
ID: 10857511
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
ID: 10857597
>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
ID: 10857615
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
ID: 10857619
>1. Sorting implies minimum O(n^2)

1. Sorting implies minimum O(nlog(n))
0
Make managing Office 365 email signatures a breeze

Are you using Office 365? Having trouble trying to set up email signatures for your users? Getting stressed out managing multiple signatures? Need an easier way to manage? We have a solution for you, try the most-user friendly and powerful signature management tool on the market.

 
LVL 45

Expert Comment

by:sunnycoder
ID: 10857638
and how about freeing the memory ?
0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10857865
>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
ID: 10857871
>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
ID: 10857901
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
ID: 10866249
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
ID: 10866912
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
ID: 10866970
ankur,

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

Featured Post

Backup Your Microsoft Windows Server®

Backup all your Microsoft Windows Server – on-premises, in remote locations, in private and hybrid clouds. Your entire Windows Server will be backed up in one easy step with patented, block-level disk imaging. We achieve RTOs (recovery time objectives) as low as 15 seconds.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

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…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

914 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

15 Experts available now in Live!

Get 1:1 Help Now