UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 6.4 Free with a free account
Forward and Backward Navigation Between Nodes
Data Structures and Algorithms · Chapter 6: Linked ListsSection 6.4 · lesson 24 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: What Separates a Good Solution from a Poor One →← Circular Linked ListsNext lesson: What Separates a Good Solution from a Poor One →
In this lesson
Doubly linked lists with sentinels make local changes constant time.
- Describe a doubly linked node and the rule that next and prev must agree
- Explain how header and trailer sentinels remove edge-case code
- Implement insertion between two neighbors and removal of a node you hold
- Compare doubly and singly linked lists on running time and memory
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,513 words). Read along, or search it.
Opening Question
Stepping Backward in a Playlist
A music app keeps a playlist as a chain of nodes. Press next, and it steps forward one song. Easy. Now press previous. In a singly linked chain, the app has to walk from the first song all the way to the one before. That's because a node knows what comes after it, but never what came before. What would it take to step backward in one move?
The Problem
Two Costs of One-Way Links
That one-way design causes two familiar annoyances in a singly linked chain. To remove a node, you first walk from the start of the chain, to find the node before it. And to reach the last node, you walk the whole chain, unless you also keep a tail reference. Both come from the same missing piece of information. So give every node a second reference, to the node behind it.
Definition
A Node with Prev and Next
A doubly linked node stores three things: its element, a reference to the node after it, called next, and a reference to the node before it, called prev. Compared with a singly linked node, it can still step forward. It can also step backward. And it always knows its predecessor: it's just node dot prev. In Java, it's a private, static nested class inside the list, holding a string element, and the two references.
Key Rule
Next and Prev Must Agree
The two references must always agree. For every pair of neighbors a and b, where b comes right after a, a dot next is b, and b dot prev is a. Almost every bug in a doubly linked list comes from one place: one of the two references wasn't updated.
The Problem
Every Edge Case Adds a Branch
Now suppose the list keeps only a head reference to its first node, and a tail reference to its last. Then every operation has to ask: is the list empty? Is this the first node? The last? The only one? Each question is an extra branch, and each branch is a place for a bug to hide.
Definition
Header and Trailer Sentinels
The cure is to give the list two permanent nodes that hold no data. The header sits before the first real element, and the trailer sits after the last. They're called sentinels, like guards at the two gates of the list. They're never removed, and they never hold data. With them in place, two promises always hold. Every real node has a non-null prev, and a non-null next. And an empty list is simply a header whose next is the trailer, with size 0.
Key Idea
Unlinking in Two Lines
Those promises are what remove the special cases. Without sentinels, unlinking a node needs four branches, to cover the first, the last, and the only node. With sentinels, prev and next are never null, so there's nothing to ask. Unlinking is two lines. Node dot prev dot next becomes node dot next. And node dot next dot prev becomes node dot prev. Adding to an empty list, removing the first, the last, or the only node: all of it runs the same code. The price is two extra nodes per list, not per element.
Worked Example
Four Links to Splice a Node
Every change is built from two small operations. The first is splicing a new node in between two neighbors, pred and succ. Four links must be set. One: the new node's prev is pred. Two: the new node's next is succ. Those two belong to the new node. Three: pred's next becomes the new node. Four: succ's prev becomes the new node. Those two redirect the old links. In code, the constructor sets the first two, and two assignments do the rest.
Implementation
One Method Serves Every Position
That one method, addBetween, serves every position. Adding at the front inserts between the header and whatever follows it. Adding at the back inserts between whatever precedes the trailer, and the trailer. Nothing has to check whether the list is empty, because even an empty list has two neighbors: the sentinels.
Implementation
Unlinking a Node You Already Hold
The second operation is unlinking. Removing a node you already hold takes two assignments, and no search, because the node carries both its neighbors. Pred dot next becomes succ. Succ dot prev becomes pred. Then size goes down by 1. Whether the list holds five nodes or five million, it's the same two assignments. In a singly linked chain, the same job first walks from the start to find the predecessor. Reading the last element is immediate too, since it sits right before the trailer.
Quick Check
Forgetting to Update Prev
Quick check. A list holds A, B, C. A programmer removes B, but writes only the first line: pred dot next becomes succ. The list prints itself forward, from the header, and backward, from the trailer. What do the two walks print? A, C, and C, A? A, C, and C, B, A? Or A, B, C, and C, A? Pause, and decide. The forward walk prints A, C: A's next now skips B. But C's prev still points to B, so the backward walk prints C, B, A. Nothing crashes. The list is quietly inconsistent, and the two directions disagree. Insertion fails the same way. An insert that sets pred dot next but forgets succ dot prev, run on an empty list, printed Ava forward, and an empty list backward. Always update both directions.
Key Idea
Finding a Value Is Still a Walk
The constant-time claim has a condition: you must already hold the node. Given only a value, someone has to find its node first, and finding is a walk. The find method starts just after the header, and follows next until it reaches the trailer, instead of null. So insert after a value is the slow part, a walk, then the fast part, a splice. Remove a value is a walk, then an unlink.
Comparison
Constant Time Versus a Walk
Compared with a singly linked chain that keeps only a head, the doubly linked list with sentinels turns several walks into constant time. Reading the last element, adding at the back, and removing the last node: each is a walk for the singly linked chain, and constant here. Removing a node you hold, or inserting before it: a walk to find the predecessor, against constant time. But finding a value is a walk in both designs. A second reference makes local changes cheap, not searching.
Worked Example
Forward and Backward Walks Mirror
And the list can walk both ways. The forward walk starts just after the header, and follows next until it reaches the trailer. The backward walk starts just before the trailer, and follows prev until it reaches the header. A singly linked chain can only offer the first. In a demo run, the list was built as Ava, Ben, Cy. Inserting Zed after Ava gave Ava, Zed, Ben, Cy, and the backward walk printed Cy, Ben, Zed, Ava. The two walks are mirror images, which is exactly what shows the prev links agree with the next links.
Quick Check
Tracing Adds, Removes, and Inserts
Quick check, on a new empty list. Add A, B and C at the back. Then add D at the front. Remove the last element. Then insert E after A. What does the list hold, front to back? Is it D, A, E, B? A, E, B, D? Or D, A, B, E? Pause, and decide. D, A, E, B. After the adds, the list is D, A, B, C. Removing the last drops C, leaving D, A, B. Then E is spliced in right after A. The other two options put D at the back, or E after B, and neither of those follows the steps. And each of those steps was constant time, except the find inside insert after.
Trade-Offs
The Price of an Extra Reference
Nothing comes free. A doubly linked node stores one more reference than a singly linked node, and every node pays it. A reference typically takes 4 or 8 bytes, depending on the Java virtual machine. So a million nodes carry a million extra references: roughly 4 to 8 megabytes more. The exact figure depends on how the virtual machine lays out objects, so measure before you decide. There's also more code to get right: four link updates per insertion instead of two, and both references kept in agreement at all times.
Decision Guide
Singly or Doubly Linked
So when is it worth it? If records are only added at one end and read from start to finish, the prev reference is never used. Choose singly linked. If nodes must be removed from the middle after being located, or the list is read in both directions, or work happens at both ends, choose doubly linked. That's the idea behind double-ended queues. And with millions of tiny elements and tight memory, measure. The extra reference may matter.
Key Takeaways
Doubly Linked List Essentials
To sum up. A doubly linked node stores prev as well as next, so it walks both ways, and always knows its predecessor. Header and trailer sentinels give every real node two neighbors, so insertions and removals need no edge-case code. Inserting between neighbors takes four link updates. Removing a node you hold takes two. Neither depends on the length. But finding a value is still a walk, and every node pays for its extra reference.
Think About It
A Million Records Added at the End
Something to think about. A program stores one million small records. It only ever adds at the end, and reads them in order. Would you choose a doubly linked list for it? What would you use instead, and what would you save?
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 Forward and Backward Navigation Between Nodes
What is a doubly linked list?
What are sentinel nodes in a doubly linked list?
How do you remove a node from a doubly linked list in Java?
When is a doubly linked list worth the extra memory?
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 →