Array list: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with " General information Abstract Data Structure: Linear sequence Implementation Invariant: There is a fixed number . An object contains a linked list whose keys are pa...")
 
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
General information
[[Category:Videos]]
{{#ev:youtube|https://www.youtube.com/watch?v=uYTck0kDvl4|500|right||frame}}
== General information ==


Abstract Data Structure: Linear sequence
'''Abstract Data Structure:''' [[Ordered sequence]]


Implementation Invariant:
'''Implementation Invariant:'''


    There is a fixed number .
# There is a fixed number <math>N</math>.
    An object contains a linked list whose keys are pairs consisting of
# An object contains a linked list whose keys are pairs consisting of an array <math>A</math>, whose index range is <math>1,\ldots,N</math>and whose component type is <math>\mathcal{K}</math>, and a natural number <math>n</math>.  
        an array , whose index range is and whose component type is , and
# For an array list item:
        a natural number .  
## The components <math>A[1|,\ldots,A[n]</math> are the elements of the ordered sequence that are stored in this item (in this order).
    For an array list item:
## The components <math>A[n+1|,\ldots,A[N]</math> are void.
        The components of are the elements of the ordered sequence that are stored in this item (in this order).
 
        The components of are void.
== Remark ==


Remark


Admittedly, array lists are more complicated than linked lists. However, there are three advantages:
Admittedly, array lists are more complicated than linked lists. However, there are three advantages:


    If is sufficiently large and the 's are close to , the space consumption is significantly reduced because there is only one next pointer per array, not per element.
# If <math>N</math> is sufficiently large and the <math>n</math>'s are not too far from <math>N</math> , the space consumption is significantly reduced compared to a linked list,because there is only one next pointer per ''array'', not per element.
    If there are many insertion and removal operations, arrays instead of single list items may reduce space fragmentation.
# If there are many insertion and removal operations, arrays instead of single list items may reduce space fragmentation.
    If is chosen such that the size of an array list item fits perfectly into one page of the background device, the number of accesses to the background device may be significantly reduced.
# If <math>N</math> is chosen such that the size of an array list item fits perfectly into one page of the background device, the number of accesses to the background device may be significantly reduced.

Latest revision as of 09:59, 21 September 2015

General information

Abstract Data Structure: Ordered sequence

Implementation Invariant:

  1. There is a fixed number [math]\displaystyle{ N }[/math].
  2. An object contains a linked list whose keys are pairs consisting of an array [math]\displaystyle{ A }[/math], whose index range is [math]\displaystyle{ 1,\ldots,N }[/math]and whose component type is [math]\displaystyle{ \mathcal{K} }[/math], and a natural number [math]\displaystyle{ n }[/math].
  3. For an array list item:
    1. The components [math]\displaystyle{ A[1|,\ldots,A[n] }[/math] are the elements of the ordered sequence that are stored in this item (in this order).
    2. The components [math]\displaystyle{ A[n+1|,\ldots,A[N] }[/math] are void.

Remark

Admittedly, array lists are more complicated than linked lists. However, there are three advantages:

  1. If [math]\displaystyle{ N }[/math] is sufficiently large and the [math]\displaystyle{ n }[/math]'s are not too far from [math]\displaystyle{ N }[/math] , the space consumption is significantly reduced compared to a linked list,because there is only one next pointer per array, not per element.
  2. If there are many insertion and removal operations, arrays instead of single list items may reduce space fragmentation.
  3. If [math]\displaystyle{ N }[/math] is chosen such that the size of an array list item fits perfectly into one page of the background device, the number of accesses to the background device may be significantly reduced.