Struct LinkedList

pub struct LinkedList<T> {
    head: *mut Node<T>,
    tail: *mut Node<T>,
    len: usize,
    marker: PhantomData<Box<Node<T>>>,
}

A doubly-linked list with owned nodes.

The LinkedList allows pushing and popping elements at either end in constant time.

Fields

head: *mut Node<T>

tail: *mut Node<T>

len: usize

marker: PhantomData<Box<Node<T>>>

Implementations

impl<T> LinkedList<T>

fn push_front_node(&mut self, node: Node<T>)

Adds the given node to the front of the list.

fn pop_front_node(&mut self) -> Option<Node<T>>

Removes and returns the node at the front of the list.

fn push_back_node(&mut self, node: Node<T>)

Adds the given node to the back of the list.

fn pop_back_node(&mut self) -> Option<Node<T>>

Removes and returns the node at the back of the list.

impl<T> LinkedList<T>

pub const fn new() -> Self

Creates an empty LinkedList.

Examples

use cs431_homework::LinkedList;

let list: LinkedList<u32> = LinkedList::new();

pub fn append(&mut self, other: &mut Self)

Moves all elements from other to the end of the list.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

This operation should compute in O(1) time and O(1) memory.

Examples

use cs431_homework::LinkedList;

let mut list1 = LinkedList::new();
list1.push_back('a');

let mut list2 = LinkedList::new();
list2.push_back('b');
list2.push_back('c');

list1.append(&mut list2);

let mut iter = list1.iter();
assert_eq!(iter.next(), Some(&'a'));
assert_eq!(iter.next(), Some(&'b'));
assert_eq!(iter.next(), Some(&'c'));
assert!(iter.next().is_none());

assert!(list2.is_empty());

pub fn prepend(&mut self, other: &mut Self)

Moves all elements from other to the beginning of the list.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

This operation should compute in O(1) time and O(1) memory.

Examples

use cs431_homework::LinkedList;

let mut list1 = LinkedList::new();
list1.push_back('a');
list1.push_back('b');

let mut list2 = LinkedList::new();
list2.push_back('c');

list2.prepend(&mut list1);

let mut iter = list2.iter();
assert_eq!(iter.next(), Some(&'a'));
assert_eq!(iter.next(), Some(&'b'));
assert_eq!(iter.next(), Some(&'c'));
assert!(iter.next().is_none());

assert!(list1.is_empty());

pub fn iter(&self) -> Iter<'_, T>

Provides a forward iterator.

Examples

use cs431_homework::LinkedList;

let mut list: LinkedList<u32> = LinkedList::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), None);

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Provides a forward iterator with mutable references.

Examples

use cs431_homework::LinkedList;

let mut list: LinkedList<u32> = LinkedList::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

for element in list.iter_mut() {
    *element += 10;
}

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), Some(&11));
assert_eq!(iter.next(), Some(&12));
assert_eq!(iter.next(), None);

pub fn is_empty(&self) -> bool

Returns true if the LinkedList is empty.

This operation should compute in O(1) time.

Examples

use cs431_homework::LinkedList;

let mut dl = LinkedList::new();
assert!(dl.is_empty());

dl.push_front("foo");
assert!(!dl.is_empty());

pub fn len(&self) -> usize

Returns the length of the LinkedList.

This operation should compute in O(1) time.

Examples

use cs431_homework::LinkedList;

let mut dl = LinkedList::new();

dl.push_front(2);
assert_eq!(dl.len(), 1);

dl.push_front(1);
assert_eq!(dl.len(), 2);

dl.push_back(3);
assert_eq!(dl.len(), 3);

pub fn clear(&mut self)

Removes all elements from the LinkedList.

This operation should compute in O(n) time.

Examples

use cs431_homework::LinkedList;

let mut dl = LinkedList::new();

dl.push_front(2);
dl.push_front(1);
assert_eq!(dl.len(), 2);
assert_eq!(dl.front(), Some(&1));

dl.clear();
assert_eq!(dl.len(), 0);
assert_eq!(dl.front(), None);

