UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 5.2 Free with a free account
Rearranging Elements Within a Fixed-Size Collection
Data Structures and Algorithms · Chapter 5: ArraysSection 5.2 · lesson 17 of 8711 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Rows, Columns, and Higher Dimensions →← How Arrays Store DataNext lesson: Rows, Columns, and Higher Dimensions →
In this lesson
Insert, remove, swap, reverse and rotate elements inside a Java array.
- Track capacity and size separately for a partially filled array
- Insert and remove elements by shifting in the correct direction
- Swap, reverse and rotate elements in place with a temporary variable and reversals
- Estimate the cost of each operation and choose a response when the array is full
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,640 words). Read along, or search it.
Opening Question
A Late Friend Wants Seat Two
Five friends sit in a row of eight cinema seats, numbered 0 to 7. A sixth friend arrives late, and wants seat 2. Everyone from seat 2 onward has to slide one seat to the right. But who should move first? Get the order wrong, and two people land in the same seat. A program meets exactly this problem when it rearranges an array.
Key Idea
Capacity Versus Size
An array's number of slots never changes. But what sits in those slots can be moved around freely, so treat the array as a workspace. An array of length 8 can hold eight values, yet a program often has only five to store. The array itself can't tell which slots hold real data, because every slot always holds something, such as zero. So the program keeps its own count, in a separate variable usually called size. Capacity is how many values fit. Size is how many are really there.
Key Terms
What the Size Counter Tells You
Those two numbers answer every question about the array. The first free index, where the next value goes, is size itself. The last real element sits at size minus 1. The array is empty when size is 0, and full when size equals the capacity. Appending looks like this: write the value at index size, then add 1 to size. The two always go together, and data, index size plus plus, does both in one step.
Common Mistake
Looping to Length Instead of Size
The most common mistake is looping to the length of the array, instead of to the size. The slots past the size aren't data. A loop that visits them counts leftover values, as if they were real. So a total over data dot length quietly adds in the leftovers. A loop over size visits real elements only.
Insertion
Shifting Right to Make Room
Now, inserting in the middle. Say the array holds 4, 9, 1, 6, 3, and 7 must go in at index 2. The free slots are all at the end. So the program shifts: it moves each element from index 2 to the end one place right, starting with the last one. 3 moves to slot 5, then 6 to slot 4, then 1 to slot 3. Now slot 2 is free, and 7 goes in. Last, size goes up by 1. The array holds 4, 9, 7, 1, 6, 3, and size is 6.
Code Walkthrough
An Insert Method That Returns the New Size
In code, the method first checks that the array isn't full, and that p is between 0 and size. If either fails, it throws an exception. Then a loop runs i from size down to p plus 1, copying the element on its left into slot i. Then the value goes into slot p. The method returns size plus 1, because a method can't change its caller's counter. So it's called as: size equals insert, of data, size, 2, and 7.
Common Mistake
Shifting in the Wrong Direction
Why from the end? Run the loop the other way, left to right, on the same array, and watch what happens. The 1 at index 2 is copied into slot 3, on top of the 6. Then that same 1 is copied into slot 4, on top of the 3. Then into slot 5. The result is 4, 9, 7, 1, 1, 1. The 6 and the 3 are gone, because each was overwritten before it was copied. That's the cinema answer too. The friend at the end moves first, into an empty seat. Then each next person has a free seat to move into.
Removal
Shifting Left to Close the Gap
Removal runs the same idea in reverse. Removing the element at index p leaves a gap. The gap is closed by shifting every later element one place left, starting with the first one. Then size goes down by 1. Remove index 1 from 4, 9, 1, 6, 3. The 1 moves into slot 1, the 6 into slot 2, and the 3 into slot 3. The last slot still holds a 3. That's a stale copy, past the new size of 4, and it's simply ignored.
Comparison
Insertion and Removal Side by Side
Side by side: insertion allows positions 0 to size, where size itself means append. Removal allows 0 to size minus 1. Insertion shifts right, last element first. Removal shifts left, first element first. Insertion fails when the array is full or p is out of range. Removal fails when the array is empty or p is out of range. And when order doesn't matter, skip the shifting. To remove, copy the last element into the gap, and reduce the size: a single step.
Quick Check
Removing With a Backward Shift
Quick check. An array holds 5, 8, 2, 7, with size 4. A programmer removes index 1, and shifts left, but starts the loop from the end instead of the front. Afterward, what do the first three slots hold? 5, 2, 7? 5, 7, 7? Or 5, 8, 7? Pause, and decide. It ends 5, 7, 7. Starting from the end, slot 2 takes the 7 first. Then slot 1 copies slot 2, which is already 7. The 2 was overwritten before it could move. Removal must shift left starting with the first element after the gap, which gives 5, 2, 7. 5, 8, 7 would mean nothing shifted at all.
Swapping
Exchanging Values With a Temporary Variable
Next, three ways to reorder in place, inside the array, with no second array. The first is swapping two elements. Exchanging two values needs a spare place, to hold one of them while the other is copied over it. That spare place is a temporary variable. Try it without one. With 3 and 8, data i equals data j overwrites the 3. Copying back puts the 8 in both slots, and the 3 is lost. With temp, the 3 is saved first, then moved to the other slot. That's three assignments, whatever the size of the array.
Reversal
Swapping From Both Ends
Reversing a range uses two positions: i at the front, and j at the back. Swap the elements they point to, move i one step right and j one step left, and stop when they meet or cross. For 1, 2, 3, 4, 5, the first swap gives 5, 2, 3, 4, 1. The second gives 5, 4, 3, 2, 1, and the two positions meet in the middle. Each swap fixes two elements, so reversing takes only about half as many swaps as there are elements.
Rotation
Rotating With Three Reversals
Rotating left by one moves every element one place toward the front, and the first element wraps around to the back. Save the first element, shift the rest left, then store the saved value in the last slot. To rotate by k, you could repeat that k times, at k times n assignments. There's a faster way, built from reversal. Reverse the first k elements, reverse the rest, then reverse the whole range. Rotate 1, 2, 3, 4, 5 left by 2: 2, 1, 3, 4, 5, then 2, 1, 5, 4, 3, then 3, 4, 5, 1, 2. That's about n swaps in total, whatever k is. One detail: k is taken modulo the size first, because rotating by the size brings everything back.
Quick Check
Rotating Six Values Left by Four
Quick check. Rotate 10, 20, 30, 40, 50, 60 left by 4, using three reversals. Which is the final array? 50, 60, 10, 20, 30, 40? 30, 40, 50, 60, 10, 20? Or 40, 30, 20, 10, 60, 50? Pause, and decide. A: 50, 60, 10, 20, 30, 40. Reversing the first four gives 40, 30, 20, 10. Reversing the last two gives 60, 50. Then reversing everything gives 50, 60, 10, 20, 30, 40: every value moved four places left, and the first four wrapped around to the back. C is the array after only two of the three reversals. And B is a rotation by 2, not by 4.
Cost Analysis
Which Operations Grow With Size
Now count the cost, in terms of the size n. Reading or writing one element by index is a single step, and so is appending. Removing when order doesn't matter is one move. A swap is three assignments. None of these grows with n. Shifting does grow. Inserting at index p moves size minus p elements: n at the front, and none at the end. Removing at p moves size minus 1 minus p. Reversing takes about n over two swaps. Rotating with three reversals takes about n, whatever k is. So inserting at the front of 1,000 elements moves 1,000 of them. With 2,000, it moves 2,000. The work grows in proportion to the size.
Design Choice
When the Array Is Full
Last, what happens when size equals the capacity, and one more value arrives? The capacity can't change in place, so the program must choose a response. It can refuse: throw an exception, or return false. That fits a real limit, like 52 cards in a deck, but every caller must handle the refusal. It can discard the oldest: shift everything left, and store the new value at the end. That suits a recent-history list, but old data is lost, and each insertion moves n minus 1 elements. Or it can copy into a larger array, say twice the size, with Arrays dot copyOf, when every value must be kept. That costs copying n elements, and memory for both arrays while it happens. Choose by what the data means. Arrays that enlarge themselves automatically come later in the course.
Key Takeaways
Shifting, Swapping and Rotating
To sum up. A partially filled array needs a size counter, and loops run to size, never to the length. Insert by shifting right from the last element. Remove by shifting left from the first. The wrong direction overwrites values before they're copied. A swap needs a temporary variable. Reversing swaps from both ends, and three reversals rotate by any k. Index access is one step. Insertion and removal cost up to n moves.
Think About It
Dragging a Song Up a Playlist
Something to think about. A playlist app stores up to 50 songs in an array. A listener drags the song at index 40 up to index 3. Which operations from this lesson does that move need? And roughly how many songs shift along the way?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Rearranging Elements Within a Fixed-Size Collection
How do you insert an element into the middle of an array in Java?
What is the difference between capacity and size in an array?
How do you swap two elements in a Java array?
How do you rotate an array using reversals?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →