001package algs13;
002
003// Part 3: MyListDrawing. Practice drawing lists.
004//
005// This is a "written homework" assignment. You do NOT need to submit this file with solutions as part of this homework.
006// You DO need to submit your answers to the questions posed below.
007//
008// Look for the TODO below, in the main method. Hand in your drawings of the lists requested.
009
010public class MyListDrawing {
011
012    private Node first;
013    private int N;
014
015    private static class Node {
016        final double item;
017        Node next;
018
019        Node(double item, Node next) {
020            this.item = item;
021            this.next = next;
022        }
023    }
024
025    public void insert(double item) {
026        if (first == null || first.item >= item) {
027            first = new Node(item, first);
028        } else {
029            Node x = first;
030            while (x.next != null && x.next.item < item) {
031                x = x.next;
032            }
033            x.next = new Node(item, x.next);
034        }
035        N++;
036    }
037
038    public void delete (int k) {
039        if (k < 0 || k >= N) throw new IllegalArgumentException ();
040        if(k == 0) first = first.next;
041        else {
042            Node prev = first;
043            for(int i = 1; i < k; i++) {
044                prev = prev.next;
045            }
046            prev.next = prev.next.next;
047        }
048        N--;
049    }
050
051    public static void main(String[] args) {
052        MyListDrawing list1 = listOf(4, 7, 9, 11);
053        list1.insert(3);
054
055        MyListDrawing list2 = listOf(4, 7, 9, 11);
056        list2.insert(8);
057
058        MyListDrawing list3 = listOf(4, 7, 9, 11);
059        list3.insert(13);
060
061        MyListDrawing list4 = listOf(4, 7, 9, 11);
062        list4.delete(0);
063
064        MyListDrawing list5 = listOf(4, 7, 9, 11);
065        list5.insert(10);
066        list5.insert(12);
067        list5.delete(2);
068
069        // TODO: Draw each list declared above, i.e. list1, list2, list3, list4, list5, before the main program exits.
070
071        // NOTE: On an exam, you will obviously not have the Trace utility available to you. You need to be
072        // able to look at code that operates on linked structures and draw the result. You should try
073        // to understand how this code is manipulating the pointers in the list. You are welcome to test your understanding
074        // with Trace, if you so choose, but do not rely on it to do the work for you - you need to develop your
075        // understanding of linked structures!
076    }
077
078    private static MyListDrawing listOf(double... items) {
079        Node next = null;
080        for (int i = items.length - 1; i >= 0; i--) {
081            next = new Node(items[i], next);
082        }
083        MyListDrawing list = new MyListDrawing();
084        list.first = next;
085        list.N = items.length;
086        return list;
087    }
088}