[−][src]Struct skip_linked_list::list::SkipLinkedList
SkipLinkedList
SkipLinkedList
is a skiplist-backed linked-list that supports fast random access.
The (amortized) time complexity is O(log n)
for both reads and writes, regardless of the position.
It is more efficient than Vec
and Linkedlist
for large list that requires lots of random access.
Examples
let mut list = skip_linked_list::SkipLinkedList::new(); list.push_front(1); list.push_back(2); list.insert(1, 3); list.insert(1, 4); list.insert(1, 5); // current list is: [1, 5, 4, 3, 2] assert_eq!(list.get(1), Some(&5)); assert_eq!(list.get(3), Some(&3)); assert_eq!(list.remove(2), 4);
Implementations
impl<T> SkipLinkedList<T>
[src]
pub fn new() -> Self
[src]
Creates a new list.
pub fn insert(&mut self, i: usize, elem: T)
[src]
Inserts an element at position index within the list, shifting all elements after it to the right.
Examples
let mut list = skip_linked_list::SkipLinkedList::new(); list.insert(0, 10); list.insert(1, 30); list.insert(1, 20); assert_eq!(list.into_iter().collect::<Vec<i32>>(), vec![10, 20, 30]);
Panics
Panics if i > len
.
pub fn get(&self, i: usize) -> Option<&T>
[src]
Gets the element at position index within the list.
Examples
let mut list = skip_linked_list::SkipLinkedList::new(); list.insert(0, 10); assert_eq!(list.get(0), Some(&10)); assert_eq!(list.get(1), None);
pub fn remove(&mut self, i: usize) -> T
[src]
Removes an element at position index within the list, shifting all elements after it to the left.
Examples
let mut list = skip_linked_list::SkipLinkedList::new(); list.insert(0, 10); list.insert(1, 20); assert_eq!(list.remove(0), 10); assert_eq!(list.remove(0), 20);
Panics
Panics if i >= len
.
pub fn len(&self) -> usize
[src]
Returns the length of the list.
pub fn push_front(&mut self, elem: T)
[src]
Inserts an element at the start of the list.
pub fn push_back(&mut self, elem: T)
[src]
Inserts an element at the end of the list.
pub fn pop_front(&mut self) -> T
[src]
pub fn pop_back(&mut self) -> T
[src]
pub fn iter(&self) -> Iter<'_, T>ⓘ
[src]
Returns an iterator over the list.
pub fn iter_mut(&mut self) -> IterMut<'_, T>ⓘ
[src]
Returns an mut iterator over the list.
pub fn into_iter(self) -> IntoIter<T>ⓘ
[src]
Consumes the list into an iterator.
impl<T> SkipLinkedList<T> where
T: Display,
[src]
T: Display,
Trait Implementations
impl<T> Drop for SkipLinkedList<T>
[src]
Auto Trait Implementations
impl<T> RefUnwindSafe for SkipLinkedList<T> where
T: RefUnwindSafe,
[src]
T: RefUnwindSafe,
impl<T> !Send for SkipLinkedList<T>
[src]
impl<T> !Sync for SkipLinkedList<T>
[src]
impl<T> Unpin for SkipLinkedList<T>
[src]
impl<T> UnwindSafe for SkipLinkedList<T> where
T: RefUnwindSafe + UnwindSafe,
[src]
T: RefUnwindSafe + UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
pub fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,