UPI Study › Courses › Programming in C › Free lessons › Lesson 11.1 Free with a free account
Singly Linked List Fundamentals
Programming in C · Chapter 11: Dynamic Memory, Linked Lists, Stacks, and QueuesSection 11.1 · lesson 71 of 789 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 Programming in C.
Lesson complete
Earn the 3 college credits for Programming in C
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Allocating Heap Memory: malloc(), calloc(), and realloc() →← Workshop: Modeling Real-World Entities with Structures and UnionsNext lesson: Allocating Heap Memory: malloc(), calloc(), and realloc() →
In this lesson
Building, walking, and freeing a chain of linked nodes.
- Define a self-referential node struct with a data member and a next pointer
- Traverse a linked list with a separate pointer from the head to NULL
- Write an append function that returns the head and handles an empty list
- Free every node safely by saving the next address before each free
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,341 words). Read along, or search it.
Opening Question
A Waiting Line of Unknown Length
At the Starlight Arcade, the claw machine has a waiting line. Some nights three players wait. Some nights, thirty. An array is a row of seats, and you pick the number of seats before the show starts. Thirty seats waste space on quiet nights. Three seats leave the fourth player with nowhere to stand. A linked list works more like a scavenger hunt. Each clue doesn't hold the prize. It tells you where the next clue is hiding. Today you'll design a node, link nodes into a list, add players at the back, walk the list, and free it.
Core Idea
Nodes Tied Together by Addresses
Here's the plan. Each player gets their own small box, called a node. Each node holds two things: the player's name, and the address of the next node. The boxes can sit anywhere in memory. The addresses, which are pointers from 8.2, tie them into a line. The last node's next holds NULL, which means nobody comes after me. To add a player, you ask for one more box and hook it on. Nothing else moves. The price: you can't jump straight to the third player with square brackets. You follow the links from the front.
Node Design
A Struct That Points to Its Own Type
In C, a node is a struct with two kinds of members. The data you want to keep, here a name, and a next pointer that holds the address of the following node. Look closely at the pointer. It's declared struct Node star next, with the full name, struct Node. Why not just Node? Because the short name Node only exists after the closing brace. Inside the braces, it isn't ready yet. Try the short way. Change struct Node star next to Node star next, and build. Clang stops: must use struct tag to refer to type Node. It even suggests the fix: put the word struct back. Now a second question. Why a pointer to the next node, and not a whole Node inside each node? Try that too. A Node that holds a Node would hold another, and another. It would need endless space. Clang refuses: field has incomplete type, struct Node. The note says the definition isn't complete until the closing brace. A pointer, though, is always eight bytes here, however long the chain grows. Put the pointer back and run: one node is thirty-two bytes. That's twenty bytes for the name, four bytes of padding, and eight for the pointer. So the link stays small, however long the list grows.
Traversal
Linking Three Nodes by Hand
Now link some nodes. To keep this first try simple, the three nodes are ordinary variables: a, b and c. They hold Mira, Leo and Dev, and each next starts as NULL. Who knows where the chain starts? One extra pointer, called the head. It holds the address of the first node, a. Then two assignments draw the links. a dot next gets the address of b, and b dot next gets the address of c. c dot next is still NULL, so the chain ends at Dev. To walk the list, take a second pointer, cur, and start it at the head. While cur isn't NULL, print cur arrow name, then hop: cur equals cur arrow next. Build and run. Mira, Leo, Dev. Then cur becomes NULL, and the loop stops. Walking a list like this is called traversal.
Quick Check
Moving the Head Loses a Node
Quick check. Priya adds one line just before the walk: head equals head arrow next. Now what does the program print? Pause and predict. Build and run: Leo, then Dev. Mira is missing. Moving the head moved the start of the list. cur begins at Leo, so the walk never sees Mira. And nothing points at Mira's node any more. In a list built on the heap, you could never print her or free her again. So leave the head alone, and walk with a separate pointer, like cur.
Plan
Adding a Player at the Tail
Linking nodes by hand works for three players. But Sam keeps adding players, so we need a function that adds one at the tail, the back of the line. The steps never change. Make the node. Find the last node. Point that last node at the new one. One special case: an empty list has no last node. Then the new node simply becomes the head. So append returns the head, which may be new, and the caller stores it back: line equals append of line and Mira.
Helper Function
Making One Node With Malloc
Here's the whole program, line_up dot c. The struct at the top is the one you just built. make_node asks for one node-sized block with malloc, which you saw briefly in 10.4. You'll see its full rules properly in 11.2. If malloc can't help, it returns NULL, so the function checks before it touches the block. Then it copies the name in, and sets next to NULL, because a brand-new node has nobody after it.
Code Walkthrough
Walking to the Last Node
Now append. First it makes the node. If that failed, it returns the head, and the list stays as it was. If the list is empty, the new node is the whole list, so append returns it as the new head. Otherwise, a walker starts at the head and hops while cur arrow next isn't NULL. It stops on the last node, the one whose next is NULL. One assignment hooks the new node on, and the head stays the same. That is the whole of append.
Sample Run
Four Players and No Fixed Limit
In main, an empty list is just a head that's NULL. Each call to append adds a player at the back, and stores the head it returns. Priya's first version used an array of three seats, and Sam's fourth player had no place. Here, Ana is simply one more box. Build and run. Mira, Leo, Dev, Ana, and then NULL.
Quick Check
Forgetting to Store the Returned Head
Quick check. Sam deletes line equals from the first call only, so it reads: append of line and Mira. The other three calls still store the head. What does print_list show now? Pause and predict. Build and run: Leo, Dev, Ana, then NULL. Mira is gone. The first append made Mira's node and returned it as the new head. Nobody stored it, so line stayed NULL. The next call saw an empty list, so Leo became the head. Mira's node still exists, but nothing points at it. That's a block nobody can ever free: a memory leak. You'll hunt those in 11.3. Put line equals back, and every player is stored again.
Cleanup Plan
Save Next Before You Free
Two jobs remain: printing the list, and giving every node back. print_list is the same walk, written as a for loop: start at the head, stop at NULL, hop to next. Every malloc needs a matching free, so a list needs a loop that frees each node. And here's the trap. Once a node is freed, you must not read its next. That box isn't yours any more. So free_list does three steps, in this order. Save the next address in a variable called after. Free the current node. Then move on to the saved address.
Code Walkthrough
Printing and Freeing the Whole List
In the code, print_list takes a const pointer, as in 10.5, because printing never changes a node. free_list copies head arrow next into after, frees head, and only then moves head to after. main calls it once at the end, so every node that append built goes back.
Speed Up
A Tail Pointer for Fast Appends
One more idea. append walks from the head every time, and that gets slow on a long line. A common fix keeps a second pointer, the tail, that always points at the last node. Then adding at the back is two assignments. The old last node points at the new one, and the tail moves to it. Three players or three thousand, it's the same few steps. Queues in 11.5 use exactly this trick.
Key Takeaways
Head, Next, and NULL
To sum up. A node is a struct: the data, plus a pointer to the next node. The head points at the first node, and NULL marks the end. To add at the back, walk to the last node and hook the new one on. Store the head that append returns. Walk with a separate pointer. And when you free, save next first.
About Programming in C at UPI Study
Programming in C (Computer Science 240) is a self-paced online course of 78 video lessons in 11 chapters, from pseudocode and your first program to data types, decisions, loops, functions, arrays, strings, pointers, files, structures, dynamic memory and linked lists. 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: C vs C++
Why take it here
Why students take Programming in C with UPI Study
Where the credit goes
Universities that work with NCCRS
Programming in C 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 Singly Linked List Fundamentals
What is a singly linked list in C?
Why does a linked list node hold a pointer instead of a whole node?
How do you traverse a linked list in C?
Why must you save the next pointer before freeing a linked list node?
About the Programming in C course
How many college credits is Programming in C?
How much does Programming in C cost and what is included?
Which universities accept UPI Study credits?
How long does Programming in C take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Programming in C.
78 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →