RE: [sv-ec] linked list amortization

Shalom,

 

For the definition of amortized cost, here's a good online reference:

http://en.wikipedia.org/wiki/Dynamic_array#Geometric_expansion_and_amort
ized_cost

 

Next, take a look at the STL list documentation (from which SV's
definition is likely derived), which uses almost identical language:

http://www.sgi.com/tech/stl/List.html

 

Perhaps it would be best to remove the "amortized" term to avoid
confusion.

 

            Arturo

 

________________________________

From: owner-sv-ec@eda.org [mailto:owner-sv-ec@eda.org] On Behalf Of
Bresticker, Shalom
Sent: Tuesday, September 25, 2007 11:27 PM
To: SV_EC List
Subject: [sv-ec] linked list amortization

 

Hi, 

In Annex H (Linked lists), the definition of 'list' in H.2 is: 

list: A doubly linked list, where every element has a predecessor and
successor. A list is a sequence that supports 
both forward and backward traversal, as well as amortized constant time
insertion and removal of elements 
at the beginning, end, or middle. 

What does 'amortized' mean here? 

Am I the only one who is not going to understand this? 

Thanks, 
Shalom 

 

Shalom Bresticker 
Intel Jerusalem LAD DA 
+972 2 589-6852 
+972 54 721-1033 

---------------------------------------------------------------------
Intel Israel (74) Limited
 
This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

-- 
This message has been scanned for viruses and 
dangerous content by MailScanner <http://www.mailscanner.info/> , and is

believed to be clean. 

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.