This is the start of my learning journey of Data Structure and Algorithm. I will not copy paste texts I’ve learnt from elsewhere. I hope to provide short and concise summarise of things. Focus on first princple.
Static Array & Dynamic Array
Static Array
static array : A Contiguous block of memory.
dynamic array : A type of data structure based on static array, but some api implemented to make it more flexible.
In C++, to declare a static array, we can do like this:
int arr[10]; // declare an array of 10 integers
There are a few operations we can do on array(with Time Complexity):
- Adding
- Appending at the end: O(1)
- Inserting in the middle: O(n)
- Deleting
- Deleting from the end: O(1)
- Deleting from the middle: O(n)
- Searching
- Given an index: O(1)
- Given a value: O(n)
- Modifying
- Given an index: O(1)
Dynamic Array
- auto resizing
- boundary checking
- avoid memory leakage
To implement a dynamic array, we need to take care of the following things:
- default constructor
- parameterized constructor
- add last element
- add element at index
- add first element
- remove last element
- remove element at index
- remove first element
- get element at index
- set element at index
- get size
- is_empty
- resize
- isElementIndex
- isPositionIndex
- display
- destructor
Here is a simple implementation of a dynamic array in C++:
#include <string>
#include <vector>
#include <stdexcept>
class MyLinkedList {
private:
int* data;
int size;
int cap;
static const int INIT_CAP = 1;
public:
MyLinkedList(){
this->data = new int[INIT_CAP];
this->size = 0;
this->cap = INIT_CAP;
}
MyLinkedList(int initCapacity){
this->data = new int[initCapacity];
this->size = 0;
this->cap = INIT_CAP;
}
~MyLinkedList() { delete[] data; }
int get(int index) {
if (index < 0 || index >= size) return -1;
return data[index];
}
void add(int index, int val) {
if (index < 0) index = 0;
if (index > size) return ;
if (size == cap) resize(cap * 2);
for (int i = size - 1; i >= index; --i) {
data[i + 1] = data[i];
}
data[index] = val;
++size;
}
void addAtHead(int val) { add(0, val); }
void addAtTail(int val) {
if (size == cap) resize(cap * 2);
data[size++] = val;
}
void addAtIndex(int index, int val) { add(index, val); }
int removeAt(int index) {
int deletedVal = data[index];
for (int i = index + 1; i < size; ++i) {
data[i - 1] = data[i];
}
data[size - 1] = int(); // clear slot to avoid leaks for objects
--size;
if (size == cap / 4 && cap > 1) resize(cap / 2);
return deletedVal;
}
int deleteAtIndex(int index) {
if (index < 0 || index >= size) return -1;
return removeAt(index);
}
private:
void resize(int newCap) {
int* temp = new int[newCap];
for (int i = 0; i < size; ++i) temp[i] = data[i];
delete[] data;
data = temp;
cap = newCap;
}
};
/*
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
Passed all test cases on LeetCode: https://leetcode.cn/problems/design-linked-list/ (although the name is LinkedList, the implementation is actually a dynamic array)
Circular Array
With the use of % operator, we can make the array circular. We can achieve O(1) time complexity for both adding and removing elements from both ends, whereas in a normal dynamic array, adding or removing elements from the front would take O(n) time complexity.
Regarding the definition of interval, we have a few options:
- [head, tail) (inclusive, exclusive)
- [head, tail] (inclusive, inclusive)
- (head, tail] (exclusive, inclusive)
We will stick with the first one: [head, tail) because its the most convinient one.
class MyLinkedList {
std::vector<int> arr;
int start;
int end;
int count;
void resize(int newSize){
std::vector<int> newArr(newSize);
for (int i = 0; i < count; i++){
newArr[i] = arr[(start+i) % arr.size()];
}
arr = std::move(newArr); //steal the pointer from newArr
// [start, end) <- (inclusive, exclusive)
start = 0;
end = count;
}
int phys(int i) {return (start + i)%arr.size();}
public:
MyLinkedList()
: MyLinkedList(1) {}
explicit MyLinkedList(int size)
: arr(size), start(0), end(0), count(0) {}
int get(int index) {
if (index < 0 || index >= count) return -1;
return arr[phys(index)];
}
void addAtHead(int val) {
if (isFull()){
resize(arr.size() * 2);
}
start = (start - 1 + arr.size())%arr.size(); // the minimum value inside bracket is 0 for modulus to work in some sense.
arr[start] = val;
count++;
}
void addAtTail(int val) {
if (isFull()){
resize(arr.size() * 2);
}
arr[end] = val;
end = (end + 1)%arr.size();
count++;
}
void addAtIndex(int index, int val) {
if (isFull()){
resize(arr.size() * 2);
}
if (index < 0 || index > count) return;
start = (start - 1 + arr.size())%arr.size(); //TODO: kinda confused here
for (int i = 0; i < index; ++i){
arr[phys(i)] = arr[phys(i+1)];
}
arr[phys(index)] = val;
++count;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= count) return;
if (index < count/2){
for (int i = index; i > 0; --i){
arr[phys(i)] = arr[phys(i-1)];
}
start = (start+1)% arr.size();
} else {
for (int i = index; i + 1 < count; ++i){
arr[phys(i)] = arr[phys(i+1)];
}
end = (end + arr.size() -1 ) % arr.size();
}
count--;
}
bool isFull(){
return arr.size() == count;
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/