pub fn contains(&self, x: &T) -> bool

where T: PartialEq<T>,

Returns true if the LinkedList contains an element equal to the given value.

Examples

use cs431_homework::LinkedList;

let mut list: LinkedList<u32> = LinkedList::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

assert_eq!(list.contains(&0), true);
assert_eq!(list.contains(&10), false);

pub fn front(&self) -> Option<&T>

Provides a reference to the front element, or None if the list is empty.

Examples

use cs431_homework::LinkedList;

let mut dl = LinkedList::new();
assert_eq!(dl.front(), None);

dl.push_front(1);
assert_eq!(dl.front(), Some(&1));

pub fn front_mut(&mut self) -> Option<&mut T>

Provides a mutable reference to the front element, or None if the list is empty.

Examples

use cs431_homework::LinkedList;

let mut dl = LinkedList::new();
assert_eq!(dl.front(), None);

dl.push_front(1);
assert_eq!(dl.front(), Some(&1));

match dl.front_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(dl.front(), Some(&5));

pub fn back(&self) -> Option<&T>

Provides a reference to the back element, or None if the list is empty.

Examples

use cs431_homework::LinkedList;

let mut dl = LinkedList::new();
assert_eq!(dl.back(), None);

dl.push_back(1);
assert_eq!(dl.back(), Some(&1));

pub fn back_mut(&mut self) -> Option<&mut T>

Provides a mutable reference to the back element, or None if the list is empty.

Examples

use cs431_homework::LinkedList;

let mut dl = LinkedList::new();
assert_eq!(dl.back(), None);

dl.push_back(1);
assert_eq!(dl.back(), Some(&1));

match dl.back_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(dl.back(), Some(&5));

pub fn push_front(&mut self, elt: T)

Adds an element first in the list.

This operation should compute in O(1) time.

Examples

use cs431_homework::LinkedList;

let mut dl = LinkedList::new();

dl.push_front(2);
assert_eq!(dl.front().unwrap(), &2);

dl.push_front(1);
assert_eq!(dl.front().unwrap(), &1);

pub fn pop_front(&mut self) -> Option<T>

Removes the first element and returns it, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use cs431_homework::LinkedList;

let mut d = LinkedList::new();
assert_eq!(d.pop_front(), None);

d.push_front(1);
d.push_front(3);
assert_eq!(d.pop_front(), Some(3));
assert_eq!(d.pop_front(), Some(1));
assert_eq!(d.pop_front(), None);

pub fn push_back(&mut self, elt: T)

Appends an element to the back of a list.

This operation should compute in O(1) time.

Examples

use cs431_homework::LinkedList;

let mut d = LinkedList::new();
d.push_back(1);
d.push_back(3);
assert_eq!(3, *d.back().unwrap());

pub fn pop_back(&mut self) -> Option<T>

Removes the last element from a list and returns it, or None if it is empty.

This operation should compute in O(1) time.

Examples

use cs431_homework::LinkedList;

let mut d = LinkedList::new();
assert_eq!(d.pop_back(), None);
d.push_back(1);
d.push_back(3);
assert_eq!(d.pop_back(), Some(3));

Trait Implementations

impl<T: Clone> Clone for LinkedList<T>

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for LinkedList<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for LinkedList<T>

fn default() -> Self

Creates an empty LinkedList<T>.

impl<T> Drop for LinkedList<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> FromIterator<T> for LinkedList<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a LinkedList<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut LinkedList<T>

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IterMut<'a, T>

Creates an iterator from a value.

impl<T> IntoIterator for LinkedList<T>

fn into_iter(self) -> IntoIter<T>

Consumes the list into an iterator yielding elements by value.

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

impl<T: Ord> Ord for LinkedList<T>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq for LinkedList<T>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: PartialOrd> PartialOrd for LinkedList<T>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T: Eq> Eq for LinkedList<T>

impl<T: Send> Send for LinkedList<T>

impl<T: Sync> Sync for LinkedList<T>