Unformatted text preview:

Linked ListsLinked List : DefinitionSlide 3A Linked List Node ClassFinal IntegerNode ClassFinal IntegerNode Class (2)A Polymorphic Linked List NodeSlide 8Inserting a Node into a Linked ListInserting a Node into a Linked List (First Node)Deleting a Node from a Linked ListTraversing a Linked ListRecursive Linked List TraversalRemoving Tail RecursionInsert and Delete operations on an empty listAbstract Data Type ListCriteria for Linked Lists - ACIDSACIDS CriteriaSlide 19Interface for ADT ListComparable Node ClassComparable Node Class (2)Implementation of ADT ListImplementation of ADT List (2)Implementation of ADT List (3)Implementation of ADT List (4)Implementation of ADT List (5)Implementation of ADT List (6)Implementation of ADT List (7)Iterative reversed listing Why recursion is your friendDoubly Linked ListsDoubly Linked List ImplementationDoubly Linked List Implementation (2)Doubly Linked List InsertionDoubly Linked List DeletionHeader Nodes for Doubly Linked ListsCircular Linked ListsSolution: Use Object Inequality1Linked ListsChapter 42Linked List : Definition•Linked List:–A collection of data items of the same type that are stored in separate objects referred to as "nodes".–Each node contains, in addition to its data value(s) a reference to an object of the same type. This reference is used to connect one node to the next node in the list.3Linked List : Definition•Linked List:–An external reference usually referred to as the "head" of the list contains the address of the first node object.•Diagram of a sample linked list containing character data:headA B CnullD4A Linked List Node Class•First attempt at a class for a linked list of integers:public class IntegerNode { public int item; public IntegerNode next;}–The problem with this solution is that it uses no data hiding - all data fields in a class should be "private" and data should be set/retrieved only with constructors, accessors, and mutators.5Final IntegerNode Classpublic class IntegerNode { private int item; private IntegerNode next; public IntegerNode(int newItem) { item = newItem; next = null; } // end constructor public IntegerNode(int newItem, IntegerNode nextNode) { item = newItem; next = nextNode; } // end constructor6Final IntegerNode Class (2) public void setItem(int newItem) { item = newItem; } // end setItem public int getItem() { return item; } // end getitem public void setNext(IntegerNode nextNode) { next = nextNode; } // end setNext public IntegerNode getNext() { return next; } // end getNext} // end class IntegerNode7A Polymorphic Linked List Nodepublic class Node { private Object item; private Node next; public Node(Object newItem) { item = newItem; next = null; } // end constructor public Node(Object newItem, Node nextNode) { item = newItem; next = nextNode; } // end constructor8A Polymorphic Linked List Node public void setItem(Object newItem) { item = newItem; } // end setItem public Object getItem() { return item; } // end getitem public void setNext(Node nextNode) { next = nextNode; } // end setNext public Node getNext() { return next; } // end getNext} // end class NodeTo instantiate a Node containing an Integer: Node n = new Node(new Integer(6));or containing a character: Node n = new Node(new Character('A'));9Inserting a Node into a Linked List5newNodehead1prev3 7 9curnewNode = new Node ( Integer (5) );newNode.setNext ( cur );prev.setNext ( newNode );10Inserting a Node into a Linked List (First Node)5newNodehead1prev3 7 9curnewNode = new Node ( Integer (5) );newNode.setNext ( head );head = newNode;11Deleting a Node from a Linked Listhead1prev3 7 9curprev.setNext ( cur.getNext() );12Traversing a Linked Listfor ( Node cur = head ; cur != null ; cur = cur.getNext() ) { System.out.println ( cur.getItem() );}head1 3 7nullnull9cur13Recursive Linked List Traversalprivate static void writeList(Node nextNode) {// -------------------------------------------------------// Writes a list of objects.// Precondition: The linked list is referenced by nextNode.// Postcondition: The list is displayed. The linked list// and nextNode are unchanged.// ------------------------------------------------------- if (nextNode != null) { // write the first data object System.out.println(nextNode.getItem()); // write the list minus its first node writeList(nextNode.getNext()); } // end if} // end writeList14Removing Tail Recursionprivate static void writeList(Node nextNode) {// -------------------------------------------------------// Writes a list of objects.// Precondition: The linked list is referenced by nextNode.// Postcondition: The list is displayed. The linked list// and nextNode are unchanged.// -------------------------------------------------------// nextNode holds the head of the list on entry while (nextNode != null) { // if becomes while // write the data object referenced by nextNode System.out.println(nextNode.getItem()); // replace recursive call with parameter update nextNode = nextNode.getNext(); } // end while} // end writeList15Insert and Delete operations on an empty list Problem with insertion and deletion methods:They require special cases and different actions for first nodes. The addition of a dummy head node to the linked list eliminates the special cases-the node does not contain any data-an empty list consists of head and the dummy node16Abstract Data Type List•A linked list is actually just one implementation of the higher object which is a General List–A General List could be implemented using arrays rather than linked lists–How would that implementation change from the linked list implementation?17Criteria for Linked Lists - ACIDS•Decide which General List implementation is better by observing General List operations:•ACIDS tests how easily are operations done–Add–Change–Inspect–Delete–Sort18ACIDS Criteria•Linked lists are better for adding or deleting items.–Insertion and deletion require constant time complexity once position is located.–In array based lists insertion and deletion require linear time complexity since all n items might have to be moved.19ACIDS Criteria•Arrays are better for sorting or finding items.–Allow random access to elements.–This allows the use of divide and conquer algorithms.20Interface for ADT List// ****************************************************//


View Full Document

EWU CSCD 300 - Definition

Download Definition
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Definition and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Definition 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?