This lesson implements linked-list operations from a head node, then compares them with a doubly linked wrapper that retains a tail and length. Those interfaces expose different information. An operation that is direct with a saved tail may require traversal when the function receives only a head.
Make head replacement part of the contract
Prepending creates a node whose next reference points to the old head, then returns the new node. The caller must retain that returned head. Appending from a head-only interface follows successors until it reaches the final node, then attaches the new node. Empty input needs a separate path because there is no final node to update.
For an insertion into the middle, first locate the predecessor. Set the new node's next reference to the predecessor's old successor before connecting the predecessor to the new node. This order preserves the remaining chain. Removing a node similarly reconnects its predecessor to its successor. Removing the head changes the returned head instead.
Maintain both directions in a doubly linked wrapper
A wrapper with head, tail, and length must keep them consistent after every mutation. In a nonempty doubly linked list, a next link and the corresponding previous link should agree. Prepending changes the old head's previous reference; appending changes the old tail's next reference. An empty-to-nonempty transition must establish both endpoints.
The constructor in the current example creates a first node, so its initial length is one. A zero initial count would make later increments disagree with the chain. Test the constructor state before testing any method. A correct append cannot repair a count that was already wrong.
Charge for the traversal you perform
Given the needed predecessor, changing a fixed number of links uses constant work. Finding a position from the head takes linear time. Retaining a tail makes append direct, but removing a singly linked tail still requires finding its predecessor. A recursive traversal also adds stack depth that a loop avoids.
Check an empty chain, one node, insertion at the head, and insertion at the end. Walk forward after every mutation and backward for the doubly linked version. Use the current implementation lesson for its exact index contracts, then apply the same reference discipline to Reverse a Linked List.
Verify links in both directions
The complete example here is a doubly linked list with a nonempty constructor, prepend, and append. Starting at 5, prepend 2 and append 9. Forward traversal should read [2, 5, 9]; backward traversal should read [9, 5, 2]. Length should be three, the head's previous link absent, and the tail's next link absent.
On prepend, retain the old head before replacing it. Connect the new head forward to the old head, then connect the old head backward to the new one. Append performs the corresponding endpoint updates. Checking only forward traversal can miss a broken previous link.
Describe the API that is actually provided
The constructor creates one node. This excerpt does not implement an empty-list constructor, removal, or indexed insertion. The main lesson develops additional operations separately. Calling this a complete general-purpose list library would overstate what the shown class supports.
Each prepend and append changes a fixed number of links, for O(1) structural work and one new allocation. Traversal takes O(n), and nodes occupy O(n) storage. Shared forward and backward ownership can form a retention cycle; Swift uses weak previous links and Rust uses Weak for that reason. Check several alternating prepends/appends, repeated payloads, both traversal directions, and the length. Compare node identity when verifying reciprocal links, because equal values can hide references to the wrong node.
Rust example and implementation choices
Rc<RefCell<DoublyNode>> permits shared endpoints and checked interior link updates. Previous links use Weak, preventing a reference-count cycle from retaining the whole chain. Upgrade is needed before following a weak link. Keep RefCell borrow scopes short when checking reciprocal neighbors. The list owns its nodes through forward strong links and endpoints, and its constructor always establishes one initial entry.
Complete implementation
use std::cell::RefCell;
use std::rc::{Rc, Weak};
struct DoublyNode {
data: i32,
next: Option<Rc<RefCell<DoublyNode>>>,
// Weak, so that a node and the one before it don't keep each other alive
prev: Option<Weak<RefCell<DoublyNode>>>,
}
impl DoublyNode {
fn new(data: i32) -> Self {
DoublyNode {
data,
next: None,
prev: None,
}
}
}
// The head and tail (and each node's neighbors) point to the same nodes,
// so the nodes are shared with Rc<RefCell<...>>
struct DoublyLinkedList {
length: usize,
head: Rc<RefCell<DoublyNode>>,
tail: Rc<RefCell<DoublyNode>>,
}
impl DoublyLinkedList {
fn new(data: i32) -> Self {
let initial_node = Rc::new(RefCell::new(DoublyNode::new(data)));
DoublyLinkedList {
length: 1,
head: Rc::clone(&initial_node),
tail: initial_node,
}
}
// O(1)
fn prepend(&mut self, data: i32) -> Rc<RefCell<DoublyNode>> {
let prepended_node = Rc::new(RefCell::new(DoublyNode::new(data)));
let previous_head = Rc::clone(&self.head);
self.head = prepended_node;
self.head.borrow_mut().next = Some(Rc::clone(&previous_head));
previous_head.borrow_mut().prev = Some(Rc::downgrade(&self.head));
self.length += 1;
Rc::clone(&self.head)
}
// O(1)
fn append(&mut self, data: i32) -> Rc<RefCell<DoublyNode>> {
let appended_node = Rc::new(RefCell::new(DoublyNode::new(data)));
let previous_tail = Rc::clone(&self.tail);
self.tail = Rc::clone(&appended_node);
self.tail.borrow_mut().prev = Some(Rc::downgrade(&previous_tail));
previous_tail.borrow_mut().next = Some(Rc::clone(&self.tail));
self.length += 1;
appended_node
}
}
Continue in Rust
Open Implement a Linked List for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the Rust example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The Rust interview preparation guide connects these language choices with further practice and the cross-language operation reference.