#Build a linked list in rust

44 messages · Page 1 of 1 (latest)

wet fossil
#

in rust, create a linked list implementing the following trait and write tests to prove its efficiency.


pub trait List<T> {
    /// Insert an item into a position in the list
    fn insert(&mut self, index: usize, item: T);
    
    /// Remove an item from the list at the provided position
    fn remove(&mut self, index: usize) -> Option<T>;
  
    /// Get the item at the provided position
    /// Returns Option::None if not found
    fn get(&self, index: usize) -> Option<&T>;
  
    /// Search the list for the the first instance of the item. 
    /// If found return its position
    fn find(&self, item: T) -> Option<usize>;
}


There are many resources out on the internet that can help you solve this. Many of which provide direct solutions. Remember this is all for fun and don't spoil it for others!

worldly jacinth
#

Here for the dog*** rant guy

rustic flame
#

lowkey, I got no idea what rust even is

true sable
worldly jacinth
true sable
#

||(there's a meme that all rust users are femboys)||

worldly jacinth
frosty pier
#

ig I'll have to learn rust, be back in a couple days 👋

frosty pier
#

Spoiler

knotty wave
#

first time coding in rust, i just looked up some basic tutorials and wrote this in a text editor

frosty pier
#

You can /spoiler your code

#

You don't have to use ||

knotty wave
#

not with files

#

you cant see anything except the part the question gives so the expand button is essentially the same as a spoiler 🙂

frosty pier
#

Well ye ig file also works

frosty pier
jolly obsidian
#

(source: i do cpp)

jolly obsidian
crimson swift
jolly obsidian
#

yes, but it will involve more effort than if you have some background in programming

#

same as any of the other questions, really

wind spade
wet fossil
#

@narrow spear

narrow spear
wind spade
narrow spear
#

I'm still practically new to rust compared to others, but from my knowledge, T can only be sized. Someone correct me if I'm wrong but because it is needing to be stored in a struct somewhere, it needs to be a basic struct, or a Boxed value

wind spade
#

That's why I asked if T was sized. If T is sized, then I can just embed T without boxes, thus using only the stack and making the whole list a lot faster

#

just realized that while T may not be sized, Box<T> definitely is, so I can just make a sized pointer to the data, including boxed values, so that I don't need to touch heap-allocated fat pointers.

narrow spear
wind spade
narrow spear
#

they are reasonable assumptions

past forge
#

||se std::cell::RefCell; use std::rc::Rc; #[derive(Debug)] struct Node < T > { item: T, next: Option < Rc < RefCell < Node < T >>> > , } #[derive(Debug)] struct LinkedList < T > { head: Option < Rc < RefCell < Node < T >>> > , length: usize, } impl < T > List < T > for LinkedList < T > { fn insert( & mut self, index: usize, item: T) { let new_node = Rc::new(RefCell::new(Node { item, next: None, })); if index == 0 { if let Some(head) = & self.head { new_node.next = Some(Rc::clone(head)); } self.head = Some(Rc::clone( & new_node)); } else { let mut current = self.head.as_ref().unwrap().borrow_mut(); for _ in 1..index { current = current.next.as_ref().unwrap().borrow_mut(); } new_node.next = current.next.take(); current.next = Some(Rc::clone( & new_node)); } self.length += 1; } fn remove( & mut self, index: usize) - > Option < T > { if index >= self.length { None } else { let mut current = self.head.as_ref().unwrap().borrow_mut(); if index == 0 { let removed_item = current.item.clone(); self.head = current.next.take(); self.length -= 1; Some(removed_item) } else { for _ in 1..index { current = current.next.as_ref().unwrap().borrow_mut(); } let removed_item = current.next.as_ref().unwrap().borrow_mut().item.clone(); current.next = current.next.as_ref().unwrap().borrow_mut().next.take(); self.length -= 1; Some(removed_item) } } } ||

#

||fn get( & self, index: usize) - > Option < & T > { if index >= self.length { None } else { let mut current = self.head.as_ref().unwrap().borrow_mut(); for _ in 0..index { current = current.next.as_ref().unwrap().borrow_mut(); } Some( & current.item) } } fn find( & self, item: T) - > Option < usize > where T: PartialEq, { let mut current = self.head.as_ref().unwrap().borrow_mut(); let mut index = 0; while let Some(node) = current.next.as_ref() { if node.borrow().item == item { return Some(index); } current = node.borrow_mut(); index += 1; } None } } #[cfg(test)] mod tests { use super:: * ; #[test] fn test_insert() { let mut list = LinkedList::new(); list.insert(0, 1); list.insert(1, 2); list.insert(0, 0); assert_eq!(list.get(0), Some( & 0)); assert_eq!(list.get(1), Some( & 1)); assert_eq!(list.get(2), Some( & 2)); } #[test] fn test_remove() { let mut list = LinkedList::new(); list.insert(0, 1); list.insert(1, 2); list.insert(2, 3); assert_eq!(list.remove(1), Some(2)); assert_eq!(list.get(1), Some( & 3)); assert_eq!(list.get(2), None); } #[test] fn test_get() { let mut list = LinkedList::new(); list.insert(0, 1); list.insert(1, 2); list.insert(2, 3); assert_eq!(list.get(0), Some( & 1)); assert_eq!(list.get(1), Some( & 2)); assert_eq!(list.get(2), Some( & 3)); assert_eq!(list.get(3), None); } #[test] fn test_find() { let mut list = LinkedList::new(); list.insert(0, 1); list.insert(1, 2); list.insert(2, 3); assert_eq!(list.find(2), Some(1)); assert_eq!(list.find(4), None); } }||

#

In this implementation, I used a singly linked list with nodes that contain a reference-counted reference to the next node. The insert method adds a new node at the specified index, the remove method removes a node at the specified index andreturns its item, the get method returns a reference to the item at the specified index, and the find method returns the index of the first occurrence of the specified item.

The tests demonstrate the efficiency of the implementation by inserting, removing, and finding items in the list. The tests use the Option type to handle edge cases, and the PartialEq trait to enable equality comparison in the find method.

Note that the implementation is not optimized for large lists, as it uses a linear time algorithm for some operations. If efficiency is a concern for large lists, a more complex data structure such as a hash table or a binary search tree may be more appropriate.

jolly obsidian
past forge
wet fossil
wet fossil
thorn reef
#

so what does this do (ping with response)

jolly obsidian