Evaluation of List Implementations

The following table is based on executing each function 1,000,000 times and computing the average execution time.
Run times are expressed in microseconds.
All functions were applied to a list of 1000 elements.
The function GetElement() accessed positions both sequentially and randomly in the list.

The functions Insert() and Delete() accessed elements randomly in the list.

Type of List	`GetElement` (sequential)	`GetElement` (random)	`Insert`	`Delete`	`PushFront`	`PopFront`	`PushBack`	`PopBack`
Array List	0.02	0.30	14.9	15.9	28.7	31.1	0.14	0.23
Circular Array List	0.13	0.38	7.81	7.83	0.21	0.23	0.19	0.24
Linked List	8.49	8.81	16.9	19.7	0.68	0.69	32.5	61.1
Linked List w/Tail	8.41	8.82	16.8	19.8	0.71	0.69	0.66	35.3
Doubly Linked List	4.51	4.85	8.07	9.13	0.71	0.60	0.65	0.67
Circularly Linked List	4.53	4.92	8.13	9.13	0.71	0.64	0.72	0.63
Array List w/Iterator	0.05	0.29	14.6	15.9	28.2	31.0	0.15	0.23
Linked List w/Iterator	0.10	8.91	16.8	20.1	0.69	0.69	32.5	62.6
Circularly Linked List w/Iterator	0.13	5.00	8.28	9.28	0.75	0.63	0.76	0.61
Recursive Linked List	35.1	35.7	71.2	57.9	0.73	0.71	147.6	115.5

Example - TimeTest.cpp

Return to Lectures page

This page was last modified on Feb 28, 2001

URL: http://people.hsc.edu/faculty-staff/robbk/Coms262/Lectures/EvaluationOfLists.html