This guide will use examples from the C/C++ programming language, however many of the information carries over to other areas and languages
- An array is a collection of elements, all of the same type, accessed by a common name.
- Arrays can be either one or two dimensional.
- A one-dimensional array is like a list
- And a two-dimensional array is like a table, or grid
- Arrays are declared by first specifying their data type, then their name, and lastly the size in square brackets([])
- Arrays are initially set to 0
int myArray[5]; // creates list of 5 integers
double myArray2[4][6]; // creates a table of doubles with 4 rows and 6 columns
- Arrays can be initialized once declared just like variables
- Initialize with curly brackets ({}). Note that elements are separated by commas
- An array may be partially initialized, with the remaining elements set to 0
- If an array is fully initialized, the dimension is not required
int arr[3] = {7, 8, 9};
int sumArray[100] = {45, 88, 2};
double piFractions[ ] = { 3.141592654, 1.570796327, 0.785398163 };
double anotherArray[2][3] = {{1, 2, 3}, {4, 5, 6}};
- Elements in an array are accessed by a specific index (offset)
- Array indices start at 0, not 1 so
myArray[1]is the second element in the list
- Great for instant access to elements
- Quickly and easily iterate through all elements in a sequence with a loop.
- Arrays take up less memory than linked lists. Each element stored on the stack is just a piece of data; whereas a linked list requires both data AND one or more pointers to the next element
Intro to C Programming: Arrays - University of Illinois at Chicago
- Similar in concept to arrays, except linked lists can be expanded
- The two main types are singly-linked lists and doubly-linked lists
- Singly-linked: every element contains some data along with a link to the next element
- Doubly-linked: same as singly-linked list, but contains a link to the next and previous element Linked List Terminology
- Node: the element
- Data: the data being stored in that specific node (i.e. an integer)
- Next: contains the address (position/location) of the next node in the list
- Head: the start of the list
- Tail: the end of the list
We must define a structure
struct node
{
int data;
node *next;
};
- Linked lists are preferred over arrays when:
- you need constant-time insertions/deletions from a list (such as in real time computing where time predictability is absoultely critical)
- You may want to update the number of items in the list. With arrays you would need tp create a new one and copy over the values. This takes up a lot of time and memory
- You want to insert items at the middle of the list (i.e. priority queue)
When to use a linked list over an array - Stack Overflow Comprehensive Guide to Singly-Linked list is C++