Join Simon Allardice for an in-depth discussion in this video Resizable arrays, part of Programming Foundations: Data Structures (2014).
As opposed to, and immutable or unchangeable one. Now, here's a couple of examples of this. In Java, the standard array is fixed-size and a fixed data type. So, it's an array of integers or an array of Booleans. Java being an object oriented language, you can also create arrays of objects like strings. But for a resizeable version, Java offers a couple of classes, the best known being the ArrayList. So instead of creating an array we create an ArrayList object. There's a different kind of syntax. As ArrayList is not baked into the core language itself.
It will require us to link to an external framework and instantiate this as a regular object. ArrayLists can be created totally empty, or given an initial capacity, even some initial values. But after this ArrayList is created, and I've called this object resizable. We can use methods to add to it, which we simply can't do with the standard array. And we also have methods to remove from it. As the equivalent example in Objective-C. Well, Objective-C is built on top of C. So we do have the standard C-style array.
But, in day-to-day usage it's much more common for Objective-C developers to use the class called NSArray. For dealing with arrays of objects. Now if you're new to Objective-C, again, don't worry about the syntax here, this is not the point of this section. I'm simply using the shorthand that creates a fixed size array here of three strings. Now most of the common classes and behaviors in Objective-C programming have this NS prefix. It's a throwback to when Objective-C was developing the next step operating system that the Macintosh OS is built on.
So this NSArray, like the standard Java Array, is also fixed size. It's an immutable array. You can create it to hold as many objects as you need, but you can't add or remove once it's been created. But just as Java has the array, and the array list, on Objective-C we have NSArray, and NSMutableArray. Which behaves identically to NSArray, but adds additional methods and this is a model you'll see across several programming languages. The data structures with what you might think of as slightly different behavior are actually implemented as completely separate classes.
Whenever adding new elements to a resizable array, we have a very important decision to make. Are we adding this new element at the very end of the existing array, are we adding it at the beginning or somewhere in the middle. Now this matters, because typically adding a new element at the end is easier, faster, and requires less work for that array to do. So if we have some kind of method or function that will just allow us to add a value, this just get's added in right at the end. With an index number one higher than the existing final index number. But on the other hand, if we have that existing array and we want to add a new item somewhere else at a specific position.
Of shuffling these items around. But just because something is happening in the background doesn't mean you can ignore the fact that this does have a performance impact. And the larger the array the more items will need to be shuffled around and re-indexed. How this re-shuffling is actually implemented under the hood differs from language to language. If the array isn't large, some will attempt to reshuffle items in place, but others will just copy the entire contents of the old array. Into a brand new array, we organizing things as they go. Now across languages, there are a few different terms for adding items to arrays.
In Python we're technically working with a data structure called a list, not an array but still the equivalent behavior is to append to the end of that list. However, if we want to add this new item not right at the end, but at a specific position in the existing array. We're not pushing onto the end anymore. We may need a different word. So in Java, the method is still just add, but we'd also provide an index for what position in the array this new item should be added. So it can re-index the other items. And Objective-C, it's still Add Object but we also need to provide an index parameter.
Pop always refers to deleting the last, the final element off an array. If you want to delete an item that's not the last element, you need some way of passing in the index numbers. So with Java, it's remove with the index parameter, with Objective-C. It's remove object at index and so on. Now okay, I get it, folks. This might seem like overkill. And if this information was only relevant for working with arrays, I wouldn't go into it as much. But this is the beginning of understanding that in all the data structure we'll encounter, there's really only five things.
Five fundamental behaviors we might need to figure out. And that's how to access, how to insert, how to delete, how to find, and how to sort. So, how do we access? How do we get to the values in this data structure? Whether that's getting to one specific element or wanting to iterate through all of them. To systematically loop through every element. Then there's how do we add a new item to this data structure? Often including, as we've seen. How we would add an item at a specific position. The flip side of that how do we delete or remove one whether from the end or this particular position.
Okay. How do we find or search that data structure to get a specific item when we don't know where it is or even if it exists at all. And finally can we sort the content of the data structure. So it's in some kind of meaningful order. And that's whether we want to sort it in place or we want another copy of it that's sorted. And these five things would cover 99% of everything you'll ever need to do with any data structure. But let me tell you folks, we often won't get all five and don't expect to For example, many data structures don't support any kind of searching behavior.
It's just a big collection, a big bucket of stuff. If you need to find something, you just programmatically go through all of it yourself. And many don't provide any kind of sorting behavior. Others are naturally sorted and can keep themselves organized. We're about to talk about the basics of sorting and searching. But as I've gone through here with these resizable arrays. And will prove to be true with many of the later data structures we've got coming up. To add a new item to a data structure will typically be some variant of the word add, inset or push and to pull a data structure.
It will be some varied word remove, delete, or pop.
Starting with simple ways of grouping data like arrays and structs, together you'll explore gradually more complex data structures, like dictionaries, sets, hash tables, queues and stacks, links and linked lists, and trees and graphs. Simon keeps the lessons grounded in the real world and answers the "why" behind many data-structuring decisions: Why use a hash table? Why is a set useful? Why avoid arrays? When you're finished with the course, you'll have a clear understanding of data structures and understand how to use them in whatever language you're programming in, today or 5 years from now.
- What is a data structure?
- Using C-style structs and arrays
- Sorting and searching arrays
- Working with singly and doubly linked lists
- Using stacks for last-in, first-out (LIFO) structures
- Using queues for first-in, first-out (FIFO) structures
- Working with hash tables
- Understanding binary search trees (BSTs)
- Learning about graphs