How to choose a data structure
Selecting transcript lines in this section will navigate to timestamp in the video
Data Structures and Algorithms (DSA) are critical for optimizing how data is stored, accessed, and processed, directly affecting the performance of an application.
- There are loads of different kinds of data structures. There are a few things to consider when you're deciding which ones to go for. The first thing to think about is do you know in advance how many items are going to be in the data structure? There might only ever be 10 things in there, or you might have no idea how many items are going to end up inside this thing. Another thing to think about is whether you want to allow duplicates. Sometimes you might not care if your data structure contains several of the same thing, but to other times you might want to enforce that no duplicates are allowed and everything in it has to be unique. Next up is the order of elements. Is it important that the data stays in a specific order? For example, imagine a real life queue of people outside a store. The first person to join is the first person to leave the queue. So in this case, the order needs to stay fixed, but at other times, it might not matter what order the elements are in. Another important thing to think about is the performance of the data structure you choose. Some are quicker if you want to insert and delete elements, but others are quicker at retrieving elements. So it's a good idea to have a think about what you're going to be doing with the data. Are you going to be changing and updating it a lot, or is it going to stay the same the whole time, and you're just going to be finding and accessing elements in it. The time differences might not be noticeable when you start writing a new app, but some bigger applications, or as new app scale up, these things can actually have a huge impact on performance. One more thing to think about is memory. Some data structures take up more memory than others, which can also affect performance. This may seem like a lot to think about for something as simple as choosing a data structure, but the more you use them, the easier it gets, and there's never a perfect data structure, so there will always be some trade offs.
1. Lets consider about Array data structure.
The general form of array declaration is
Method 1 is int arr[];
Method 2 is int[] arr;
The element type determines the data type of each element that comprises the array. Like an array of integers, we can also create an array of other primitive data types like char, float, double, etc. and objects (which are instances of classes, like String, Integer, or custom classes user define).
Initialization an Array in Java
When an array is declared, only a reference of an array is created. We use new to allocate an array of given size.
int arr[] = new int[size];
- Array Declaration is generally static, but if the size in not defined, the Array is Dynamically sized.
- Memory for arrays is always dynamically allocated (on heap segment) in Java. This is different from C/C++ where memory can either be statically allocated or dynamically allocated.
- The elements in the array allocated by new will automatically be initialized to zero (for numeric types), false (for boolean) or null (for reference types).
Array Literal in Java
In a situation where the size of the array and variables of the array are already known, array literals can be used.
// Declaring array literal
int[] arr = new int[]{ 1,2,3,4,5,6,7,8,9,10 };
- The length of this array determines the length of the created array.
- There is no need to write the new int[] part in the latest versions of Java.
int[] arr = { 1,2,3,4,5,6,7,8,9,10 }; Change an Array Element
To change an element, assign a new value to a specific index. The index begins with 0 and ends at (total array size)-1.
// Changing the first element to 90
arr[0] = 90;
Array Length
We can get the length of an array using the length property:
// Getting the length of the array
int n = arr.length;
Accessing and Updating All Array Elements
- All the elements of array can be accessed using Java for Loop.
- Each element in the array is accessed via its index.
// accessing the elements of the specified array
for (int i = 0; i < arr.length; i++)
System.out.println("Element at index " + i + " : " + arr[i]);
}
Creating copy of an array - some methods
Arrays.copyOf() Method (Creates New Array)
- This method creates a new array and copies the entire original array into it.
- If the specified length is greater than the original array, extra elements are initialized with default values.
int[] arr = {1, 2, 4, 8};int[] tempArr = Arrays.copyOf(arr, arr.length);Arrays.copyOfRange() Method (Copying a Subset)
- Similar to copyOf(), but allows copying a specific range of elements.
int[] arr = {1, 2, 4, 8};int[] tempArr = Arrays.copyOfRange(arr, 0, arr.length);
Advantages of Java Arrays
- Efficient Access: Accessing an element by its index is fast and has constant time complexity, O(1).
- Memory Management: Arrays have fixed size, which makes memory management straightforward and predictable.
- Data Organization: Arrays help organize data in a structured manner, making it easier to manage related elements.
Disadvantages of Java Arrays
- Fixed Size: Once an array is created, its size cannot be changed, which can lead to memory waste if the size is overestimated or insufficient storage if underestimated.
- Type Homogeneity: Arrays can only store elements of the same data type, which may require additional handling for mixed types of data.
- Insertion and Deletion: Inserting or deleting elements, especially in the middle of an array, can be costly as it may require shifting elements.
2. ArrayList
Java ArrayList is a part of collections framework and it is a class of java.util package. It provides us with dynamic sized arrays in Java. The main advantage of ArrayList is, It automatically adjusts its capacity as elements are added or removed.
Key Features
- Resizable Array: ArrayList can automatically grow dynamically in size.
- Indexed Access: ArrayList elements can be accessed using indices like arrays.
- Supports Generics: It ensures type safety at compile-time.
- Not Synchronized: So have to use alternative solutions like Collections.synchronizedList() or CopyOnWriteArrayList for thread safety. To read more information on this topic.
- Allows Null and Duplicates: ArrayList allows both null values and duplicate elements.
- Maintains Insertion Order: Elements are stored in the order they are added.
// Java Program to demonstrate ArrayList
import java.util.ArrayList;
// Creating an ArrayList
ArrayList<Integer> a = new ArrayList<Integer>();
// Adding Element in ArrayList
a.add(1);
a.add(2);
a.add(3);
// Printing ArrayList
System.out.println(a);
static int[] incrementArray(int[] numbers) { int[] result = new int[numbers.length]; for (int i = 0; i < numbers.length; i++) { result[i] = numbers[i] + 1; } return result; }
int[] myArray = new int[5];
The Collection interface Selecting transcript lines in this section will navigate to timestamp in the video - [Instructor] Most data structures in Java implements the collection interface. So if you've ever even created a simple list, then you've probably used the classes that implement collection. There are several other interfaces that sits underneath this. So things like list, queue, and set all extends the collection interface. And since Java 21, there's also a new one called sequenced collection. And this provides a more uniform way of getting the first and last elements in the collection. And then there are all the concrete classes that sits underneath these that implements these interfaces. So for example, a realist implements the list interface, which extends the collection interface and PriorityQueue implements queue and HashSet implements set. These are just a couple of examples. There are actually lots more interfaces that extend collection and lots more classes that implements those interfaces. You might hear this structure referred to as the collections framework. It's the backbone of most data structures in Java, so it gets talked about quite a lot. The fact that these classes are all part of the same group of classes that stem from collection at the top is pretty handy. It means that there's a consistent API. There are only a set number of methods to remember when using all of these different classes. For example, add, remove, clear, contains, isEmpty, size and so on. These are all the same in all the different concretes implementations. So once you're used to using those methods, you can use them on loads of different concrete classes. And above the collection interface, there's actually another interface called Iterable. This is the very top of the collections framework. This means that any of the classes in the framework can be iterated over using an iterator object if you want to. There are lots of differences between collections and arrays and Java. For example, collections can change in size and you don't have to specify when you create them how many items will be in it, so it can grow bigger over time or become smaller as elements are removed. They also can't hold primitive types.
------------------------------------
LinkedLists Selecting transcript lines in this section will navigate to timestamp in the video - [Instructor] The first data structure from the collections framework I'm going to look at is the LinkedList. This is an interesting one because it's doubly linked, which means that each elements in the list has a reference to the next element and the previous elements. So let's see what it looks like by creating a simple shopping list using a LinkedList. To do that, I do LinkedList. And then in a pair of diamonds brackets, I need to put the type of elements that's going to be in the list. So if I want string to be in my LinkedList, I put string. And then I can give it a name. So I'm going to name this one shoppingList and I can do equals new LinkedList. So now I've got a new empty LinkedList and the next thing is to add some items to it. To do that there's a method called add, so I can do shoppingList.add, and then I'm going to pass in the string apple. Then I'm going to add a few more shopping items. So I'm going to do shoppingList.add and pass in banana, and then shoppingList.add and I'm going to pass in pear. So let's print this out and see what it looks like at the moment. So I'm going to do system.out.println and pass in shoppingList. And I'm going to run this now and see what I get. So in the output down here, I can see I've got a list with three items in it, apple, banana, and pear. I notice that they're in the same order that I added them in the list. So LinkedLists keep items in the same order. Now let's say I wanted to add an item as second place in the list, so not at the end, but after apple and before banana. I can do that with LinkedLists by using the add method again. So I can do shoppingList.add, and then I'm going to put the index where I want the element to go. LinkedLists start at index zero. So in this example, apple is at index zero and banana is at index one. And I want my new items to be an index one. So I'm going to pass in one and then the name of the item. So I'm going to add a mango. Now I'm going to print this out again. So I'm going to do system.out.println and pass in shoppingList again and rerun it. And now I can see I've got a mango in second place. So it's apple, mango, banana and pear now. LinkedLists are quite quick at adding elements. Like I've just done there. They're quicker than ArrayLists for adding elements and removing them. ArrayLists look really similar to LinkedLists, but behind the scenes, ArrayLists actually raised, like get resized. Whereas on the other hand, a LinkedList is a test of elements where each is linked to the other one. So in this example, the banana has a reference to the pear which comes next, and it has a reference to the mango, which comes before it. And that's changed since I added the mango. So before banana has a reference to apple which is coming before it. So it had to update that reference when I inserted mango. This means that LinkLists are a bit slower, randomly accessing elements because it has to go through and see what one comes next until it gets to the one at once. So ArrayList are quicker for randomly accessing elements, but LinkedLists are quicker for adding and deleting elements from the list. LinkedLists also comes with some handy methods called addFirst, addLast, removeFirst and removeLast to add or remove elements to the front or the back of the list. So I'm going to give a go with the remove fast method. So I'm going to do shoppingList.removeFirst, and then I'm going to print out the list again, see what's in it now. So I'm going to do system.out.println shoppingList. And when I rerun it, I can see that it's removed apple from the front of the list. So now it's just mango banana and pear. One last thing to know about LinkedLists is they aren't synchronized, which is a good thing in terms of performance and memory and things like that. But it does mean that it's not thread safe. So if you've got multiple threads trying to modify the list at the same time, they might overwrite each other's changes. Luckily, it's really easy to make LinkedLists synchronized, and I'll show you how to do that now. So I'm going to create a new list. So I'm going to do List string and diamond brackets again, and I'm going to call this one synchronizedShoppingList. And I just need to make sure that I've imported the list class and then I can do equals and on the right side, I'm going to do Collections.synchronizedList, and then I can pass in shoppingList. So this will make a copy of the shopping list, but put it in a list that is synchronized. So if I print this out and I do system.outdoorprintln, synchronizedShoppingList and rerun the program, I can see my new list, SynchronizedShoppingList is exactly the same as the old one. So it's made a copy of it, but now it's thread safe and I can just continue using it like a normal LinkedList.
.....................................
Stacks Selecting transcript lines in this section will navigate to timestamp in the video - [Instructor] The next data structure we're going to look at, is the stack. Stacks are data structure, where the first element you add to it, is the last one you take out. So you can think of it like a real life stack of plates. When you stack plates on top of each other, when you want to pick one up, you would take it from the top of the pile. And the first one you put down stays at the bottom. There's actually a couple of different ways to create a stack in Java. And neither of them are perfect. There is a stack class, but it has a few limitations. For example, it lets us remove elements from anywhere in the stack. If you imagine a real life stack of plates, this isn't very stack-like behavior. So it's generally recommended to use the deque interface instead. So I'm going to demonstrate using a deque here, but it is worth being aware of the stack class, because you might come across it in older code. So, to create my stack, I'm first going to type deque, which is about D-E-Q-U-E. And then in a pair of diamond brackets, I put the type that's going to be in the deque, say I'm going to put string, and I'm going to call it 'Stack.' And then after the equal sign, I'm going to put new. And then I can't put deque, because deque is an interface. So I need to put a concrete type. And the name of the concrete type I'm going to be using, is called ArrayDeque. So now I want to add some things to my stack. The method for adding things to a stack, is called push. So I'm going to do stack.push, and I'm going to pass in the string first request. So when you're using a stack, you might have a load of requests, where you want to make sure that the last one you add to the stack, is the first one that gets processed. And then I'm going to do stack.push and put second request. One more. I'm going to do stack.push and pass in third request. So now let's print out and see what it looks like. So, I'm going to do system.out.println, and pass in stack. So if I run it now, I can see I've got three objects. And the last one I added third request is first, and then second request, and then first request. So it's in reverse order to the order that I added them in. If I did this using the stack class, it would actually print out the elements in the opposite order. So, the first request would be on top, and the third request would be last. Again, this isn't really how stacks should behave. So, is another reason to use the deque interface instead. Now, the method to get the top elements of the stack is called peek. So I'm going to do system.out.println, and pass in stack.peek, to get the first element. And when I rerun it now, I get back third request because that's the item on the top of the stack. So, if I want to remove the first element from the top of the stack, I can use a method called pop. So I'm going to do stack.pop, and then another system.out.println. And I'm going to pass in stack again, to see what the stack looks like now. So if I run this again, I can see that third request has been removed from the top of the stack. So now, I've just got second request, first request. You can also use a method called poll, which is very similar and pretty much does the same thing. So if I do stack.poll, and then another system.out.println and pass in stack. When I rerun it, it's removed the top elements again. So now, I'm just down to one thing, first request. The only difference between poll and pop, is when you use pop on an empty key, it will throw a no such element exception. Whereas if you do that with poll, it will overturn now. One last thing to bear in mind is that ArrayDeque is not thread-safe. This means that it's much faster than the stack class, which is synchronized. But, it is something to be aware of. If you use it in a multithreaded context.
----------------------------
Queues Selecting transcript lines in this section will navigate to timestamp in the video - Now let's look at the queue data structure. In a queue data structure, the first thing you add is the first thing you take out. Think of it like a real queue of people waiting outside a store. The first person that joins the queue is the first person that gets served. So like with stacks, there's actually multiple ways to implement a queue in Java, in fact, there's lots of ways. But the good news is that when you know how to do it with one concrete class, it's very similar for all of them. Because they all implement the Queue interface in Java, the methods they have are largely the same. So, when you choose which one to use, you don't have to worry about learning a whole new sets of methods. You can just worry about what specific features you want your queue to have. One way to make a queue is with an ArrayDeque, which is the same class I used to create a stack in the previous video. So I'm going to demo using this ArrayDeque class again. To create my queue, the first thing I'm going to do is type queue. And then in the pair of square brackets, the type of elements in the queue. So I'm going to put string and I'm going to call this queue. And I just need to make sure that I've imported the queue class. It is important to use queue on the left side of the assignment, because that makes it easier to change which concrete type you use later on, if you want to. It also makes it less likely people will accidentally use methods that aren't queue related, because they might then inadvertently change the behavior to not be queue-like. So on the right hand side, I'm going to put the concrete type. I'm going to use a ArrayDeque, so I'm going to put new ArrayDeque. The methods to add items to a queue is called offer. So I'm going to add three people to the queue, person one, person two and person three. And to do that, I do Queue.offer and then person one, and then Queue.offer again and person two and then queue.offer and person three. So now I've got three people in my queue, let's print it out and see what it looks like. So I'm going to do system.out.print line in person queue. And when I run this, I can see I've got person one, person two and person three. So the first thing I added is at the front of the queue and then person two, and then person three. The last one I added is the last thing in the queue. Now I want to see the item that's first in the queue. So similar to the stack example, I'm going to use the peak method again. So I'm going to do system.out.print line Queue.peak and rerun it. And this tells me that the first thing in the queue is person one. Now let's say I want to remove the first item, to do that I can do queue.poll, and I'm going to print it out again. So I'm going to do system.out.print line and person queue and rerun it. And it's removed person one from the front. So now I've got person two and person three. Unlike stack there's no pop method. So this time I have to use poll. Now, I could actually change this ArrayDeque class to some other concrete implementation. For example, I could change it to LinkedList, so let's change it to LinkedList. And I don't actually have to make any changes at this point, if I run it again. I can see the output's still the same. So I've got a list of person one, person two, person three. And when I do Queue. Peak to get the first item, it gives me person one. And then when I do Queue. Poll to remove the first item, I still got person two and person three. So everything is exactly the same. And LinkedList is quite a common implementation to use for a queue. But in most cases, the ArrayDeque has better performance. Linkedlist is better if you're removing the current element during iteration though. Another option I could change it to is something called priority key. So I'm going to change Linkedlists to priority key. And let's run it again and see what happens. So this one is slightly different. So I've got person one, person two and person three. And then when I get the first element again as person one, but when I remove that element, what I've got left is person three and person two. So person two and person three have swapped places. What's happening here is with a priority queue, the retrieval order is the natural order. So for strings, it's done alphabetically. So person one is still first because it's first alphabetically, but person three comes before person two alphabetically. So the order's actually person one person three person two. So when I remove the first element, it removes person one, but it leaves person three and then person two, because it's done it alphabetically. If it was a queue of numbers, even if you put the numbers in a random order, the first ones to be retrieved will be the lowest. And the last one will be the highest number. So that's what priority queue is for. But for this demo, I'm going to put this back to a ArrayDeque because it's one of the more common implementations.
;;;;;;;;;;;;;;;;;;
TreeSets Selecting transcript lines in this section will navigate to timestamp in the video - [Instructor] Next up, we're going to look at tree sets. Tree sets are data structure that store unique elements in a sorted order. So let's see what that actually looks like. I'm going to create a tree set. So the first thing I want to do is I'm going to type set. It's good practice to use the parent's type on the left hand side. So that means that if you change your mind about which concrete type to use later, you can just change the right hand side and leave the left hand side as it is. So I'm going to type set the interface and in diamond brackets, I'm going to put the type of elements that's going to be in the set. So I'm going to create a tree set of integers, so I'm going to type integer and I need to make sure that I've imported the sets as well. And I'm going to call this one tree set, then I'm going to do equals new tree set. So on the right hand side, I've put the concrete type tree set. Now the methods add elements to a tree set is called add. So I'm going to do tree set dot add one to add the number one to my sets. And then I'm just going to go ahead and add some more random numbers. So let's do tree set dot add 300, tree set dot add 47 and tree set dot add, let's go six. Now I'm going to go ahead and print this out to see what it looks like. So I'm going to do system dot out dot print line and pass in tree set. So let's run this and see what I get. And I can see I've got 1, 6, 47, 300. So it's not put them in the order that I added the elements in, but it's put them in ascending order from lowest to highest. So one up to 300. One of the key features of the tree set is that it stores elements by defaults in ascending order. So if a number it would store them going up with the smallest first and the largest at the end. Another feature of tree sets is that you can't store duplicate values. So let's give that a go and see what happens. So I'm going to add a new line and do tree set dot add, and I'm going to try adding another six. Then I'll do another system dot out dot print line and pass in tree set again and run it again. And I can see I've still got 1, 6, 47, 300. So there's still only one six in that, even though I tried to add another one. Now I'm going to try creating a tree set of strings and see what that looks like. So I'm going to do sets and in my diamond brackets, I'm going to put string and I'm going to call this one word set. Then I'll do equals new tree set. I'm going to go ahead and add some animals to this one, so I'm going to do word set dot add and pass in tiger, word set dot add and pass in giraffe and word set dot add and I'm going to pass in bear. Now I'm going to print it out and see what's I get. I'm going to do system dot out dot print line and pass in word set and run the app again. And I can see us put them in alphabetical order this time. So it's gone bear, giraffe tiger, because bear comes first alphabetically and tiger comes last. I can also define a different way to order strings if I want to. Say for example, I could order these ones by length instead. To do this, I'm going to put something inside the constructor for the tree set. I'm going to type Comparotor with a capital C dot comparing, and I'm going to pass in a string and two colons and length. So this is telling it to sort to the words by the length of them rather than alphabetically. So let's go ahead and run this again. And now I can see it's bear, tiger, giraffe because bear has four letters, tiger has five letters and giraffe has seven letters. Now let's see what happens when I add another animal. So I'm going to do words set dot add and pass in wolf. So, wolf has four letters in it. So I'm expecting it either to come before bear at the beginning, or maybe after bear in between bear and tiger because bear and wolf both have four letters. Now let's print out the word set again, so system dot out dot print line and pass in word set, and I can see that unexpectedly wolf actually isn't in their at all. I've got bear, tiger and giraffe though, but even though I've added wolf, it's not appearing. This is because wolf has four letters and bear also has four letters. And when I'm comparing strings by length, the tree set is counting that as a duplicate. So in this case, it's not including words with the same length. I can also remove elements from a tree set by using the remove method. So let's try removing giraffe. So I'm going to do word set dots remove and I just pass in the string giraffe, and I'm going to print it out again. So I'm going to do a system dot out dot print line and pass in word set and run the app again. And now I can see I've just got bear and tiger so it's removed the giraffe elements.
static TreeSet<String> createSortedTreeSet( String word1, String word2, String word3) { TreeSet<String> set = new TreeSet<>(Comparator.comparing(String::length)); set.addAll(Arrays.asList(word1, word2, word3)); return set; }
Asymptotic Analysis of Algorithms
Asymptotic analysis helps evaluate the efficiency of an algorithm by examining how its execution time or memory usage grows relative to the input size.
- Big O Notation: It is used to describe the upper bound of an algorithm’s runtime in terms of its input size.
- Best, Average, and Worst Case: These terms refer to the performance of an algorithm in the best, average, and worst scenarios.
- Analysis of Loops and Recursion: Loops and recursive functions are key to understanding time complexity in algorithms.
No comments:
Post a Comment