Singly Linked Lists, Explained

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

Singly Linked Lists

Data Structures and Algorithms · Chapter 6: Linked ListsSection 6.2 · lesson 22 of 879 min · free with a free account

← Why Connecting Nodes Solves Problems Arrays CannotNext lesson: Circular Linked Lists →

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

Build and test a singly linked list with head, tail and size.

  • Implement a singly linked list with a private Node class, head, tail and size
  • Add and remove nodes at the front, the end and a given position
  • Keep head, tail and size consistent on empty and one-node lists
  • Compare the cost of each list operation with the same operation on an array

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

Opening Question

A Treasure Hunt of Clue Cards

Picture a treasure hunt. Each clue card holds a prize, and a note saying where to find the next card. You're handed only the first card. To reach the fifth, there's no shortcut: you follow the notes, one card at a time. A singly linked list works exactly this way. Each element sits in its own small object, and each one knows only where the next one is.

Building Blocks

Nodes, Head, Tail and Size

A singly linked list is built from nodes. Each node is a small object with two fields: a value, and next, a reference to the following node. The list itself keeps three things. Head refers to the first node. It's the only way into the chain, and every walk starts there. Tail, which is optional, refers to the last node, so the list can add at the end without walking. And size counts the nodes. The last node's next is null, which means refers to nothing. In a list, null works like a full stop.

Code Walkthrough

A Private Nested Node Class

Here's the start of the list type. Node is declared inside it, as a private nested class, so outside code only ever sees values, never nodes. The node's constructor stores the value, and leaves next as null. Below it are the list's three fields. An empty list has head null, tail null, and size zero. All three always agree. To string walks the chain with a helper reference, cur. Start at the head, keep going while cur refers to a node, and hop to cur dot next. On the empty list, that loop never runs, and it prints empty brackets, with size zero.

Adding at the Front

Connect the New Node First

Adding comes down to one rule. Connect the new node to the rest of the chain first, then connect the chain to the new node. At the front, no walk is needed. Make the node, point its next at the old first node, then move head to the new node. If the list was empty, the new node is also the last one, so tail must point at it too. Add thirty, then twenty, then ten, each at the front, and the list reads ten, twenty, thirty. Two reference changes each time, however long the list is.

Adding at the End

Why the Tail Reference Helps

At the end, the tail makes adding just as quick. The old last node points at the new node, and then tail moves forward. Without a tail, the list would have to walk from the head to find the last node, every single time. And again, an empty list is the special case. The new node becomes head and tail at once. Build ten, twenty, thirty with two adds at the back and one at the front, and it prints in order.

Searching

Index Of and Get Walk the Chain

Searching uses the same walk. Index of moves cur from node to node, counting as it goes, and returns the position of the first match. A value that isn't there makes cur fall off the end of the chain, so the method returns minus one instead. And get has no shortcut. An array jumps straight to slot i, but a list must follow i links from the head. One common slip is the loop condition. Cur dot next not null stops one node early, and on an empty list, cur itself is null, so it fails. Run it. Thirty is at position two, ninety-nine isn't there, and get of one walks a single link, to twenty.

Inserting by Position

Stopping at the Node Before the Gap

Inserting in the middle is where the one-way links bite. The new node lands between two existing nodes, and only the node before the gap can change its next. So the walk stops one early, at the node called prev. For index two, the loop runs once, and prev is node twenty. Then the same rule: the new node points at what followed prev, which is thirty. Only then does prev point at the new node. Index zero and index size are handed to add first and add last. Anything outside zero to size throws an exception. Run it, and twenty-five lands between twenty and thirty.

Quick Check

Inserting Six at Index One

Quick check. A list holds four, eight, fifteen, and this program inserts six at index one. What does the list print? Pause and predict. Four, six, eight, fifteen. For index one, the walk runs zero times, so prev stays on the head, node four. Six then points at eight, and four points at six. Six first would mean index zero, and six after eight would mean index two.

Removing at the Front

Moving Head to the Second Node

Removing from the front mirrors adding there. Move head to the second node. The old first node is no longer reachable, and Java reclaims its memory on its own. Two details matter. An empty list has nothing to remove, so the method throws an exception. And if this removal leaves the list empty, tail must be set to null too. Otherwise it would keep pointing at a node that's no longer in the list.

