Using Doubly Linked List, and Sorting methods: Introduction: In this project, we
ID: 3801330 • Letter: U
Question
Using Doubly Linked List, and Sorting methods:
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.
This project covers the materials up to chapter 18 of your textbook.
Description:
As you have learned so far that array is a very efficient way of handling a collection of related data, but the problem is that the size needs to be predetermined and storage needs to be reserved. However, in many real world applications, the amount of data is hard to predict. So, we will need to employ dynamic memory allocation approach, which means we allocate storage only when needed.
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:
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
package com.java2novice.ds.linkedlist;
import java.util.NoSuchElementException;
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;
}
}
/**
* 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("adding: "+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("adding: "+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 backword..");
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[]){
DoublyLinkedListImpl<Integer> dll = new DoublyLinkedListImpl<Integer>();
dll.addFirst(10);
dll.addFirst(34);
dll.addLast(56);
dll.addLast(364);
dll.iterateForward();
dll.removeFirst();
dll.removeLast();
dll.iterateBackward();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.