Discussion 3: LinkedList

Discussion 3: Thursday, June 4, 2026.

In this discussion you will implement a singly linked list in Rust using raw pointers and manual memory management. This exercise is great preparation for the upcoming Vec project, where you will manage heap memory directly in a similar way.

Clone the course code repository and navigate to the linked_list directory to get started:

git clone https://github.com/rust4ds/ds210-sum26-code.git
cd discussion_3_linked_list

When you are done, zip the src directory and submit it to Gradescope.

Part 1: Simple Linked List

Implement get and push_back in src/simple_linked_list.rs.

The struct definitions and push_front are already provided. Nodes are heap-allocated using MALLOC.malloc, the same custom allocator you will use in the Vec project. Take a look at push_front to understand the pattern before writing your own code.

get(i) — return a raw pointer to the node at index i. Traverse the list one step at a time. If i is out of bounds, panic.

push_back(value) — allocate a new node and append it to the end of the list. Think about the empty list as a special case.

To test and run:

cargo test --test simple
cargo run --bin simple_main --release

The simple_main binary compares the performance of your linked list against a Vec for len, get, push_back, and push_front. Look at the timing results and think about why each operation takes as long as it does for each data structure. Do the results match your expectations? Take a screenshot of the output and upload it to Gradescope.

Part 2: O(1) len and push_back

Look at the timing results from Part 1 and analyze the runtime of each operation on your linked list. Which ones could be made faster? How would you do it?

For this part, make len() and push_back() run in O(1) time. Hint: consider storing additional metadata in the LinkedList struct.

Run simple_main again after your changes and compare the timings to Part 1. Take a screenshot of the new output and upload it to Gradescope.

Part 3: Remove

Implement remove in src/remove_linked_list.rs. The remove_head function is already provided — read it carefully.

remove(i) — remove the node at index i. Think carefully about all the cases your implementation needs to handle.

Start by running the tests to make sure your implementation is correct:

cargo test --test remove

Then run the binary and look at the output carefully:

cargo run --bin remove_main

Is there a memory leak? If so, think about what is causing it and how to fix it. The fix applies to both remove and remove_head. Apply it, then run the tests and the binary again to confirm everything is correct.

Part 4: Drop

Run the drop_main binary:

cargo run --bin drop_main

Look at the output — is there a memory leak? Why is it happening?

Rust allows you to run custom cleanup code when a value goes out of scope by implementing the Drop trait. Implement Drop for LinkedList in src/drop_linked_list.rs, then run drop_main again to confirm there is no longer a leak.