Using Doubly Linked List, and Sorting methods: (In Java) (please attach your out
ID: 3805135 • Letter: U
Question
Using Doubly Linked List, and Sorting methods: (In Java) (please attach your output with the answer)
(Please answer if it is correct and working) (Have been getting many wrong and spam answers lately)
Introduction:
In this project, we use the same file structure of Artist and Art to extend the concepts of array and linked list and have them applied to sorting. The input files of p1arts.txt and p1artists.txt have been slightly modified. They are named p7arts.txt and p7artists.txt.
Assignments:
Implement a doubly linked list class so that you can use it to arrange the input file to produce the output similar to the following (Name this file p7out(yourName).txt:
Artistist ID
Artist Name
Art ID
Art Title
Appraised Value
1
Acconci
1038
Spring Flowers
800
1050
Cattle Ranch
10000
1103
Trail End
8000
2
Budd
1042
Coffee on the Trail
7544
3
Carpenter
1013
Superstitions
78000
1021
Bead Wall
14000
1034
Beaver Pole Jumble
28000
1063
Asleep in the Garden
110000
Your data structure should be an array of Artist and each artist will maintain a list that contains all his/her works in ascending order on ArtID. You may assume that p7artists.txt has been properly sorted and when you search for an artist, use Binary Search.
Design and implement your doubly linked list so that you will be able to place data in ascending order. There is plenty of information available online. For example, the following segment of code from the web should give you a good starting point
public class DoublyLinkedListImpl<E> {
private Node head;
private Node tail;
private int size;
public DoublyLinkedListImpl(){
size = 0;
}
/**
* this class keeps track of each element information
* @author java2novice
*/
private class Node {
E element;
Node next;
Node prev;
public Node(E element, Node next, Node prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
}
Hints:
This array of linked list is similar to what you did for project 3. The only differences are: (1) you need to have data arranged in order and (2) you need to use a doubly linked list.
What methods shall you include in your class? Be creative. You may just implement a minimal set of operations that enable you to sort the list in a convenient way.
p7artist.txt:
p7arts.txt:
For reference (Doubly Linked List implementation)
DoublyLinkedList.java:
import java.util.NoSuchElementException;
/*
* Java Program to Implement Doubly Linked List
*/
public class DoublyLinkedList<E>
{
private Node head;
private Node tail;
private int size;
public DoublyLinkedList()
{
size = 0;
}
/**
* this class keeps track of each element information
*
*/
private class Node
{
E element;
Node next;
Node prev;
public Node(E element, Node next, Node prev)
{
this.element = element;
this.next = next;
this.prev = prev;
}
}
/**
* returns the size of the linked list
* @return
*/
public int size()
{
return size;
}
/**
* return whether the list is empty or not
* @return
*/
public boolean isEmpty()
{
return size == 0;
}
/**
* adds element at the starting of the linked list
* @param element
*/
public void addFirst(E element) {
Node tmp = new Node(element, head, null);
if(head != null )
{
head.prev = tmp;
}
head = tmp;
if(tail == null)
{
tail = tmp;
}
size++;
System.out.println(element);
}
/**
* adds element at the end of the linked list
* @param element
*/
public void addLast(E element) {
Node tmp = new Node(element, null, tail);
if(tail != null)
{
tail.next = tmp;
}
tail = tmp;
if(head == null)
{
head = tmp;
}
size++;
System.out.println(element);
}
/**
* this method walks forward through the linked list
*/
public void iterateForward(){
System.out.println("iterating forward..");
Node tmp = head;
while(tmp != null)
{
System.out.println(tmp.element);
tmp = tmp.next;
}
}
/**
* this method walks backward through the linked list
*/
public void iterateBackward(){
System.out.println("iterating backward..");
Node tmp = tail;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.prev;
}
}
/**
* this method removes element from the start of the linked list
* @return
*/
public E removeFirst() {
if (size == 0) throw new NoSuchElementException();
Node tmp = head;
head = head.next;
head.prev = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
/**
* this method removes element from the end of the linked list
* @return
*/
public E removeLast() {
if (size == 0) throw new NoSuchElementException();
Node tmp = tail;
tail = tail.prev;
tail.next = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
public static void main(String a[]){
DoublyLinkedList<Integer> dll = new DoublyLinkedList<Integer>();
// Sample code
dll.addFirst(10);
dll.addFirst(100);
dll.addFirst(20);
dll.addFirst(200);
dll.addFirst(34);
dll.addLast(56);
dll.addLast(364);
dll.addLast(36);
dll.addLast(34);
dll.addLast(25);
dll.iterateForward();
dll.removeFirst();
dll.removeFirst();
dll.removeFirst();
dll.removeLast();
dll.removeLast();
dll.removeLast();
dll.iterateBackward();
}
}
Artistist ID
Artist Name
Art ID
Art Title
Appraised Value
1
Acconci
1038
Spring Flowers
800
1050
Cattle Ranch
10000
1103
Trail End
8000
2
Budd
1042
Coffee on the Trail
7544
3
Carpenter
1013
Superstitions
78000
1021
Bead Wall
14000
1034
Beaver Pole Jumble
28000
1063
Asleep in the Garden
110000
Explanation / Answer
import java.util.ListIterator; import java.util.NoSuchElementException; public class DoublyLinkedList implements Iterable { private int n; // number of elements on list private Node pre; // sentinel before first item private Node post; // sentinel after last item public DoublyLinkedList() { pre = new Node(); post = new Node(); pre.next = post; post.prev = pre; } // linked list node helper data type private class Node { private Item item; private Node next; private Node prev; } public boolean isEmpty() { return n == 0; } public int size() { return n; } // add the item to the list public void add(Item item) { Node last = post.prev; Node x = new Node(); x.item = item; x.next = post; x.prev = last; post.prev = x; last.next = x; n++; } public ListIterator iterator() { return new DoublyLinkedListIterator(); } // assumes no calls to DoublyLinkedList.add() during iteration private class DoublyLinkedListIterator implements ListIterator { private Node current = pre.next; // the node that is returned by next() private Node lastAccessed = null; // the last node to be returned by prev() or next() // reset to null upon intervening remove() or add() private int index = 0; public boolean hasNext() { return index 0; } public int previousIndex() { return index - 1; } public int nextIndex() { return index; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); lastAccessed = current; Item item = current.item; current = current.next; index++; return item; } public Item previous() { if (!hasPrevious()) throw new NoSuchElementException(); current = current.prev; index--; lastAccessed = current; return current.item; } // replace the item of the element that was last accessed by next() or previous() // condition: no calls to remove() or add() after last call to next() or previous() public void set(Item item) { if (lastAccessed == null) throw new IllegalStateException(); lastAccessed.item = item; } // remove the element that was last accessed by next() or previous() // condition: no calls to remove() or add() after last call to next() or previous() public void remove() { if (lastAccessed == null) throw new IllegalStateException(); Node x = lastAccessed.prev; Node y = lastAccessed.next; x.next = y; y.prev = x; n--; if (current == lastAccessed) current = y; else index--; lastAccessed = null; } // add element to list public void add(Item item) { Node x = current.prev; Node y = new Node(); Node z = current; y.item = item; x.next = y; y.next = z; z.prev = y; y.prev = x; n++; index++; lastAccessed = null; } } public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) s.append(item + " "); return s.toString(); } // a test client public static void main(String[] args) { int n = Integer.parseInt(args[0]); // add elements 1, ..., n StdOut.println(n + " random integers between 0 and 99"); DoublyLinkedList list = new DoublyLinkedList(); for (int i = 0; iRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.