Inserting into and deleting from lists is kind-of integral to the whole "using lists" thing. If you can't put things in or take things out, you've got a useless data structure on your hands.

But before we show you how that works in lists, we've got a couple of questions for you. Nothing bad, we promise. (Or maybe it is bad, depending on your definition of what's bad. It isn't as invasive as a colonoscopy, so at least we can promise you that.)

And with an introduction like that, we're sure you're raring to go with these questions.

Anyway.

Do you think it's harder to take something out of (or put it back from)

• the end of the bookshelf or the middle of the shelf?
• the ends or middle of a package of sliced cheese?
• the ends or middle of Pandora's Box?

Aside from maybe the infeasibility of putting anything back in Pandora's box once it's opened, it's easier to grab things from the side than from right in the very middle. When you're dealing with bytes instead of actual books or cheese, adding or removing things from a list takes time. This time, though, when you talk about adding and removing things, you're usually dealing with huge chunks of data.

That makes a huge difference.

Barring some sort of situation where you get thrown into the world of infomercial people, it takes about the same amount of time to add a book to the side of a shelf as it does in the middle—even if adding in the middle might technically take longer. It's the same for removing a slice of American cheese: the difference in time is negligible. In computer science? Not so much.

We'll walk through each type one by one really quickly, just to give you a sense of how they're different.

Arrays

Arrays are some of the easiest data structures to insert or delete from, but only when you're dealing with the end of the array (largest memory address). Inserting and deleting from the front or middle of the array takes a little more…work.

As long as you know the index of the last element and have the space to throw in another element, all you need to do is throw that new element into the next index. If you don't know that index, just walk through your array, one element at a time, until you reach an index that doesn't have an element. Then insert the element there.

Yep, it really is that easy.

 

 

Deleting from the back? That's even easier. You don't need to worry about space in the array to remove an element. Just find that final element either by traversing or using whatever method you have and remove it (usually by setting it to null). According to the array, the space still exists in the array, but the element itself is gone. You could put something new in there now if you want to.

 

 

Done.

Now comes the trickier parts: messing with elements at the front or the middle of an array.

If you create a new element for array[x], if an element at x already exists, you need a way to keep that element. If you just replace it, it'll get lost, but if you displace it—and everything after it—you won't lose any data.

Just like last time, make sure there's enough space in your array to fit another element. If there is, shift the entire array from the place you want to throw an element in down by one index/address in computer memory.

If you're inserting at the front, the element at array[0] is moved to array[1], array[1] is moved to array[2], and every other element gets one added to their index value.

If you're inserting at array[12], array[12] moves to array[13], array[13] is moved to array[14], and…you get the idea.

If you're into generalizing things, you could say that array[x] is copied to array[x + 1] for all x greater than or equal to the index where an element needs to be inserted.

 

 

If you're using a loop to run through and move those elements instead of moving them manually (which is a much better idea in our books, TBH) start from the last element and move it into the next empty space. Then move to the one before it and move into the new empty space. Just copying over array[x] into array[x + 1] is going to overwrite whatever used to be in array[x + 1].

Alternatively, you can create some temp variables to store the value before you overwrite it. That would let you move through the array, working from the empty space to the end. Just make sure you're keeping track of your variables. Otherwise…you could lose half your array.

 

 

 

Deletions also involve moving elements around, but instead of making space for a new element, we're filling the gap a removed element created. If you're deleting the front, the element at array[1] now becomes the new front of the array at array[0]. If you're deleting array[32], every other element after it gets moved up by one index (array[33] becomes the new array[32]). More generally, array[x]is copied to array[x - 1] whenever x is greater than or equal to the index of the deleted element.

 

As long as you start from the deleted element, you don't have to worry about storing array values while they're being moved around. If the deleted element is at array[2], all you have to do is move array[3] into its spot and boom. It's deleted. Basically, the exact thing you didn't want to happen during insertion is the same destructive power you can take advantage of for deleting an element.

In this case, 43 is replaced with 46, the copy of 46 becomes 51, and the copy of 51 becomes 54.

 

Whether you're using primitives or pointers, this process should always work for deleting an element.