Data Structure
Dionysen

Array

Array has fixed size and contiguous memory. New elements cannot be appended. You can use memory address to access elements of Array.

char a[5] = {'h', 'e', 'l', 'l', 'o',}; 
C++ counts food tags from `0`, so `a[0] = 'h'` and `a[1] = 'e'`.
Random access using `a[i]` has `O(1)` time complexity.
Units of array can be modified.
a[0] = 'b';

result:

bello

Dynamic Allocation of Arrays

A size-n array can be created in this way:

char a[n];

But when writing the code, n must be known.

If n is unknown, how dose the program run?

char* a = NULL;
int n; // array size
cin >> n; // read in the size. e.g., get n = 5
a = new char[n];

Now a is an empty array whose size is 5.

// store somrthing in the array
a[0] = 'h';
a[1] = 'e';
a[2] = 'l';
a[3] = 'l';
a[4] = 'o';

When done, free memory. Otherwise, memory leak can happen.

delete [] a;
a = NULL;

Removing an element in the middle has O(n) time complexity. Require moving the remaining items leftward.

Vector

Vector is almost the same as array.

The main difference is that vector’s capacity can automatically grow.

New elements can be appended using push_back() in O(1) time(on average).

The last element can be removed using pop_back() in O(1) time.

std::vector<char> v = {'h', 'e', 'l', 'l', 'o'}; 
v.push_back();
v.pop_back();
v.erase(v.begin() + 1);

Vector can delete an element in the middle using erase() in O(n) time. So it is not better to do this.

std::vector<char> v(100);
cout << v.size(); // print "100"
cout << v.capacity(); // print "100"
// then
v.push_back('x');
cout << v.size(); // print "101"
cout << v.capacity(); // print "200"

When size is going to exceed capacity, program will create a new array of capacity 200, copy the 100 elements from the old array to the new, put the new element in the 101st position and free the old array from memory.

List

A Node

A node contains a data and two pointers that one points to the previous node and another points to the next node.

Doubly Linked List

std::list<char> l = {'h', 'e', 'l', 'l', 'o'}; 
cout << l[2];		// does not work
l[0] = 'a'; // does not work
list<char>::iterator iter = l.begin();
cout << *iter; // print 'h'
iter++;
cout << *iter; // print 'e'
*iter = 'a';

push_back();
push.front();

Diference

Array Vector List
Size fixed can increase and decrease can increase and decrease
Memory contiguous contiguous not contiguous
Array Vector List
Rand Access O(1) O(1)
push_back() O(1)(average) O(1)
pop_back() O(1) O(1)
insert() O(n)(average) O(1)
erase() O(n)(average) O(1)

Which shall we use?

Array: Fixed size throughout.

Vector:

  • Random access(i.e., read or write the i-th element) is fast.
  • Insertion and deletion at the end are fas.
  • insertion and deletion in the front and midddle are slow.

List:

  • Sequentially visiting elements is fast; random access is not allowed.
  • Frequent insertion and deletion at any position are OK.
int arr[] = {3, 5, 12, 16, 17, 26, 32, 51, 53, 64};

Inputs: (i) an array whose elements are in the accending order and (ii) a key.

Goal: Search for the key in the array. If found, return its index; if not found, return -1.

Examle 1:

  • Search for the elemnt 53.
  • Return 8.

Example 2:

  • Search for the element 9.
  • Return -1.

Example: key = 26. Use two variables left and right pointing to the front of the array and the back respectively.

int search(int arr[], int left, int right, int key)
{
while (left <= right) {
int mid = (left + right) / 2;
if (key == arr[mid])
return mid;
if (key > arr[mid])
left = mid + 1;
else
right = mid - 1;
}
return -1;
}

How to suport both search and insertion?

std::vector<int> v = {3, 5, 12, 16, 17, 26, 32, 51, 53, 64};

The ascending order must be kept; otherwisem search would take O(n) time.
Inserting an item into the middle has O(n) time complexity(on average).
Can we perform binary search in the list?
No, Given left and right, we cannot get mid efficiently.

Search Insertion
Vector O(log n) O(n)
List O(n) O(1)
Skip List O(log n) O(log n)
显示评论