Arrays, Lists and Vectors
From Wikiversity
 |
Subject classification: this is a technology resource . |
 |
Educational level: this is a tertiary (university) resource. |
Contents |
[edit] Arrays
[edit] What is an array
If you have taken the prerequisites to this course or have done any more than the very basics of programming you will have come across arrays. You will know an array is simply an area of memory allocated for a set number of elements of a known size. You can access these elements by their index (position in the array) and also set or retrieve the value stored. Arrays are not to be confused with Associative Arrays, which will be covered in the Hash Tables lesson.
[edit] Characteristics of an array
An array is always of a fixed size; it does not grow as more elements are required. The programmer must ensure that only valid values in the array are accessed, and must remember the location in the array of each value. Arrays are basic types in most programming languages and have a special syntax for their use.
The computational complexity for writing to and accessing an array is O(1). No matter the number of elements in the array, the calculation to find the element in the array is single multiplication and addition.
element_memory_location = start_memory_location + (size_of_element * index_in_array)
The computational complexity of inserting an element in the middle of an array is O(N), where N is the number of elements in the array. The elements in the array must all be shifted up one index after the insertion, or all the elements must be copied to a new array big enough to hold the inserted element.
pseudo code for insertion
The memory usage of an array is simply the number of elements in the array multiplied by the size of each element.
[edit] Lists
[edit] Linked Lists
A linked list is made up of a linear series of nodes (For non-linear arrangements of nodes, see Trees and Graphs). These nodes, unlike the elements in an array, do not have to be located next to each other in memory in order to be accessed. The reason is that each node contains a link to another node. The most basic node would have a data field and just one link field. This node would be a part of what is known as a singly linked list, in which all nodes contain only a next link. This is different than a doubly linked list, in which all nodes have two links, a next and a previous. While a linked-list API may exist in one's programming library, linked lists are often implemented by the programmer and customized for particular applications.
[edit] Characteristics of a Linked List
As mentioned above, a node in a linked list must have a data field and either one or two links. This allows the linked list to grow or shrink in constant O(1) time, as all that needs be done to insert or delete a node is change a few links. This is much better than the time for inserting or deleting an element in an array.
However, the linked list requires linear O(N) time to find or access a node, because there is no simple formula as listed above for the array to give the memory location of the node. One must traverse all links from the beginning until the requested node is reached. If nodes are to be inserted at the beginning or end of a linked list, the time is O(1), since references or pointers, depending on the language, can be maintained to the head and tail nodes. If a node should be inserted in the middle or at some arbitrary position, the running time is not actually O(1), as the operation to get to the position in the list is O(N).
Code for a singly linked list and node
Code for a doubly linked list and node
Linked lists use more memory than an array containing the same data due to each element not only having a value, but also one or two links.
[edit] Vectors
| Project: Data Structures and Algorithms |
| Previous: An introduction to Data Structures and Algorithms — Arrays, Lists and Vectors — Next: Stacks and Queues |
