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:

1       Acconci
2       Budd
3       Carpenter
4       Dill
5       Edwards
6       Fleming
7       Garber
8       Higgins
9       Ibe
10      Kollasch
11      Lerman
12      Metz
13      Novarre
14      Ortega
15      Parker
16      Penn
17      Pierobon
18      Prinzen
19      Quiroz
20      Rath

p7arts.txt:

1038    Spring Flowers  1       800
1050    Cattle Ranch    1       10000
1103    Trail End       1       8000
1042    Coffee on the Trail     2       7544
1013    Superstitions   3       78000
1021    Bead Wall       3       14000
1034    Beaver Pole Jumble      3       28000
1063    Asleep in the Garden    3       110000
1070    Beginnings      4       27500
1036    Blackhawk       5       25500
1017    Brittlecone     6       1300
1053    Blue Eyed Indian        6       40000
1056    Cavalry Is Coming       6       1900
1075    Western Boots and Spurs 6       6000
1077    Bull Riding     6       5200
1049    Buttercup with Red Lip  7       400
1018    Mountain Scene  8       2500
1055    Starlit Evening 9       9500
1096    Ceremonial Sticks       10      15000
1090    Off the Grid    11      8000
1003    Spring Flowers  12      2400
1081    Coming Under Fire       13      650
1039    Treachery       14      20000
1102    Crying Hats     14      10000
1073    Dancing in the Light    15      4000
1052    American Rodeo  16      3500
1059    Dwelling        17      16000
1005    The Hang        18      8000
1011    Eve     19      975
1099    Watch That Rattler      20      900
1037    Floating World  7       2350
1109    Friends 8       16000
1084    Crossing the Platt River        9       2200
1072    Funnel  10      4500
1115    Starry Night    11      8500
1008    End of the Path 12      1900
1112    Dark Canyon     13      8000
1009    Amen    14      3000
1030    Ash Bench       14      13000
1043    Creosote Bushes 15      18000
1078    Chuckwagon      16      32000
1041    Night Version   17      3800
1082    Spring Flowers  18      20000
1116    Apache Warrior  19      23000
1029    Horseshoe Falls 20      15000
1006    House Remembered        14      700
1046    Immediate Gratification 14      1500
1031    Inside/Out      15      3500
1107    Striking It Rich        16      1750
1051    Night Version   17      7000
1088    Lessons 18      3700
1045    Leaf Patterns   19      2100
1100    Hungry Cowboys  20      750
1094    Life Is Sweet   18      25000
1106    Horse Corral    19      12500
1062    Cowboy and Saddle       20      18000
1032    Rising Sun      7       2000
1060    Story Sticks    8       650
1044    Mexican Fiesta  9       14000
1047    Medicine Man    10      2500
1014    Plenty  14      500
1015    Punch   14      10000
1023    Shooting the Rapids     15      1300
1027    Mountain Climber        16      4700
1035    Nature/Nurture  17      1300
1040    Night on the Praire     18      1300
1065    Moonlite        19      1300
1092    Dressing Up     20      1300
1024    Spirit and Nature       7       592
1067    Owl in Flight   8       7000
1001    Red Rock Mountain       9       18000
1028    Tired Cowboy    10      4700
1054    Snake Charmer   7       4500
1068    Moonlight       8       9750
1069    Renaissance     9       5500
1113    Shadow House    10      5500
1114    Storytelling at the Campfire    7       18000
1064    Spirit Columns  8       7000
1002    Offerings       9       10000
1089    Life Lessons    10      4125
1091    Stone Palette   7       11500
1074    Storm on the Rise       8       8000
1098    Sweet Project   9       592
1048    Comfy Chair     10      800
1101    The Red Door    2       10000
1080    The Dust Behind 3       18000
1058    The Gathering   3       250
1019    The White Heart 3       9300
1095    The Spirit      3       20000
1079    Carrying the Mail       4       8000
1093    Antelopes       5       12500
1110    Three Sisters   6       6500
1085    Traces  6       20000
1004    Seeking Shelter 6       52000
1083    Untitled        6       2500
1016    Untitled        6       6000
1026    Untitled (couple)       7       4000
1057    Untitled        8       4500
1086    Untitled (desert landscape)     2       18000
1025    Profile of a Woman      3       625
1022    The Cowboy      3       4200
1104    Untitled        3       1800
1010    Untitled (land with adobe)      3       800
1111    Untitled (man and crucifix)     4       3200
1020    Untitled (Man holding coat)     5       3000
1012    Man on Horseback        6       8000
1097    Untitled (Sea)  6       2800
1066    Untitled (still life)   6       19500
1033    Untitled (Woman abstract)       6       2500
1108    Untitled Mural  6       400
1061    Untitled Mural  7       3520
1071    Ride the Rapids 8       300
1076    Ride the Bronco 14      1500
1105    Meteor Show     15      10000
1087    Three Woman     16      20000
1007    Homage to the Ancestors 17      1200

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();
}
}

Answer 1

import java.util.ListIterator;
import java.util.NoSuchElementException;

public class DoublyLinkedList<Item> implements Iterable<Item> {
    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<Item> iterator()  { return new DoublyLinkedListIterator(); }

    // assumes no calls to DoublyLinkedList.add() during iteration
    private class DoublyLinkedListIterator implements ListIterator<Item> {
        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 < n; }
        public boolean hasPrevious()  { 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<Integer> list = new DoublyLinkedList<Integer>();
        for (int i = 0; i < n; i++)
            list.add(StdRandom.uniform(100));
        StdOut.println(list);
        StdOut.println();

        ListIterator<Integer> iterator = list.iterator();

        // go forwards with next() and set()
        StdOut.println("add 1 to each element via next() and set()");
        while (iterator.hasNext()) {
            int x = iterator.next();
            iterator.set(x + 1);
        }
        StdOut.println(list);
        StdOut.println();

        // go backwards with previous() and set()
        StdOut.println("multiply each element by 3 via previous() and set()");
        while (iterator.hasPrevious()) {
            int x = iterator.previous();
            iterator.set(x + x + x);
        }
        StdOut.println(list);
        StdOut.println();


        // remove all elements that are multiples of 4 via next() and remove()
        StdOut.println("remove elements that are a multiple of 4 via next() and remove()");
        while (iterator.hasNext()) {
            int x = iterator.next();
            if (x % 4 == 0) iterator.remove();
        }
        StdOut.println(list);
        StdOut.println();


        // remove all even elements via previous() and remove()
        StdOut.println("remove elements that are even via previous() and remove()");
        while (iterator.hasPrevious()) {
            int x = iterator.previous();
            if (x % 2 == 0) iterator.remove();
        }
        StdOut.println(list);
        StdOut.println();


        // add elements via next() and add()
        StdOut.println("add elements via next() and add()");
        while (iterator.hasNext()) {
            int x = iterator.next();
            iterator.add(x + 1);
        }
        StdOut.println(list);
        StdOut.println();

        // add elements via previous() and add()
        StdOut.println("add elements via previous() and add()");
        while (iterator.hasPrevious()) {
            int x = iterator.previous();
            iterator.add(x * 10);
            iterator.previous();
        }
        StdOut.println(list);
        StdOut.println();
    }
}