The UnorderedList class provides an unordered list. It implements the ListInterf

Question

The UnorderedList class provides an unordered list. It implements the ListInterface as defined in our textbook. You will be given most of the methods, and the list node class. You will have to complete the class by writing the following methods:

add: the add method will add the new element at the end of the list

remove: the remove method will remove the given element from the list

// unordered singly linked list
// fields:
// head and tail
// length
// current (used by first and next to iterate through list)
// interface (from Dale):
// size returns the number of elements
// add(T item) adds item to this list (add at end)
// remove (T item) removes item and returns true;
// if not found returns false.
// contains (T item) returns true if the list contains item;
// otherwise, returns false.
// get(T item) returns an element such that item.equals(element);
// if no such element exists, returns null.
// toString() returns a formatted string that represents the list
// reset() initializes current to the first element on the list
// getNext() returns the element at the current position on the list
// if current is not at end, advances current to next
// if current is at end, advances current to first
// preconditions: list is not empty, list has been reset,
// list has not been modified since most recent reset

public class unorderedList<T> implements ListInterface<T> {

private listNode<T> head;
private listNode<T> tail;
private int length;
private listNode<T> current;

// initialize the empty list
public unorderedList() {
tail = null;
head = null;
length = 0;
current = head;
}

// add new item at end of list
public void add(T item)
{
       //YOUR CODE HERE
}

// return the number of elements in the list
public int size() {
return length;
}

// remove item from list
public boolean remove(T item)
{

//YOUR CODE HERE

}

// set current to first element in list (or null if list is empty)
public void reset() {
current = head;
}

// return current element and move to next element in list
// move back to head if there is no next element
// assumes list is not null!!
public T getNext() {
       T element = current.getElement();
if (current == tail)
current = head;
else
current = current.getSuccessor();
return element;
}

// return true if element is in the list, otherwise return false
public boolean contains (T element) {
listNode<T> curr = find(element);
if (curr != null)
return true;
return false;
}

// returns a list item that matches element
public T get(T element) {
   listNode<T> curr = find(element);
   if (curr != null)
   return curr.getElement();
   return null;
}

// Returns a nicely formatted string that represents this list.
public String toString() {
   String result = "The list: ";
   listNode<T> curr = head;
   while (curr != null) {
       result = result + " " + curr.getElement() + " ";
       curr = curr.getSuccessor();
   }
   return result;
}

// private method to find the node that contains item
// return the node or null if not found
private listNode<T> find(T item) {
listNode<T> curr = head;
while (curr != null && !curr.getElement().equals(item)) {
curr = curr.getSuccessor();
}
if (curr != null)
return curr;
return null;
}

}

Explanation / Answer

struct node { int data; struct node *next; struct node *previous; }; struct listset { struct node *head; struct node *tail; int length =0; int current_elements; }; struct listset * new_listset(){ struct listset *new_list = malloc(size()); new_list ->head = NULL; new_list ->tail = NULL; return new_list; }; struct node *unorderList(struct listset *this, int item){ struct node *curr_elem = this->head; if(!curr_elem) return NULL; while(item != curr_elem->data){ if(curr_elem->next==NULL)return NULL; curr_elem = curr_elem->next; } return curr_elem; } void listset_add(struct listset *this, int item){ struct node *new_node = malloc(size()); new_node -> data = item; new_node ->next = NULL; if(!this->head) { new_node->previous = NULL; this->head = this->tail = new_node; } else{ this->tail->next = new_node; } this->current_elements++; } void listset_remove(struct listset *this, int item){ struct node *elem_remove = unorderList(this, item); if(!elem_remove) return; if(elem_remove->next && elem_remove->previous) elem_remove->previous->next = elem_remove->next; else if (elem_remove->previous && !elem_remove->previous){ elem_remove->previous->next=NULL; this->tail = elem_remove->previous; } else{ this->tail = NULL; this->head = NULL; } free(elem_remove); } void listset_contain(struct listset *this, int item){ struct node *elem_contain = unorderList(this, item); if(!elem_contain) return; if(elem_contain->next && elem_contain->previous) elem_contain->previous->next = elem_contain->next; else if (elem_remove->previous && !elem_remove->previous){ printf("%d",elem_contain->previous->next); } else{ print(" No Element found "); } } void listset_get(struct node *head, int key) { while (head != NULL) { if (head->a == key) { printf("key found "); return; } head = head->next; } printf("Key not found "); } void listset_reset(struct listset *this){ struct node *reset = unorderList(this); reset->current_element = reset->head; } int size() { struct listset x; x->length=sizeof(struct node); return x->length; } static void listset_print(const struct listset *list) { struct node *n = list->head; while (n) { printf("%d ", n->data); n = n->next; } printf(" : "); n = list->tail; while (n) { printf("%d ", n->data); n = n->previous; } printf(" "); } int main(void) { struct listset *list = new_listset(); struct node *node1= new_node(); listset_add(list, 6); listset_add(list, 3); listset_add(list, 1); listset_add(list, 4); listset_add(list, 2); listset_print(list); listset_contain(list,1); listset_get(node1,1); listset_remove(list, 6); listset_reset(list); listset_contain(list,3); listset_get(node1,5); listset_print(list); listset_remove(list, 1); listset_contain(list,6); listset_print(list); listset_remove(list, 5); listset_print(list); listset_reset(list); listset_remove(list, 3); listset_contain(list,5); listset_get(node1,4); listset_print(list); listset_remove(list, 2); listset_print(list); listset_remove(list, 4); listset_print(list); return 0; }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.