Strings: Why Text Needs Its Own Data Handling, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.8 Free with a free account

Strings: Why Text Needs Its Own Data Handling

Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.8 · lesson 74 of 879 min · free with a free account

← Sorting and Selection in PracticeNext lesson: Pattern Matching: Finding a Word Inside a Text →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

How Java stores, compares, and builds text efficiently.

  • Explain why Java strings are immutable and why equals, not ==, compares text
  • Use StringBuilder to build and edit text efficiently
  • Predict the result of compareTo from character codes
  • Recognize quadratic string patterns in loops and replace them

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,193 words). Read along, or search it.

Opening Question

Why file10 Sorts Before file2

Here are three file names: file2, file10, and file1. Let's ask Java to sort them. The result: file1, file10, file2. Ten lands before two. No person would sort them that way. So why does Java? The answer is in how text is stored and compared. A string looks like an array of characters, but text has needs of its own.

What Text Needs

Comparing, Joining, Converting, and Encoding

Text has to compare in dictionary order, be glued together and cut apart, and convert to and from numbers. It serves as a lookup key in maps, and it has to cover every writing system on Earth. Java's String class is shaped by these needs.

Immutability

Strings Never Change After Creation

A Java String is immutable: once it's created, its characters can never change. Methods that seem to change one, like toUpperCase, or the plus operator, build a new string, and leave the original alone. Run it. The old name still reads cat. The upper-case copy is CAT, and s now names a new string, cats. Next, two equal literals share one object, so double equals says true. But a string made with new is a separate object, so it says false. Double equals asks whether two names point to the same object. To compare the text itself, always use equals. Why immutable? A string can be shared freely, and a map key keeps the same hash code for life, which the hash tables of chapter 14 rely on.

Quick Check

A Discarded toUpperCase Result

Quick check. This program calls toUpperCase on x, then builds y by adding an exclamation mark. What does it print? Pause and predict. It prints data, then data with an exclamation mark. The call built an upper-case copy, but nothing kept it, so it was thrown away. x still names the original. To keep the change, assign it: x equals x dot toUpperCase.

StringBuilder

Editing Text in a Changeable Buffer

So how do we edit text without making a new string each time? A StringBuilder keeps its characters in an array it can change. Edit the builder as much as you like. Then call toString once, at the end, to get the final String. Run it. Append gives cats. Insert at the front gives big cats. Set the first character, and it's a capital B. Delete index three, and the space goes. Reverse turns the whole text around. Appending is cheap. But insert and delete shift every later character, so they cost order n.

Capacity Growth

Why Appending Costs Order One

Why is appending cheap? A new builder has room for 16 characters. When it fills, Java allocates an array about twice as large, and copies the characters across. It's the same trick a resizable list uses. This program appends a hundred thousand characters, and counts each time the buffer is replaced. Capacity runs 16, 34, 70, 142, and on. A hundred thousand characters needed only 13 reallocations. The total copying stays under about twice the final length, so each append costs order one, on average. Inserting at the front is different. In one test, a hundred thousand front inserts took about 136 times as long as the appends.

Characters

Chars Are Numbers

Characters are numbers. A Java char is a 16-bit code. Letters are numbered in alphabetical order, and digits in numeric order. So arithmetic on them means something. The digit character seven, minus the character zero, is the number seven. c minus a is two. And a plus three, cast back to a char, is d. Capital A is 65, and lower-case a is 97. Every capital letter has a smaller code than every lower-case one. Unicode gives every character a code point, over 1.1 million of them. A single char holds only codes up to 65,535. A bigger one, like the smiling-face emoji, takes two chars, called a surrogate pair. So length reports four for a three-character string. Code point count reports the true three.

Comparison

Dictionary Order by Character Code

Strings compare like words in a dictionary, but by character code. Scan from the left until they differ. The smaller character there decides. If one string runs out first, it's a prefix of the other, and it comes first. compareTo returns a difference, so negative means the first string comes first. Apple against apricot gives minus two, since p is two less than r. Capital Apple against lower-case apple gives minus 32. App against apple gives minus two, the difference in lengths. And the string 10 comes before the string 9, since the character 1 is smaller than 9. Sort seven words in this natural order. Digits come first, then capitals, so Zebra lands before apple. Ignoring case puts Zebra last.

Answer

The File Names Explained

And that answers the file names. file10 and file2 first differ at their fifth character: one against two. One is smaller, so file10 comes first. The number ten never enters into it. A rule that sorts the way people expect has to read each run of digits, as one whole number.

Quick Check

Sorting b9, B2, and b10

Quick check. Three tags: b9, capital B2, and b10. Arrays.sort uses the natural order. What order comes out? Pause and predict. Capital B2 first, then b10, then b9. Capital B has a smaller code than lower-case b. Then b10 and b9 differ at the second character, and one is smaller than nine. Numeric value never enters into it.

Hidden Cost

Plus-Equals in a Loop Is Quadratic

Because a string can't change, an operation usually costs as much as building its result. length and charAt are constant time. substring copies the piece it returns. And plus builds a new string holding both sides. A single expression, like hello plus a name, is fine. The trouble is repeating s plus-equals x inside a loop. Every pass copies all the characters so far. After n passes, that's n times n plus one, over two characters: quadratic. In one test, 10,000 appends with plus-equals took 16 milliseconds. 200,000 took about 2.9 seconds: 181 times longer, for 20 times the work. A StringBuilder did the 200,000 in under half a millisecond.

Better Loop

Walk With an Index, Not Substring

The same trap hides in substring. Chopping off the first character, again and again, copies everything that's left on every pass. Walking with an index copies nothing. Both loops here add up the same character codes, and they print the same total. In one test on a hundred thousand characters, chopping took about 638 milliseconds. Walking took a quarter of a millisecond.

Everyday Tasks

Reversing, Palindromes, Counting, and Parsing

With these tools, most everyday text tasks take one pass. A builder reverses stressed into desserts. A palindrome test compares characters from both ends, moving inward. With spaces and case removed, never odd or even reads the same both ways. Letter counts use an array of 26, where the character itself picks the counter. Mississippi has four i's and four s's. Split cuts a sentence into words, here six, and join glues them back with dashes. Parsing builds a number digit by digit: ten times the value so far, plus the next digit. Adding one proves it's a real number. And parseInt rejects text that isn't a number, with a NumberFormatException.

Key Takeaways

Java Strings in Brief

To sum up. Strings are immutable. Compare them with equals, never with double equals. Build text in a StringBuilder: appending costs order one on average. Chars are numbers, and comparison goes character by character. So 10 sorts before 9, and capitals before lower case. Plus-equals and substring in a loop are quadratic. Walk with an index instead.

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

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

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 UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks 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 Strings: Why Text Needs Its Own Data Handling

What is the difference between == and equals for Java strings?
In Java, == checks whether two references point to the same String object, while equals compares the characters themselves. Two equal string literals share one object, so == happens to return true for them, but new String("cat") == "cat" is false even though the text matches. To compare text, use s.equals(t), or equalsIgnoreCase when letter case should not matter.
Why are strings immutable in Java?
Java strings are immutable, meaning their characters never change after creation, so they can be shared safely. Methods such as toUpperCase and the + operator build a new string and leave the original alone, which is why calling x.toUpperCase() without assigning the result changes nothing. Immutability also means a string used as a map key keeps the same hash code for life, which hash tables rely on.
Why does Java sort file10 before file2?
Java compares strings character by character using character codes, not numeric values. The strings file10 and file2 first differ at the fifth character, where 1 has a smaller code than 2, so file10 comes first. The same rule puts capital letters before lowercase ones, since A is 65 and a is 97. Sorting the way people expect requires reading each run of digits as a whole number.
Why is using += to build a string in a loop slow?
Using s += x in a loop is slow because each pass copies every character built so far into a new string, which makes the total work quadratic. After n single-character appends, about n(n+1)/2 characters have been copied. In one test, 200,000 appends with += took about 2.9 seconds, while a StringBuilder did the same job in under half a millisecond, since its appends cost order one on average.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

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.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →