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}