Circular Linked Lists, Explained

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

Circular Linked Lists

Data Structures and Algorithms · Chapter 6: Linked ListsSection 6.3 · lesson 23 of 878 min · free with a free account

← Singly Linked ListsNext lesson: Forward and Backward Navigation Between Nodes →

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, walk, and update a circular linked list held by its tail.

  • Explain why a circular linked list is held by a tail reference
  • Traverse a ring safely with a do-while loop that stops back at the start
  • Implement addFirst, addLast, rotate, and removeFirst while keeping the tail correct
  • Apply rotation to round-robin scheduling and turn-taking problems

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

Opening Question

Walking a Ring Without End

Some jobs never really end. A processor serves each waiting task in turn, then starts over. Players take turns, round and round a circle. A plain chain of nodes has an end, which is awkward for work like that. Join the last node back to the first, and the chain becomes a ring, with no end at all. So how do you walk a ring without walking forever?

Worked Example

Holding the Ring by Its Tail

Here's that ring, built by hand. A points to B, B to C, and the one new link: C's next points back to A. A ring has no obvious first or last, so we hold it by its last node, the tail. Then the first node is always one step away: tail dot next. Run it. The tail is C, and tail dot next is A. Then eight steps around a ring of three print A, B, C, A, B, C, A, B. The walk wraps around without ever meeting null. It stopped only because the loop counted to eight.

Key Idea

Tail Gives Access to Both Ends

Holding the tail gives instant access to both ends. The last node is tail. The first node is tail dot next. Adding at either end needs no search. Holding the head would give quick access to the front only. Two special cases to remember. An empty ring has tail equal to null. And a one-node ring points to itself: tail dot next is tail.

Common Mistake

Replacing the Null Test with Do-While

Every walk of a plain list rests on one test: keep going while the current node isn't null. In a ring, no next is ever null. So that loop, copied onto a ring, never ends. The program doesn't fail with a message. It simply never finishes. The replacement test is to stop when the walk returns to where it started. Remember the start, and step until you're back. Because the walk begins at the start, the test must come after the first step. That's exactly what a do-while gives you. A, B, C, once each. The if around it handles the empty ring. And a one-node ring works too: one step brings cur back to start, after one visit.

Comparison

Plain Walk Versus Ring Walk

Side by side, the two kinds of list differ in three places. A plain list starts its walk at the head. A ring starts at tail dot next. The plain walk continues while cur isn't null. The ring's walk continues until cur is the start again, tested after each step. A counted loop is the other safe choice: if the list stores its size, run the loop exactly size times.

Implementation

Add First and Add Last

Now a full circular list type. It keeps only a tail and a size. Add first is the heart of it. On an empty list, the new node must point to itself, since it's both the first and the last node. It becomes the tail. Otherwise, two pointer changes. The new node points at the old first node, then the tail points at the new node. The tail itself doesn't move, so the new node is first. Add last reuses that work. Insert at the front, then move the tail one step forward, onto the new node. The same position is now the back. Run it. Empty brackets, then A, B, C after adding B and C at the back and A at the front. D goes last, and the first element is still A.

Quick Check

Pointer Changes in the Wrong Order

Quick check. The ring holds A, B, C, with the tail on C. Someone inserts X at the front, but writes the two pointer changes in the opposite order. A six-step walk from tail dot next follows. What does it print? Pause and predict. X, six times. Setting tail dot next to x first overwrites the only reference to A. The second line then copies tail dot next, which is now x, into x dot next. So X points to itself, and A and B can't be reached from the tail. Point the new node somewhere safe before you change the old links.

Implementation

Removing Nodes Without Losing the Tail

Deleting needs the most care, because removing the last node changes which node the list is held by. Remove first has two cases. If the first node is also the tail, the ring had one node, so the list empties. Otherwise, the tail simply skips the old first node. Rotate moves the tail one step forward, so the first node becomes the last, with no relinking at all. Remove by value walks the ring, remembering the node before. When it unlinks the tail itself, the tail moves back to prev. The test covers every case: a middle node, the last node, a front node, a value that isn't there, and the last two nodes, which empty the list.

Worked Example

Rotate Then Remove First

Rotate and remove first are the two operations the applications use most. A, B, C rotated once is B, C, A. Rotated again, C, A, B. Each time, the first element moved to the back. Remove first then takes C off the front, leaving A, B.

Application

Round-Robin Scheduling with a Quantum

Round-robin scheduling is a fair way for a processor to share its time. Each task gets a short, fixed slice of time, called the quantum. If a task isn't finished when its slice ends, it goes to the back of the line. A finished task leaves for good. That's exactly a ring: rotate, or remove first. With a quantum of two, A runs two and goes to the back, B finishes in one slice and leaves, and so on, until every task is done. No task waits behind a long one for its whole run, which is why round robin is used.

Quick Check

Tracing Two Tasks with Quantum Two

One more check. Task A needs three units and task B needs five, with a quantum of two. The program prints each slice as a name and the units used. In what order do the slices run? Pause and predict. A two, B two, A one, B two, B one. A runs two, with one left, and goes to the back. B runs two, with three left. A finishes with its last unit and leaves. Then B is alone in the ring, so it runs two, and then one. Running A twice in a row ignores the rotation. And B can't run twice before A's turn comes back.

Application

Every Third Player Is Out

Turn-taking is the same idea with people: players go in a fixed order, and after the last one, the first plays again. Rotation does all the work. A well-known puzzle combines both operations. Six players stand in a circle, and every third player is out, until one remains. Rotate twice, so the third player is at the front, then remove the front. Players three, six, four, two and five leave, and player one wins. The wrap-around that a plain list would need special code for simply happens.

Trade-Offs

When a Ring Beats a Plain List

So a ring isn't better than a plain list in every way. It's better when the work goes round: scheduling, turns, and rotating buffers of work. Its main risk is looping forever with the plain end test. A plain list's main risk is following a null at the end. When the data has a real beginning and end, the plain list is simpler and safer.

Key Takeaways

Circular List Essentials

To sum up. In a circular list, the last node points back to the first. Hold it by the tail: tail dot next is the first node, so both ends are instant. Walk with a do-while that stops back at the start, never with a null test. And update the tail whenever the last node leaves, emptying the ring when the only node goes.

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

What is a circular linked list in Java?
A circular linked list is a linked list whose last node points back to the first node instead of to null, so the nodes form a ring with no end. It is usually held by a tail reference, because tail.next is then the first node, giving instant access to both ends. An empty list has tail equal to null, and a one-node list points to itself.
How do you traverse a circular linked list without an infinite loop?
Remember the starting node and stop when the walk returns to it, testing after each step. A do-while loop fits: if tail != null, set Node start = tail.next and Node cur = start, then do { System.out.println(cur.element); cur = cur.next; } while (cur != start);. The usual while (cur != null) test never ends on a ring, because no next reference is null. Looping exactly size times also works.
How do you insert at the front of a circular linked list?
Point the new node at the old first node, then point the tail at the new node: x.next = tail.next; tail.next = x;. The tail does not move, so x becomes the first element. On an empty list, x points to itself and becomes the tail. Adding at the back is the same insert followed by tail = tail.next. Swapping the two assignments loses the old first node, leaving x pointing to itself.
Why is a circular linked list used for round-robin scheduling?
Round-robin scheduling gives each task a fixed time slice, called the quantum, and sends an unfinished task to the back of the line, which is exactly one rotation of a ring. A finished task is removed from the front. With task A needing 3 units, task B needing 5, and a quantum of 2, the slices run A 2, B 2, A 1, B 2, B 1.

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 →