Welcome back! Today we're going to wrap up our discussion of lists. First, we'll make some forward progress on our linked list implementation. Then, we'll compare and contrast the two performance of our two approaches.
At this point we can initialize our linked lists and get and set items. But what about add and remove? It's not a list yet!
Both add and remove require adjusting the linkage to either insert or delete elements. This is tricky! Let's start with remove. First, let's look at what needs to happen using a diagram.
OK, now let's take a stab at this in code!
What about add? We'll leave that for you to work on... But, to help you get started, let's diagram it first:
Let's examine the performance tradeoffs of our
ArrayList versus our
Now, you might be wondering why anyone would use a linked list, ever! However, there are applications that only ever modify the ends of the list!
For example, consider a help queue. Requests are added at one end and removed from the other. So we are only ever modifying the front or the end of the list.
Modifying the front of a linked list is
But what about the end?
Could we make that
Let's see how.