Please enable JavaScript.
Coggle requires JavaScript to display documents.
Array and String - Coggle Diagram
Array and String
1. Intro to Array
0. Overview
What is the corresponding built-in data structure of
array
and
dynamic array
in your frequently-used language?
How to perform basic operations (initialization, data access, modification, iteration, sort, etc) in an array?
How to perform basic operations (initialization, data access, modification, iteration, sort, addition, deletion, etc) in a dynamic array?
array
and
dynamic array
1. Intro to Array
An
array
is a basic data structure to
store a collection of elements sequentially
. But elements can be
accessed randomly
since each element in the array can be identified by an array
index
.
2. Intro to Dynamic Array
an array has a
fixed capacity
and we need to specify the size of the array when we initialize it
most programming languages offer built-in
dynamic array
which is still a random access list data structure but with
variable size
3. Intro to String
1. Intro to String
String has its own
compare function
It depends on the answer to the question:
Does the language support
operator overloading
?
If the answer is yes (like C++), we may use "==" to compare two strings.
If the answer is no (like Java), we may not use "==" to compare two strings. When we use "==", it actually compares whether these two objects are the same object.
Immutable
or
Mutable
Immutable means that you can't change the content of the string once it's initialized.
Compare to an array, there are some extra operations we can perform on a string.
concatenate
find
get substring
A string is actually an array of
unicode characters
. You can perform almost all the operations we used in an array.
2. Immutable String - Problems & Solutions
If you want your string to be mutable, there are some substitutions:
If you did want your string to be mutable, you can convert it to a char array.
If you have to concatenate strings often, it will be better to use some other data structures like
StringBuilder
4. Two-Pointer Technique
1. Two-pointer Technique - Scenario I
Let's start with a classic problem:
Reverse the elements in an array.
We can use two pointers at the same time to do the iteration: one starts from the first element and another starts from the last element. Continue swapping the elements until the two pointers meet each other.
2. Two-pointer Technique - Scenario II
Sometimes, we can use two pointers with different steps to solve problems.
E.g., Given an array and a value, remove all instances of that value in-place and return the new length.
2. Intro to 2D Array
1. Intro to 2D Array
In some languages, the multidimensional array is actually implemented internally as a
one-dimensional array
while in some other languages, there is actually
no multidimensional array at all
.
5. Conclusion
1. Array-related Techniques
0. Overview