Removing at the End

The Awkward Walk to the Tail

Removing the last node is the awkward one. Tail says which node goes, but detaching it means changing the next of the node before it. A node can't point backward. So the only way to find that node is to walk from the head, until its next is the tail. Then cut the last node off, and move tail back one. With exactly one node, there's no node before it, so the work is handed to remove first. That walk makes remove last slow on long lists, even with a tail. Nodes that point both ways, coming up in this chapter, fix that.

Removing by Value

Skipping Over the Unwanted Node

Removing by value uses the same idea as inserting. Find the node before the unwanted one, and make its next skip over it. Before the general case, three special cases: an empty list, a match at the head, handed to remove first, and a value that isn't there. And if the node being removed is the last one, tail moves back to prev. The skipped node becomes unreachable. Put together: three adds build ten, twenty, thirty. Inserting twenty-five at two, removing twenty, and removing both ends leaves only twenty-five.

Edge Cases

Empty and One-Node Lists

Most linked list bugs hide at the edges: a list with zero nodes, or one. There, head and tail may both be null, or be the very same node. So check three rules after every operation. Head, tail and size agree about emptiness. The last node's next is null, and tail refers to it. And with exactly one node, head and tail refer to the same node. Test the empty list and the one-node list before anything longer.

Common Mistake

Moving Head Too Soon

The most damaging pointer mistake is the wrong step order. Move head to the new node first, and then point the new node at head. By then, head is the new node itself. So the new node points at itself, and twenty and thirty can't be reached anymore. Walk six steps, and it prints ten, six times. Without that limit, a traversal would never end. Other usual suspects: a stale tail, a dot on a null reference, a forgotten size update, and a walk that stops one node off. Draw boxes and arrows, and trace by hand.

Quick Check

A Remove First That Forgets the Tail

One more check. This small list's remove first forgets one line: it never sets tail to null when the list becomes empty. Add five, remove it, then add seven. What does the program report about head and size? Pause and predict. Head null, size one. Removing five set head to null, but tail still pointed at the old node five. So add last took the else branch, and hung seven off that lost node. The list's head never sees it. Seven at the head would need tail reset to null. And five is long gone from the head, so the third answer can't happen.

Operation Costs

Constant Time Versus a Walk

So what does each operation cost? Work that doesn't depend on the length is constant time, written O of one. Work that follows many links grows with n, written O of n. Add first, remove first, and add last with a tail are all constant. So are size and is empty, read from a counter. Remove last, add or remove at a position, get, index of, and remove by value all walk, so they're O of n. Next to an array: reading index i is constant for the array, but a walk for the list. At the front, it's the reverse. And the list grows one node at a time, paying one extra reference per node.

Key Takeaways

Singly Linked Lists in Summary

To sum up. A singly linked list keeps a head, an optional tail and a size, and each node points only forward. Connect the new node to the chain first, then the chain to the new node. The front is constant time. Positions and the last node need a walk. And test the empty and one-node lists first, keeping head, tail and size in agreement.

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 Singly Linked Lists

What is a singly linked list in Java?
A singly linked list is a chain of nodes in which each node holds a value and a next reference to the following node, so links point only forward. The list keeps a head reference to the first node, often a tail reference to the last node, and a size counter. The last node's next is null, which marks the end of the list.
How do you add a node at the front of a singly linked list?
Create the node, set its next to the current head, then move head to the new node: Node n = new Node(v); n.next = head; head = n;. Add one to size, and if the list was empty, also set tail to the new node. The operation takes the same two reference changes however long the list is, so it runs in constant time.
Why is removing the last node of a singly linked list slow?
Removing the last node requires changing the next of the node before it, and a singly linked node cannot point backward. Even with a tail reference, the code must walk from the head until it finds the node whose next is the tail, then set that node's next to null and move tail back to it. The walk grows with the length of the list.
What are common bugs in a singly linked list implementation?
The most common bug is changing references in the wrong order, such as moving head to a new node before linking that node to the old head, which makes it point to itself. Other frequent slips are a stale tail after the list becomes empty, a forgotten size update, calling a method on a null reference, and a loop that stops one node early or late.

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 →