/*****************************************************************************/ /* */ /* Singly-Linked List Manipulation: Graphical Version */ /* */ /* January 1999, Toshimi Minoura */ /* October 1999, Jacob Lundberg */ /* */ /*****************************************************************************/ import java.awt.*; // A SLNodeG is a node in a singly-linked list. class SLNodeG { // class for nodes in a singly-linked list SLNodeG next; // next SLNodeG in a singly-linked list String key; // key value for this node public Object data; // data stored in this SLNodeG boolean focus; // node under focus SLNodeG(String key, Object data) { // constructor for a SLNodeG with data next = null; this.key = key; // set argument key to instance variable key this.data = data; // set argument data to instance variable data } // Allow nifty printing of key/data pairs. public String toString() { return key + ": " + data; } } class SListG extends StepTestCanvas { SLNodeG head; // head of doubly-linked list SLNodeG tail; // tail of doubly-linked list SLNodeG currentNode = null; // node currently being visited SLNodeG newNode = null; // node being inserted int nNodes = 0; // # of nodes in current list public void reset() { // initialize list head = null; tail = null; currentNode = null; newNode = null; nNodes = 0; } public void insertTail(String key, Object data) { newNode = new SLNodeG(key, data); // create new data node currentNode = null; repaintStep("New node with key = " + key + " will be added to tail. "); if (head == null) { // is list empty? head = newNode; // add single new data node } else { tail.next = newNode; // add new node at end } tail = newNode; currentNode = tail; nNodes++; SLNodeG newNodeTemp = newNode; newNode = null; currentNode = null; repaintStep("New node with key = " + key + " added to tail. "); System.out.println("Node with key = " + key + " added to tail."); } public SLNodeG removeHead() { SLNodeG tempNode = head; // save the head if( currentNode == head ) // avoid an oops currentNode = head.next; repaintStep("Node at head (with key = " + head.key + ") will be removed. "); head = head.next; // forget the head repaintStep("Node at head (with key = " + tempNode.key + ") removed. "); System.out.println("Node at head (with key = " + tempNode.key + ") removed."); return tempNode; // return the head } public Object find(String key) { // find value for key currentNode = null; repaintStep("Node with key = " + key + " will be searched for. "); for (SLNodeG current = head; current != null; current = current.next) { if (current.key == key) { // is key contained in current SLNodeG? System.out.println("Node containing " + key + " found."); currentNode = null; current.focus = true; // highlight node found repaintStep("Node with key = " + key + " found. "); current.focus = false; // end highlighting return current.data; // return data associated with key } else { currentNode = current; repaintStep("Node with key = " + key + " being searched for, node with key = " + current.key + " visited."); } } System.out.println("Node with key = " + key + " not found."); repaintStep("Node with key = " + key + " not found."); return null; } public void print() { // print content of list if (head == null) { // is list empty System.out.println("list empty"); return; } System.out.print("List content: "); for (SLNodeG current = head; current != null; current = current.next) { System.out.print(" key = " + current.key + ", data = " + current.data); } System.out.println(""); } public void drawRightArrow(Graphics g, int x1, int y1, int x2, int width) { int hWidth = width; Polygon poly = new Polygon(); // arrow from (x1, y1) to (x2, y1) poly.addPoint(x1, y1 - hWidth); poly.addPoint(x1, y1 + hWidth); poly.addPoint(x2 - 4, y1 + hWidth); poly.addPoint(x2 - 4, y1 + 4); poly.addPoint(x2, y1); // tip of right arrow poly.addPoint(x2 - 4, y1 - 4); poly.addPoint(x2 - 4, y1 - hWidth); g.fillPolygon(poly); // draw arrow } static Color LineColor = new Color(0, 0, 0); static Color NodeColor = new Color(0, 100, 0); static Color VisitedNodeColor = new Color(150, 255, 0); static Color FocusColor = new Color(225, 225, 0); static Color NewNodeColor = new Color(0, 255, 225); static final Color BoxColor = new Color(100, 0, 0); // for box outline static final int x1 = 50; // left position of list static final int y1 = 50; // top position of boxes static final int BoxWidth = 60; // width of node static final int LinkWidth = 30; // distance between nodes static final int BoxHeight = 30; // height of node Font f = new Font("TimesRoman", Font.BOLD, 18); public void paint(Graphics g) { g.setFont(f); // set font for letters if (head == null && newNode == null) { // initial condition g.drawString("List Empty", 250, 80); return; } if (newNode != null) { int newNodeX = x1 + (BoxWidth + LinkWidth) * nNodes; g.setColor(BoxColor); // set box outline color g.drawRect(newNodeX, y1, BoxWidth, BoxHeight); g.setColor(NewNodeColor); // set color for new Node g.fillRect(newNodeX, y1, BoxWidth, BoxHeight); g.setColor(Color.blue); // set color for node label g.drawString(newNode.data + ": " + newNode.key, newNodeX + 12, y1 + 21); } SLNodeG current = head; for (int i = 0; current != null; i++) { System.out.println("drawing SLNodeG with data " + current.data); int x = x1 + i * (BoxWidth + LinkWidth); // x position of node if (current.focus) { g.setColor(FocusColor); // set color for focused Node } else if (currentNode == current) { g.setColor(VisitedNodeColor); // set color for Node visited } else { g.setColor(NodeColor); // color for other Nodes } g.fillRect(x, y1, BoxWidth, BoxHeight); // draw box g.setColor(BoxColor); // set box outline color g.drawRect(x1, y1, BoxWidth - 1, BoxHeight - 1); // draw box outline if (currentNode == current || current.focus) { g.setColor(Color.blue); // set color for node label } else { g.setColor(Color.white); // for other node } // drawk key and value within node g.drawString(current.data + ": " + current.key, x + 12, y1 + 21); g.setColor(LineColor); // draw lines to children nodes if (current.next != null) { // draw link drawRightArrow(g, x + BoxWidth - 10, y1 + BoxHeight / 2, x + BoxWidth + LinkWidth, 2); } current = current.next; // go to next node } } public static void main(String argv[]) { new StepTestFrame("Singly-Linked List", new SListG(), 600, 250).show(); } public void runMain() { // This sequence of requests has not been debugged. // If anything is wrong, please inform the instructor. reset(); // make list empty repaintStep(); int i = 0; // counter insertTail("A", new Integer(++i)); print(); insertTail("B", new Integer(++i)); print(); insertTail("C", new Integer(++i)); print(); System.out.println("Data associated with key = \"B\": " + find("B")); System.out.println("Removed node is " + removeHead()); print(); insertTail("D", new Integer(++i)); print(); insertTail("E", new Integer(++i)); print(); System.out.println("Removed node is " + removeHead()); print(); System.out.println("Removed node is " + removeHead()); print(); System.out.println("Data associated with key = \"B\": " + find("B")); System.out.println("Data associated with key = \"D\": " + find("D")); repaintStep("Commands exhausted: Press the Restart button."); } }