Assignment 4: Lifetimes in Rust Solution

Linked List

A linked list is a linear data structure in which each element is a separate object. Every element in the list consists of two items:

    • The data of this element.

    • A reference to the next node.

The last node has a reference to an empty node. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty, then the head is an empty list.

A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application has to deal with an unknown number of objects within a linked list.

Source code: linked_list.rar

Question 1: Given the following implementation of a linked list in main.rs in the attached source code:


pub enum LinkedList<T>{
Tail,
Head(T,Box<LinkedList<T>>),
}

The code is missing the implementation for 4 functions, empty, new, push, and push_back.

a-    Implement the function empty to return an empty linked list. The function should have the following signature:


pub fn empty()->self{…}

b-    Implement the function new which creates a new linked list with the following signature:


pub fn new(t:T)->self{…}

c-    Implement the function push to insert a new element on the front of the list.

For example, if we have a list as follows:

2→3→5→7

.push(1) should result in the following list:

1→2→3→5→7




The function has the following signature:

1
ECE 421 | Exploring Software Development Domains



pub fn push(self, t:T)->self{

d-    Implement the function push_back to insert a new element at the back of the list. The function has the following signature:


pub fn push_back(self, t:T)->self{

Similarly, if we have a list as follows:

2→3→5→7

push_back(1) should result in the following list:

2→3→5→7→1

e- Run the tests defined in the main function and make sure that all the tests pass successfully. Question 2: Refer to the function cons (https://docs.rs/im/5.0.0/im/list/fn.cons.html) and

a-    provide an explanation of the function, the answer should provide a description of what the function does, and a detailed explanation of each parameter of the function.

b-    Update your code in question 1 to use the function cons. Please save the updated code in a different project with the name: linked_list_question2.rar

Question 3: Rust has a lot of smart pointers, such as Rc<T>, Arc<T>, Cell<T>, and RefCell<T>. Smart pointers wrap the contained values to provide extended functionality beyond that provided by references. Consider the following example:


enum Level {
Low,
Medium,
High
}

struct Task {
id: u8,
level: Level
}

fn main() {
let task = Task {

id: 10,
level: Level::High
};

task.id=100;
println!("Task with ID: {}", task.id);
}




2
ECE 421 | Exploring Software Development Domains


Executing the previous example should result in an error, mention the error and explain how interior mutability can be applied to the problem to solve it. Rewrite the previous code so it runs. (Hint: Consider using Cell<T>)

Skip List

A subway system can be expressed as a simple list of stops (expressed as a stop number):

c- stop_1 -> stop_2 -> stop_3 -> stop 4 -> stop 5 -> stop_6

However, some cities in Europe have something called express trains which reduce the number of stops to cover larger distances faster. Suppose someone wants to go from stop_1 to stop_5. Instead of seeing the doors open and close four times, they can switch between the express and the local at the third stop.

Express:    stop_1 -----------> stop_3 ---------------------> stop_6

Local:    stop_1 -> stop_2 -> stop_3 -> stop 4 -> stop 5 -> stop_6

The local service trains stops at every stop along the way, but the express service trains skips certain smaller stops only to halt at shared stations where travelers can switch between the two trains. The skipping happens quite literally on some stops where trains simply drive through, sometimes confusing tourists and locals alike.

Similarly, a skip list is essentially several lists, each at a different level. The lowest level contains all nodes, where the upper levels are their “express services” that can skip some nodes to get further ahead quicker. This results in a multilayered list, fused together only at certain nodes that have a connection on these particular levels:

next
-------|




next
-----------------------------------
> next
-------|

next
-------> next ---------------------
> next
-------|

next
-------> next -------
> next -------
> next
-------> next
-------|
1
2
3
4
5


Ideally, each level has half the number of nodes that the previous level has, which means that there needs to be a decision-making algorithm that can work with growing lists and still maintain this constraint. If this constraint is not kept, search times get worse, and in the worst-case scenario, it’s a regular linked list with a lot of overhead.

Question 4: Provide an implementation of skip list, as shown in the following figure, to complete the following code. Remember a skip list is a linked list -- this means the only element that can be directed accessed is the head, and you have to travel through elements to find the one you need. (Hint: you may reuse some of your code from questions 1 and 2)





3
ECE 421 | Exploring Software Development Domains















pub struct SkipList<T>{

//add your code here

}

impl<T> SkipList<T>{

fn new() -> self{

    • creates a new skip list. //add your code here

}

fn len(&self) -> usize{

    • returns the number of elements at level 0 of the skip list. //add your code here

}

fn is_empty(&self) -> bool{

    • checks if the skip list is empty. //add your code here

}

fn push(&mut self, value: T){

    • add an element with value T to the front of the skiplist. //add your code here

}

fn push_back(&mut self, value: T){

    • add an element with value T to the back of the skiplist. //add your code here

}

}

















4