Array list - Revision history

Weihe: /* Remark */

2015-09-21T09:59:18Z

Remark

← Older revision		Revision as of 09:59, 21 September 2015
Line 18:		Line 18:
	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 <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 <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 <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.		# 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.

Weihe: /* Remark */

2015-09-21T09:58:57Z

Remark

← Older revision		Revision as of 09:58, 21 September 2015
Line 18:		Line 18:
	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 <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 <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 <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.		# 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.

Weihe: /* Remark */

2015-09-21T09:58:40Z

Remark

← Older revision		Revision as of 09:58, 21 September 2015
Line 18:		Line 18:
	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.

Weihe: /* General information */

2015-09-21T09:56:04Z

General information

← Older revision		Revision as of 09:56, 21 September 2015
Line 3:		Line 3:
	== General information ==		== General information ==

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

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

Weihe: /* General information */

2015-09-21T09:55:35Z

General information

← Older revision		Revision as of 09:55, 21 September 2015
Line 3:		Line 3:
	== General information ==		== 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 ==

Luedecke at 23:09, 19 June 2015

2015-06-19T23:09:48Z

← Older revision		Revision as of 23:09, 19 June 2015
Line 1:		Line 1:
			[[Category:Videos]]
			{{#ev:youtube\|https://www.youtube.com/watch?v=uYTck0kDvl4\|500\|right\|\|frame}}
	== General information ==		== General information ==

Luedecke at 09:04, 7 June 2014

2014-06-07T09:04:42Z

← Older revision		Revision as of 09:04, 7 June 2014
Line 1:		Line 1:

	== General information ==		== General information ==

Luedecke at 09:02, 7 June 2014

2014-06-07T09:02:05Z

← Older revision		Revision as of 09:02, 7 June 2014
Line 1:		Line 1:
	General information
			== General information ==

	Abstract Data Structure: Linear sequence		'''Abstract Data Structure: Linear sequence'''

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

	There is a fixed number .		There is a fixed number .
Line 13:		Line 14:
	The components of are void.		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:

Luedecke: 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..."

2014-06-07T08:59:29Z

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..."

New page

General information

Abstract Data Structure: Linear sequence

Implementation Invariant:

There is a fixed number .
An object contains a linked list whose keys are pairs consisting of
an array , whose index range is and whose component type is , and
a natural number .
For an array list item:
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

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 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.