Data Structures & Algorithms

Array

An array is a sequenced collection of variables all of the same type. Each variable, or cell, in an array has an index, which uniquely refers to the value stored in that cell. The cells of an array, A, are numbered 0, 1, 2, and so on. Each value stored in an array is often called an element of that array.

• An array can store primitive elements, such as characters.
• An array can also store references to objects.

• Adding an Entry:
  • To add an entry e into array board at index i, we need to make room for it by shifting forward the n - i entries board[i],...,board[n - 1]

• Removing an Entry:
  • To remove the entry e at index i, we need to fill the hole left by e by shifting backward the n - i - 1 elements board[i + 1],...,board[n - 1]

List ADT

List as Abstract Data Type. Cuando hablamos de ADT, queremos simplemente definir el comportamiento de la estructura de datos que queremmos definir; y no la definición estricta de una implementación en programación. Por tanto, en este sentido, a List ADT sería:

• A way to organize data
  • Examples
    • To-do list
    • Gift lists
    • Grocery Lists
• Items in list have position
• Items may be added anywhere
  • Write/modify items at a position.

Array Lists

An obvious choice for implementing the list ADT is to use an array, A, where A[i] stores (a reference to) the element with index i. With a representation based on an array A, the get(i) and set(i, e) methods are easy to implement by accessing A[i] (assuming i is a legitimate index).