UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 11.2 Free with a free account
Positional List Operations
Data Structures and Algorithms · Chapter 11: Dynamic Lists, Iterators, and the Collections FrameworkSection 11.2 · lesson 45 of 8710 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: Visiting Every Element of a Collection One at a Time →← Collections That Grow as Elements Are AddedNext lesson: Visiting Every Element of a Collection One at a Time →
In this lesson
Reading, inserting and removing Java list elements by index.
- Apply get, set, add, remove and indexOf with the correct index ranges
- Distinguish remove by position from remove by value on a List of Integer
- Compare the cost of positional operations on ArrayList and LinkedList
- Use subList as a half-open view and explain when it stops working
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,462 words). Read along, or search it.
Opening Question
Every Element Has an Index
In a theater, every seat has a number. A ticket for seat twelve takes you straight there, without visiting seats one to eleven. A list works the same way. It's an ordered sequence, and every element has a position, called an index. Operations can name the position they want. Java's List interface gathers these positional operations, and both ArrayList and LinkedList provide them. The calls look identical on both. So why can the same loop be instant on one, and painfully slow on the other?
Core Operations
Get, Set, Add, Remove and Index Of
A list remembers the order elements were placed in, and allows duplicates. Get reads the element at position i. Set replaces it, and returns the element it replaced. Add x appends at the end. Add with a position inserts there, and every element from that position onward moves one place later. Remove at a position takes that element out and returns it, and the later elements move one place earlier. Index of finds the first position holding a value, or minus one.
Valid Index Ranges
Elements Versus Slots Between Them
Notice one detail. Reading, replacing and removing work on an element, so the index must name an existing one: zero up to size minus one. Inserting works on a slot between elements, so its index may also equal size, which means at the end. So with three elements, get accepts zero to two, but add with a position accepts zero to three. And for an empty list, add at zero is valid, while get has no valid position at all.
Worked Example
Tracing Every Positional Operation
Here's every operation in turn. Three adds give Ana, Ben, Cy, and get of one reads Ben, at index one. Set of one to Bo replaces Ben, and hands Ben back. Add at zero puts Zed at the front, so Ana, Bo and Cy each move one place later. Add at size appends End. Remove at two takes out Bo, and returns it. Cy and End move one place earlier. Index of Cy is now two, and index of Nobody is minus one. Never pass that minus one on to get or remove: it isn't a valid position. Add another Cy at the end, and index of gives the first match, two, while last index of gives the last, four. The variable is declared as a List, while the object is an ArrayList. So switching to another kind of list later means changing one word, where the object is created.
Quick Check
Insert, Remove, Then Set
Quick check. A list holds P, Q, R. Insert X at position one, remove position two, then set position zero to Y. What does printing the list show? Pause and predict. It shows Y, X, R. Inserting X at one gives P, X, Q, R: Q and R move one place later. So position two now holds Q, and that's what remove takes out. Set then replaces P with Y. Y, Q, R forgets that the insert shifted Q. And Y, X, Q removes R, the element that was at position two before the insert.
Common Mistake
Remove by Position or by Value
Now a trap. A list of Integer objects has two methods named remove. Remove with an int removes by position. Remove with an object removes the first equal element. Pass a plain int, and Java picks the position version. So remove of one, on ten, twenty, thirty, one, two, removes twenty: position one, not the value one. Only remove of Integer dot value of one removes the value. Mix them up, and the wrong element silently disappears, with no error at all.
Error Handling
Index Out of Bounds Exceptions
A position outside the valid range throws an index out of bounds exception. This program catches each one, and prints its message, on a list of a, b, c. Get of three, get of minus one, and remove of five all fail: index three out of bounds for length three, and so on. Add at three is allowed, because three is the size: the list becomes a, b, c, d. But add at six, with size four, fails. And a LinkedList words it differently: index three, size three. The wording varies, but the rule doesn't. Two habits prevent most of these. Guard an index that comes from outside: check it's at least zero and below size. And check index of before you use it.
Cost Comparison
Array Storage Versus Linked Nodes
Both types implement List, so all of this code works with either. What changes is the cost, because they store elements differently. An ArrayList keeps its elements in an array, so the element at any index is found by direct calculation: get and set are order one. But inserting or removing in the middle shifts every element after it. A LinkedList keeps linked nodes. No elements move, but reaching position i means following links from the nearer end: up to about n over two of them. So get is order one against order n. Adding at the front flips it: order n against order one. And inserting in the middle is order n in both.
Measured Results
Timing a Hundred Thousand Elements
Here's what that looks like, measured on one machine with lists of a hundred thousand numbers. The exact milliseconds will differ on yours. The pattern won't. Twenty thousand gets in the middle: about two milliseconds for the ArrayList, over three seconds for the LinkedList, which walks about fifty thousand links per call. Inserting at the front reverses it. The ArrayList shifts a hundred thousand elements each time. And inserting in the middle is order n in both, yet the ArrayList still wins by a wide margin. Shifting is one fast block copy, while walking links jumps between scattered objects. Big O hides those constant factors.
Practical Advice
Default to ArrayList
So default to ArrayList. It wins at positional reading and writing, and it's competitive nearly everywhere else. Consider a LinkedList only when most of the work is adding and removing at the ends, and positional access is rare. And never write a loop of get i calls over a LinkedList. Every call walks from an end, so the loop slows down badly as the list grows.
Sublist Views
A Half-Open Window Onto the List
Finally, sublists. Sub list from, to, returns a view of part of a list. The range is half-open: from is included, to is not, so the view's size is to minus from. The key word is view. A sublist copies nothing. It's a window onto the original, so changes made through the window show up in the original. Sub list two, five covers Wednesday, Thursday and Friday. Setting its first element to capital WED writes through to days. And clearing the view deletes those three days from the original, in one step. For an independent copy, pass the sublist to a new ArrayList. Adding extra to the copy leaves days unchanged. One rule surprises people. Change the original's size after making a view, and the view can no longer be used: asking its size throws a concurrent modification exception.
Edge Cases
Empty and Invalid Sublist Ranges
A few more sublist rules. Sub list one, one is allowed, and empty. From larger than to throws an illegal argument exception. A to larger than the size throws an index out of bounds exception. So use a sublist right away, or copy it.
Quick Check
Clearing a Sublist View
Quick check. A list holds one through six. The program takes sub list one, four, and clears it. What does the list print afterward? Pause and predict. It prints one, five, six. Sub list one, four covers positions one, two and three: the values two, three and four. The four is excluded. Because the sublist is a view, clearing it removes those three from the original list. The unchanged list assumes the sublist was a copy. And one, six treats the range as closed, removing position four as well.
Fixed Lists
Lists That Refuse Some Changes
Two kinds of list look normal, but refuse some changes. Arrays dot as list wraps an array. Set works, giving x, b. But add throws an unsupported operation exception, because the size is fixed. List dot of builds an unmodifiable list, so even set throws the same exception. When you need a fully changeable list, wrap either one in a new ArrayList.
Key Takeaways
Positions, Costs and Views Summarized
To sum up. Get, set and remove take positions zero to size minus one, while add with a position takes zero to size. Set and remove return the old element, and index of returns minus one when the value is absent. On a list of Integer, remove of an int removes by position. ArrayList reads and writes by position in order one. LinkedList needs order n, because it walks links. And sub list is a half-open view: changes pass through, and changing the original's size breaks it.
Think About It
Swapping ArrayList for LinkedList
Something to think about. A program reads every element of an ArrayList with a loop of get i. A teammate changes the object to a LinkedList: one word. It still compiles, and gives the same answers. What happens to the running time as the list grows? And what does that say about coding against the List interface?
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 Positional List Operations
What is the valid index range for get versus add in a Java List?
Why does list.remove(1) remove the wrong element from a List<Integer>?
Is get(i) faster on an ArrayList or a LinkedList in Java?
Does subList in Java return a copy of the list?
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 →