1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
use super::DoublyLinkedList;
impl<T> DoublyLinkedList<T> {
/// Removes the first element from the `DoublyLinkedList`, if it exists.
///
/// # Behavior
///
/// - If the list is empty, this method does nothing.
///
/// # Examples
///
/// ```
/// use villa01_data_structures::doubly_linked_list::DoublyLinkedList;
///
/// let mut list = DoublyLinkedList::new();
/// list.insert_at_end(1);
/// list.insert_at_end(2);
/// list.insert_at_end(3);
///
/// list.delete_first();
/// assert_eq!(list.get(0), Some(&2)); // The new head is now 2
/// assert_eq!(list.len(), 2); // The length of the list is updated
///
/// list.delete_first();
/// list.delete_first();
/// assert!(list.is_empty()); // The list is empty after all elements are removed
/// ```
/// # Safety
///
/// - This method uses `unsafe` internally to deallocate the removed node from the heap.
/// - It is safe as long as the internal structure of the `DoublyLinkedList` remains valid,
/// ensuring proper pointer updates between nodes.
///
/// # Complexity
///
/// - **Time Complexity:** `O(1)`
/// - **Space Complexity:** `O(1)`
pub fn delete_first(&mut self) {
if let Some(head) = self.head {
unsafe {
// One item lists
if self.head == self.tail {
// Deallocate memory in heap
self.head = None;
self.tail = None;
} else if let Some(next) = (*head).next {
self.head = Some(next);
(*next).prev = None;
}
let _ = Box::from_raw(head);
}
self.length -= 1;
}
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_delete_first_empty_list() {
let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
list.delete_first();
assert!(
list.is_empty(),
"List should remain empty after deleting from an empty list"
);
}
#[test]
fn test_delete_first_one_item_list() {
let mut list = DoublyLinkedList::new();
list.insert_at_end(42);
list.delete_first();
assert!(
list.is_empty(),
"List should be empty after deleting the only item"
);
assert_eq!(list.len(), 0, "List length should be 0 after deletion");
}
#[test]
fn test_delete_first_multi_item_list() {
let mut list = DoublyLinkedList::new();
list.insert_at_end(1);
list.insert_at_end(2);
list.insert_at_end(3);
list.delete_first();
assert_eq!(
list.get(0),
Some(&2),
"First element should now be 2 after deleting the first"
);
assert_eq!(list.len(), 2, "List length should be 2 after deletion");
list.delete_first();
assert_eq!(
list.get(0),
Some(&3),
"First element should now be 3 after another deletion"
);
assert_eq!(
list.len(),
1,
"List length should be 1 after another deletion"
);
list.delete_first();
assert!(
list.is_empty(),
"List should be empty after deleting all elements"
);
assert_eq!(
list.len(),
0,
"List length should be 0 after deleting all elements"
);
}
#[test]
fn test_delete_until_empty() {
let mut list = DoublyLinkedList::new();
list.insert_at_end(10);
list.insert_at_end(20);
list.insert_at_end(30);
list.delete_first();
list.delete_first();
list.delete_first();
assert!(
list.is_empty(),
"List should be empty after deleting all elements"
);
assert_eq!(
list.len(),
0,
"List length should be 0 after deleting all elements"
);
list.delete_first();
}
#[test]
fn test_list_integrity_after_delete_first() {
let mut list = DoublyLinkedList::new();
list.insert_at_end(5);
list.insert_at_end(10);
list.insert_at_end(15);
list.delete_first();
list.insert_at_end(20);
assert_eq!(list.get(0), Some(&10), "First element should now be 10");
assert_eq!(list.get(1), Some(&15), "Second element should remain 15");
assert_eq!(
list.get(2),
Some(&20),
"Newly inserted element should be at the end"
);
assert_eq!(list.len(), 3, "List length should be 3 after operations");
}
}