Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17


Self Organizing List

Posted on 2001-09-14
Medium Priority
Last Modified: 2012-06-27
I have an assignment where I need to read data from a file, and use it to grow a self-organizing list with 4 of the following methods:
Front: If an item is not already present in the list, put it at the front, else ignore it.
Rear: If an item is not already present in the list, put it at the rear, else ignore it.
Move-to-front: If an item is already present in the list, move it to the front, else add it to the rear.
Transpose: If an item is already present in the list, interchange it with the item immediately before it, else add it to the rear..
Count: If an item is already present in the list, order list items by the frequency with which they have occurred, most frequent first, else add it to the rear.
Order: Maintain the list in ascending (numeric or alphabetical) order.

What I did was derive a class from std::list and then I implemented the first 4 of these insertion methods.  What I don't understand is the following:  Everytime I call Front, Rear, Move-to-front, and then Transpose to insert a new item, Rear will never have any effect on the list because Front will have already placed the item at the front of the list.  Or if I implemented all 6 methods, the last method called would be order which would cancel the effects of the other 5 methods.  It seems like a self organizing list should only use 1 of these methods, or maybe a combination of 2 or 3 of them.  Either that or I am misunderstanding everything.
Question by:nidan
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
LVL 16

Accepted Solution

imladris earned 140 total points
ID: 6483666
Yes, I agree. The first line reads "WITH 4 of the following methods". I would assume that means they have to be available. Which is used, would depend on some selection by the user of the list, perhaps in the constructor.

Author Comment

ID: 6485106
Here are the actual instructions which I don't understand:

Using the STL for list, add any four of the above six insertion methods, each corresponding to one of the methods above.  
Build a self-organizing list with the first 1000 numbers in Numbers and then insert TestNumbers into it.  Repeat for 2000, 4000, 8000, and 16000 numbers. ( Numbers and TestNumbers are data files which I have already ).

Then I have to explain what the theoretical complexity of each of the implemented methods is and why, and what the empirical complexity of each method is.

I don't need any code for this.  I want to know if you think I should create all 5 lists with a combination of the 4 methods:

while ( cin >> number )

or if I should use the standard list class to create the first list, and then use different methods to create the other 4 and then compare results.  Or should I create the 5 lists using the same method?  
LVL 49

Expert Comment

ID: 6485191
Stand back from the problem and it make a little more sense...

Some random data comes in to your program and you put it into a list.  Later you begin to access that data, and it turns out that some of the random elements are accessed more often than others.  So it would be convenient/expedient if those often-used data items were closer to the front of the list.

Or in another light, as more an more copies of a particular datum come in, you don't want to insert duplicates, you just want to increase a counter.  Then you want to reorganize so that the items with the highest count appear earlier in the list.

So really, you just need one insertion fn -- it places the item at the end of list or, if it is already in the list, it just bumps the count for that item and optionally moves it closer to the front of the list.

Because this is classwork, your prof wants you to write several insert functions and discuss them.  In real life, you would only use one at a time.

Front: Badly named -- call this fn UpdateOnly.  You would use this for a pre-built list.  Not an insert fn at all.

Rear: Call this fn AddNewOrUpdate.  It can be called for random items while you are building the list.

Move-to-front: Irrelevant excercise -- You would use this if you had a gut-feeling that the new item would eventually have a high count.  I'd call it ForcedInsertToFront.

Transpose: Irrelevant excercise -- I guess it could be used as a helper fn for the case when you happen to know that adding this datum would normally force a reorganization.  And to avoid that, you postpone the full reorg by moving it forward one notch immediately.  It will be closer to where you eventually want it to be.  I'd call it UpdateAndBumpForward

Count: Who thinks of these names?  This should be called AddNewOrUpdateAndForceReorder.  Like AddNewOrUpdate, this would be called while building the list.  However, it forces a reorganization with each new irem.  By using this, you ensure that the list is always in order, but performance would suck.  I'd use this fn every 10 or 100 inserts (or never; just call Order periodically).

Order: Not an insert operator - a helper fn.  It is called by AddNewOrUpdateAndForceReorder.

I hope that helps.

-- Dan
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!


Author Comment

ID: 6485927
I agree with what you're saying, but my dilemna is the instructions which say using the STL for list, add any four of the above 6 insertion methods, and build a self organizing list...  I have implemented 4 of the insertion methods.  How do I use these methods to create the lists?  Do I use all 4 of them together to add an item?  
Or do I use a different insertion method for every different list? Or should I use the same insertion method for every list?  The experiment is to create several kinds of self - organizing lists and compare their performance to the original list.  I am unsure of what the original list is.

LVL 30

Expert Comment

ID: 6495629
>>How do I use these methods to create the lists?  Do I
>>use all 4 of them together to add an item?  

No, you would not use all 4 together.
Each insertion method has it's own function, and depending on the calling functions's requirements, will depend on which function is called.

For example, if you had a function that took 10 names from a user's input, and the function had to put the names in a list, and then sort the list, you could make the function put all names that begin with letters A-M use the mylist.front() function, and all names that begin with letters N-Z use the mylist.rear() function.

This is not the greatest example in the world, but it might point you in the right direction.

Expert Comment

ID: 6502623

I'm probably too late to help you with your work, but I think this will shed light on your problem.  You should create six list classes, each a subclass of std::list, that have different implementations of insert ().

Then you create six empty lists and put the same data into each list. You could do this with a method called insert_all ():

void insert_all (integer item)
   bobby.insert (item);
   peter.insert (item)
   greg.insert (item);
   cindy.insert (item);
   jan.insert (item);
   marsha.insert (item);

LVL 11

Expert Comment

ID: 6868104
I think you forgot this question. I will ask Community Support to close it unless you finalize it within 7 days. Unless there is objection or further activity,  I will suggest to accept "imladris, DanRollins. Axter" comment(s) as an answer.

If you think your question was not answered at all, you can post a request in Community support (please include this link) to refund your points.
The link to the Community Support area is:


Expert Comment

ID: 6891068
Force-accepted by
CS Moderator

DanRollins: points for you at
Axter: points for you at

Expert Comment

ID: 6996994
Force accepted

** Mindphaser - Community Support Moderator **

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

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

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

688 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