Hello, im having trouble with this question. I get how the logic behind it and t
ID: 3809132 • Letter: H
Question
Hello, im having trouble with this question. I get how the logic behind it and the implementation of regular linked lists, however, implementing a sorted one is tough for me and I can't find a good source to learn how to do it. I'd really appreciate some help.
override method add(E e) so as to insert the element into a new node in an ordered list.
rewrite methods addFirst(E e), addLast(E e) and add(int index, E e) so as to insert the element into a new node in an ordered list.
implement methods contains(E e), get(int index), indexOf(E e), lastIndexOf(E e) and set(int index, E e) making any changes necessary to the code that improves efficiency for an ordered list.
Add code to to demonstrate that these methods work correctly.
to answer more info: with ordered list you need addfirst and addlast to check whether or not the element is greater than the tail or less than the head before adding
public class MyOrderedLinkedList extends MyAbstractList {
private Node head, tail;
/**Create a default list*/
public MyOrderedLinkedList() {
}
/**Create a list from an array of objects*/
public MyOrderedLinkedList(E[] objects) {
super(objects);
}
// **************************************************************
// **************************************************************
/** Add a new element to the list in order.*/
// **************************************************************
// **************************************************************
public void add(E e) {
}
/**Return the head element in the list*/
public E getFirst() {
if (size == 0) {
return null;
} else {
return head.element;
}
}
/**Return the last element in the list*/
public E getLast() {
if (size == 0) {
return null;
} else {
return tail.element;
}
}
// **************************************************************
// **************************************************************
/**Must be rewritten to add a new element to the list in order.*/
// **************************************************************
// **************************************************************
public void addFirst(E e) {
Node newNode = new Node(e); // Create a new node
newNode.next = head; // link the new node with the head
head = newNode; // head points to the new node
size++; // Increase list size
if (tail == null) // the new node is the only node in list
{
tail = head;
}
}
// **************************************************************
// **************************************************************
/**Must be rewritten to add a new element to the list in order.*/
// **************************************************************
// **************************************************************
public void addLast(E e) {
Node newNode = new Node(e); // Create a new for element e
if (tail == null) {
head = tail = newNode; // The new node is the only node in list
} else {
tail.next = newNode; // Link the new with the last node
tail = tail.next; // tail now points to the last node
}
size++; // Increase size
}
@Override
// **************************************************************
// **************************************************************
/**Must be rewritten to add a new element to the list in order.*/
// **************************************************************
// **************************************************************
public void add(int index, E e) {
if (index == 0) {
addFirst(e);
} else if (index >= size) {
addLast(e);
} else {
Node current = head;
for (int i = 1; i < index; i++) {
current = current.next;
}
Node temp = current.next;
current.next = new Node(e);
(current.next).next = temp;
size++;
}
}
// **************************************************************
// **************************************************************
/**Must be rewritten to do nothing and return null.*/
// **************************************************************
// **************************************************************
public E removeFirst() {
if (size == 0) {
return null;
} else {
Node temp = head;
head = head.next;
size--;
if (head == null) {
tail = null;
}
return temp.element;
}
}
// **************************************************************
// **************************************************************
/**Must be rewritten to do nothing and return null.*/
// **************************************************************
// **************************************************************
public E removeLast() {
if (size == 0) {
return null;
} else if (size == 1) {
Node temp = head;
head = tail = null;
size = 0;
return temp.element;
} else {
Node current = head;
for (int i = 0; i < size - 2; i++) {
current = current.next;
}
Node temp = tail;
tail = current;
tail.next = null;
size--;
return temp.element;
}
}
@Override
/**Remove the element at the specified position in this list. Return the
* element that was removed from the list.*/
public E remove(int index) {
if (index < 0 || index >= size) {
return null;
} else if (index == 0) {
return removeFirst();
} else if (index == size - 1) {
return removeLast();
} else {
Node previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node current = previous.next;
previous.next = current.next;
size--;
return current.element;
}
}
@Override
/**Override toString() to return elements in the list*/
public String toString() {
StringBuilder result = new StringBuilder("[");
Node current = head;
for (int i = 0; i < size; i++) {
result.append(current.element);
current = current.next;
if (current != null) {
result.append(", "); // Separate two elements with a comma
} else {
result.append("]"); // Insert the closing ] in the string
}
}
return result.toString();
}
@Override
/**Clear the list*/
public void clear() {
size = 0;
head = tail = null;
}
@Override
/**Return true if this list contains the element e*/
public boolean contains(E e) {
if (size == 0) {
return false;
} else {
Node current = head;
while (current != null) {
if (current.element == e) {
return true;
}
current = current.next;
}
}
return false;
}
@Override
/**Return the element at the specified index*/
public E get(int index) {
if (index < 0 || index >= size) {
return null; // Out of range
} else if (index == 0) {
return getFirst();
} else if (index == size - 1) {
return getLast();
} else {
Node current = head.next;
for (int i = 1; i < index; i++) {
current = current.next;
}
return current.element;
}
}
@Override
/**Return the index of the head matching element in this list. Return -1 if
* no match.*/
public int indexOf(E e) {
if (head.element == e) {
return 0;
} else if (tail.element == e) {
return size - 1;
} else {
Node current = head.next;
int index = 1;
while (current != null) {
if (current.element == e) {
return index;
}
current = current.next;
index++;
}
}
return -1;
}
@Override
/**Return the index of the last matching element in this list. Return -1 if
* no match.*/
public int lastIndexOf(E e) {
int index = -1;
Node current = head;
for (int i = 0; i < size; i++) {
if (current.element == e) {
index = i;
}
current = current.next;
}
return index;
}
@Override
/**Replace the element at the specified position in this list with the
* specified element.*/
public E set(int index, E e) {
if (index < 0 || index > size - 1) {
return null;
} else {
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
current.element = e;
return current.element;
}
}
@Override
/**Override iterator() defined in Iterable*/
public java.util.Iterator iterator() {
return new LinkedListIterator();
}
private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
private class LinkedListIterator
implements java.util.Iterator {
private Node current = head; // Current index
@Override
public boolean hasNext() {
return (current != null);
}
@Override
public E next() {
E e = current.element;
current = current.next;
return e;
}
@Override
public void remove() {
System.out.println("Implementation left as an exercise");
}
} // end of LinkedListIterator
private static class Node {
E element;
Node next;
public Node(E element) {
this.element = element;
}
} // end of Node
public abstract class MyAbstractList implements MyList {
protected int size = 0; // The size of the list
/**Create a default list*/
protected MyAbstractList() {
}
/**Create a list from an array of objects*/
protected MyAbstractList(E[] objects) {
for (int i = 0; i < objects.length; i++) {
add(objects[i]);
}
}
@Override
/**Return true if this list contains no elements*/
public boolean isEmpty() {
return size == 0;
}
@Override
/**Return the number of elements in this list*/
public int size() {
return size;
}
@Override
// **************************************************************
// **************************************************************
/**Remove the first occurrence of the element e from this list. Shift any
* subsequent elements to the left. Return true if the element is removed.
* Must be overridden to avoid multiple calls to indexOf.
*/
// **************************************************************
// **************************************************************
public boolean remove(E e) {
int i = indexOf(e);
if (i >= 0) {
remove(i);
remove(e); //call this method again to go through the list again to see if theres another occurrence
return true;
} else {
return false;
}
}
}
Explanation / Answer
Hey, there should not be addFirst and addLast for sorted linked list method because in sorted linked list the index of element is determined by the value of data. The method set(int index, E e) also not possible for sorted linked list use add method insted. Other methods contains(E e), get(int index), indexOf(E e), lastIndexOf(E e) works same for sorted linked list. So you need to change your add method:
public void add(E e) {
Node newNode = new Node(e);// Create a new node
if (head == null || tail == null) { // the new node is the only node in list
newNode.next = head; // link the new node with the head
head = newNode; // head points to the new node
if (tail == null) {
tail = head;
}
} else if (e >= tail.element) { // new node is greater then tail
tail.next = newNode; // Link the new with the last node
tail = tail.next; // tail now points to the last node
} else if (e <= head.element) { // new node is smaller then head
newNode.next = head; // link the new node with the head
head = newNode; // head points to the new node
} else {
Node current = head;
for (int i = 1; i <= size; i++) {
if(current.elememt >= e) {
break;
}
current = current.next;
}
Node temp = current.next;
current.next = new Node(e);
(current.next).next = temp;
}
size++; // Increase size
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.