CS 238 Week 11 Lecture
Overview
The lecture explains how a singly linked list stores data in nodes connected by next references rather than in contiguous array memory, making front insertion and removal efficient. It traces Python implementations of push_front, insert_after, remove, printing, and pop_front, showing how traversal and pointer updates change the list.
Key takeaways
- A singly linked list connects nodes through next references, so its elements do not need to occupy contiguous memory.
- Adding a node to the front takes O(1) time because push_front only creates a node and updates its next and head references.
- Finding a node by position requires traversal from head, so insertions and removals at arbitrary positions take O(n) search time even when the final link update is simple.
- Removing a middle node works by redirecting the previous node's next reference to the removed node's successor, making the removed node unreachable from head.
- pop_front takes O(1) time by advancing head to head.next, while preserving head during other traversals prevents losing access to the list.
Chapters
- Unlike a Python list or NumPy array, whose elements are contiguous, linked-list nodes may be scattered in memory and connected by references.
- Each node holds a data value and a next reference; the final node points to None.
- The list's head reference identifies its first node, while a None head represents an empty list.
- push_front creates a node, assigns its next reference to the current head, then makes the new node the head.
- Repeatedly pushing 5, 7, 11, and 10 produces the list 10 → 11 → 7 → 5.
- Front insertion takes O(1) pointer updates, unlike inserting at the front of an array, which may require shifting elements.
- insert_after cannot jump directly to an index; it starts at head and follows next references until it reaches the target node.
- Inserting 19 after the third node links 7 → 19 → 5 by setting the new node's next to the old successor.
- Removing the fourth node bypasses 19 by changing the previous node's next reference to point to 5.
- A temporary traversal reference preserves self.head while searching, and printing continues until the traversal reference reaches None.
- pop_front removes the first node by assigning self.head to self.head.next; the example changes 10 → 11 → 7 → 5 into 11 → 7 → 5.
- The code run demonstrates the sequence: push 5, 7, 11, and 10; insert 19 after node 3; remove node 4; then pop the front.
- The lecture distinguishes a singly linked list, which traverses in one direction, from a doubly linked list with an additional previous reference.
Transcript excerpt
0:01 Hello CS238 class. Uh for this week we're going to be talking about a link list data structure. Now this is sort of more important when we talk about languages like C, C++ and even assembly language where you have more direct access to memory allocation deallocation which you kind of don't have that type of access when you talk about languages like Python uh Java and C kind of give you some illusion of that but really it's more direct in uh C++ or C. So in Python you've probably used numpy or list structures looking at the code on the left side over here. Consider a list like this. You have elements 10 11 7 and 5 and they are um continuous or
0:49 contiguous to each other. So they're arranged side by side. You can access elements of a list either using a rangebased loop or you can of course use the list followed by the index. So index zero would access 10, index one for 11 and so forth. So um in C++ or C you have dynamic arrays or list structures but you have to of course manually um implement them and you have an alternative to this dynamic array structure which would be a link list which here is the image of a link list right here. So even though we can draw link list to look continuous or contiguous it's really in memory these elements are kind of scattered all over the place and then we use these references these pointers references here to kind of glue these elements together to kind of form an illusion of
1:40 a continuous uh list type structure. And really the benefit of this structure in C++ is if you need to uh resize it, it's requires a lot less overhead than
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, James Andro-Vasko.