UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 6.1 Free with a free account
Why Connecting Nodes Solves Problems Arrays Cannot
Data Structures and Algorithms · Chapter 6: Linked ListsSection 6.1 · lesson 21 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: Singly Linked Lists →← Copying Arrays SafelyNext lesson: Singly Linked Lists →
In this lesson
How linked nodes avoid the fixed size and shifting of arrays.
- Explain the two main limits of arrays: fixed size and costly middle insertion
- Describe nodes, next references, the head and null as the parts of a chain
- Insert and remove nodes by relinking references in a safe order
- Compare arrays and linked chains and choose one for a given workload
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,570 words). Read along, or search it.
Opening Question
A Help Desk Waiting Line
A help desk keeps a waiting line. Customers join at unpredictable times, and some give up and leave from the middle of the line. Nobody knows in advance how long the line will get. An array handles this badly. It needs a capacity up front, and every arrival or departure in the middle moves a crowd of elements. Is there a design that never guesses a size, and never shifts a crowd? There is, and it's built from a different block: the node.
Array Limit One
Guessing a Fixed Size
The first limit is the fixed size. An array's length is chosen when it's created, so the programmer must guess the most items it will ever hold. Guess too large, and slots sit empty: room that's paid for, but never used. Guess just right, and everything fits. But that needs a perfect forecast of the future. Guess too small, and the array fills up. Then the only remedies are to refuse, to discard, or to copy everything into a larger array.
Array Limit Two
Shifting to Insert and Remove
The second limit is costly insertion and removal in the middle. In an array, an element's position is its identity. To insert in the middle, every later element shifts one slot right. To remove, every later element shifts back. In an array of 1,000 items, inserting at the front moves all 1,000. Removing the front moves 999. In the middle, it's about 500 either way. At the end, nothing moves. Both limits come from one design decision: array elements are tied to neighboring positions. A block of neighbors can't stretch, and making room means moving the neighbors.
Definition
Nodes, Next References and the Head
So connect elements by references, instead of by position. The building block is a node: a small unit with two parts. One part is the data it stores. The other is a reference to another node: a value that tells the program where that node can be found. That reference is called next. Each node knows where the next one is, so nodes joined this way form a chain. The chain is reached through a reference to its first node, called the head. It's the only way in. And the last node's next is null, a reference that points to nothing. That marks the end of the chain.
Key Difference
Order Held by References
Here's the key difference from an array: where the order lives. In an array, order is held by positions. Slot 3 comes after slot 2 because they're neighbors. In a chain, order is held by references. Node C comes after node B, because B's reference points to C. So the nodes themselves can sit anywhere in memory. Only the references say who comes next.
Traversal
Following References From the Head
The price of that freedom: there's no index to jump with. To reach a node, the program starts at the head and follows one reference at a time. That walk is called a traversal. Current starts at the head. While current isn't null, use its data, then move current to current dot next. To reach the fifth node, the program follows four references. That one fact explains most of the trade-offs ahead.
Payoff
No Capacity to Guess
Now the payoff. A chain has no capacity. When a new item arrives, the program creates one node, and links it in. When an item leaves, its node is simply disconnected. There's no guess, no empty slots held in reserve, and no moment when the structure is full. The cost is that every node carries a reference as well as its data, so each item takes more room than it would in an array.
Insertion
Relinking Two References
Because the order lives in the references, changing the order means changing references. Nothing else has to move. Take the chain A, B, D, and insert X between B and D. Two references change. First, the new node takes over B's old reference: X dot next becomes D. Then B is pointed at X: B dot next becomes X. The chain reads A, B, X, D. The order of those two steps matters, just as the shifting direction mattered for arrays.
Quick Check
Inserting R in the Wrong Order
Quick check, with a new chain: P, then Q, then S. A programmer inserts R between Q and S, but writes the two steps in the other order. First, Q dot next becomes R. Then, R dot next becomes Q dot next. What does the chain look like afterward? Is it P, Q, R, S, as intended? Does R point to itself, with S lost? Or does Q still point to S, skipping R? Pause, and decide. R points to itself, and S is lost. After the first line, Q dot next is already R. So the second line copies R into R dot next. Nothing refers to S anymore, and a walk from the head would circle on R forever. The safe rule: connect the new node to the rest of the chain first, then connect the chain to the new node.
Removal
Pointing Past the Removed Node
Removal is even simpler. To remove B from the chain A, B, C, change A's reference to point past B, straight to C. B is no longer reachable from the head, so it's gone from the chain. No element after B has to move.
Trade-Off
Cheap Relinking, Costly Reaching
But here's the catch. Relinking is cheap only once the program is standing at the right node. Reaching position 500 means following 499 references from the head. So a chain makes changing the order cheap, and reading by position costly: the exact opposite of an array.
Comparison
Where the Array Wins
Here's the honest comparison, for n items, using a simple chain with only a head reference. First, where the array wins. Reading the item at position i: one step for an array, up to i steps for the chain. Inserting or removing at the end: one step for an array with room, and about n steps for the chain, which must walk there first. And room per item: the array stores just the value. The chain stores the value, plus a reference.
Comparison
Where the Chain Wins
The chain wins elsewhere. Inserting or removing at the front: about n moves for the array, but one step for the chain, which just changes the head. Inserting in the middle, once the spot is reached: about n over 2 moves for the array, and one or two reference changes for the chain. Adding when the storage is full: the array copies all n items into a larger array. The chain just links one new node. And searching for a value is a tie: up to n comparisons, either way.
Worked Numbers
Inserting After Position 500
Put numbers on it, with 1,000 items. Insert after position 500, starting from the head. The chain needs about 500 steps just to reach the spot. That's about what the array pays in shifting, so it's a tie. The chain wins big only when the program is already at the spot, for example while it scans through and inserts as it goes, or when the change is at the front.
Quick Check
A To-Do App That Inserts While Scrolling
Quick check. A to-do app keeps a list of tasks. As the user scrolls, the app inserts a new task right after the one on screen. Tasks are never looked up by number, and the list grows and shrinks all day. Which design suits it best: an array, a linked chain, or would it make no difference? Pause, and decide. A linked chain. The app is already standing at the spot, so each insert is one or two reference changes, with no shifting. Nothing is read by position, so the chain's slow lookups never cost anything. And there's no capacity to guess. An array would shift every later task on each insert, and would need a size guess besides.
Rule of Thumb
Array or Chain
So, a rule of thumb. If the program mostly reads items by position, and the size is known in advance, lean toward an array. If it adds and removes at the front, or while scanning, and the size is unpredictable, lean toward a chain. If it needs the smallest possible room per item, the array again. And if it mixes both kinds of work, weigh the operations that happen most often.
Variants
Singly, Doubly and Circular Chains
The chain so far is the simplest form. Change what each node holds, or where the last reference points, and you get variants for different jobs. Singly linked: one reference, to the next node. It's the simplest chain, with a flexible size and cheap changes at the front. Doubly linked: two references, to the previous and the next node. It moves backward as well as forward, and can remove a node when only that node is known. And circular: the last node refers back to the first, for going around again and again, like turns in a round-robin. Each of the three gets a lesson of its own.
Key Takeaways
Nodes Versus Arrays
To sum up. Arrays have two weaknesses: a fixed size, and costly insertion or removal in the middle. A node stores data and a reference. Nodes joined by references form a chain, reached through its head, and ended by null. Insertion and removal relink a few references, in the right order, instead of shifting elements. But there's no index. Reaching position i means following references from the head, so a chain wins mainly at the front, or at the spot.
Think About It
Lines in a Text Editor
Something to think about. A text editor keeps a document as a sequence of lines. Users sometimes jump to a line number, and they often insert new lines near the cursor. Which of those two actions would you want to be cheap? And what would you ask about the users, before choosing an array or a chain?
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 Why Connecting Nodes Solves Problems Arrays Cannot
What is a node in a linked list?
What are the advantages of a linked list over an array?
Why is accessing an element by index slow in a linked list?
What happens if you link a new node in the wrong order?
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 →